알고리즘 - 링크 정렬 (거품, 선택, 삽입)

정렬 알고리즘
고전 정렬 알고리즘 은 거품, 선택, 삽입 을 포함한다.
 
다음은 오름차 순 으로 한 마디 설명 을 드 리 겠 습 니 다.
거품 - N - 1 차 순환 을 하고 매번 순환 할 때마다 첫 번 째 요소 부터 이 요 소 를 그 후의 요소 와 비교 하 며 전자 가 크 면 위 치 를 바 꾸 고 마지막 위치 요소 가 비 교 될 때 까지 실행 이 끝나 면 가장 큰 요 소 는 마지막 위치 에 있 습 니 다. 물 속 기포 가 위로 올 라 가 는 과정 과 비슷 하고 위로 올 라 갈 수록 기포 가 큽 니 다.
 
선택 - N - 1 회 순환 을 하고 매번 순환 할 때마다 정렬 되 지 않 은 모든 요 소 를 옮 겨 다 니 며 가장 큰 요 소 를 찾 아 꼬리 에 놓 으 면 마지막 위 치 를 최대 요소 로 보장 합 니 다.포 지 셔 닝 의 과정 은 선택 이다.
 
삽입 - N - 1 차 순환 을 진행 합 니 다. 매번 순환 할 때마다 정렬 되 지 않 은 첫 번 째 요 소 를 꺼 내 고 이 요 소 를 새로운 서열 표 에 삽입 합 니 다. 삽입 과정 은 질서 있 는 목록 에서 첫 번 째 요 소 를 시작 으로 삽입 할 요소 보다 큰 요 소 를 찾 습 니 다. 삽입 할 요 소 를 이 요소 에 삽입 하기 전에 삽입 합 니 다.
 
배열 형식의 정렬 알고리즘 예 는 다음 박문 을 보십시오.
http://www.cnblogs.com/peggy89321/p/3246466.html
 
본 고 는 단일 체인 테이블 형식의 정렬 코드 를 제시한다.
https://github.com/fanqingsong/code-snippet/blob/master/C/listOrder/listOrder.c
 
정렬 선택

    /***********************************************************************
                                    selecting sort method
    ************************************************************************/

    // find specific node by strcmpfunc and detach it from list
    PT_NODE FindAndDetachNode(PT_NODE ptHeadNode, STRCMPFUNC strcmpfunc )
    {
        PT_NODE ptTargetNode = NULL;
        PT_NODE ptPreMax = NULL;
        PT_NODE ptCurNode = NULL;
        PT_NODE ptPreNode = NULL;

        ptTargetNode = ptHeadNode->next;
        ptPreMax = ptHeadNode;

        ptCurNode = ptHeadNode->next;
        ptPreNode = ptHeadNode;
        while( ptCurNode )
        {
            // current node string is larger than specific node string, record it
            if ( strcmpfunc(ptCurNode->str, ptTargetNode->str) )
            {
                ptTargetNode = ptCurNode;
                ptPreMax = ptPreNode;
            }

            ptPreNode = ptCurNode;
            ptCurNode = ptCurNode->next;
        }

        // specific node found, detach it from list
        if ( ptTargetNode )
        {
            ptPreMax->next = ptTargetNode->next;
            ptTargetNode->next = NULL;
        }

        // return specific node
        return ptTargetNode;
    }

    // sort list by specific order by strcmpfunc
    void SortListWithSelectMethod(PT_NODE ptHeadNode, STRCMPFUNC strcmpfunc)
    {
        T_NODE tNewHead = {NULL, NULL};
        PT_NODE ptNode = NULL;

        // selection sort method
        while( TRUE )
        {
            // find target node and detach it from list
            ptNode = FindAndDetachNode(ptHeadNode, strcmpfunc);
            if ( !ptNode )
            {
                break;
            }

            // insert target node into new list from head
            InsertNode2ListHead(&tNewHead, ptNode);
        }

        // reset head node to new list
        ptHeadNode->next = tNewHead.next;
        tNewHead.next = NULL;
    }

 
거품 정렬

    /***********************************************************************
                                    bubble sort method
    ************************************************************************/

    // bubble list by strcmpfunc and detach last from list
    PT_NODE BubbleAndDetachLast(PT_NODE ptHeadNode, STRCMPFUNC strcmpfunc)
    {
        PT_NODE ptCurNode = NULL;
        PT_NODE ptPreNode = NULL;
        PT_NODE ptNextNode = NULL;

        ptCurNode = ptHeadNode->next;
        ptPreNode = ptHeadNode;
        while( ptCurNode )
        {
            ptNextNode = ptCurNode->next;
           
            // reach list tail
            if ( !ptNextNode )
            {
                break;
            }
       
            // current node string is larger than next node string, swap it
            if ( strcmpfunc(ptCurNode->str, ptNextNode->str) )
            {
                ptPreNode->next = ptNextNode;
                ptCurNode->next = ptNextNode->next;
                ptNextNode->next = ptCurNode;

                // reset current node's previous node
                ptPreNode = ptNextNode;
            }
            else
            {
                ptPreNode = ptCurNode;
                ptCurNode = ptCurNode->next;
            }
        }

        //detach current node from list
        ptPreNode->next = NULL;

        // current node is the last node, return it
        return ptCurNode;
     
    }

    // sort list by specific order by strcmpfunc
    void SortListWithBubbleMethod(PT_NODE ptHeadNode, STRCMPFUNC strcmpfunc)
    {
        T_NODE tNewHead = {NULL, NULL};
        PT_NODE ptNode = NULL;

        // selection sort method
        while( TRUE )
        {
            // bubble list and detach last from list
            ptNode = BubbleAndDetachLast(ptHeadNode, strcmpfunc);
            if ( !ptNode )
            {
                break;
            }

            // insert max node into new list from head
            InsertNode2ListHead(&tNewHead, ptNode);
        }

        // reset head node to new list
        ptHeadNode->next = tNewHead.next;
        tNewHead.next = NULL;
    }

 
삽입 정렬

    /***********************************************************************
                                    inserting sort method
    ************************************************************************/
    PT_NODE DetachFirstNode(PT_NODE ptHeadNode)
    {
        PT_NODE ptFirstNode = NULL;

        ptFirstNode = ptHeadNode->next;

        // detach first node from list
        if ( ptFirstNode )
        {
            ptHeadNode->next = ptFirstNode->next;
        }

        return ptFirstNode;
    }

    // insert node into list by inserting sort method
    void InsertNode2ListByInsertMethod(PT_NODE ptHeadNode, PT_NODE ptNode, STRCMPFUNC strcmpfunc)
    {
        PT_NODE ptPrevNode = NULL;
        PT_NODE ptCurNode = NULL;

        ptPrevNode = ptHeadNode;
        ptCurNode = ptPrevNode->next;

        while( ptCurNode )
        {
            if ( strcmpfunc(ptCurNode->str, ptNode->str) )
            {
                ptPrevNode->next = ptNode;
                ptNode->next = ptCurNode;

                // insert ok, let's leave
                break;
            }
            else
            {
                ptPrevNode = ptCurNode;
                ptCurNode = ptCurNode->next;
            }
        }

        // current node is NULL, previous node is last node of list,
        // ie, insert not ok,  the node shall be added to tail
        if ( !ptCurNode )
        {
            ptPrevNode->next = ptNode;
            ptNode->next = NULL;
        }
    }

    // sort list by specific order by strcmpfunc
    void SortListWithInsertMethod(PT_NODE ptHeadNode, STRCMPFUNC strcmpfunc)
    {
        T_NODE tNewHead = {NULL, NULL};
        PT_NODE ptNode = NULL;

        // selection sort method
        while( TRUE )
        {
            // get first node from list
            ptNode = DetachFirstNode(ptHeadNode);
            if ( !ptNode )
            {
                break;
            }

            // insert the node into new list by inserting method
            InsertNode2ListByInsertMethod(&tNewHead, ptNode, strcmpfunc);
        }

        // reset head node to new list
        ptHeadNode->next = tNewHead.next;
        tNewHead.next = NULL;
    }