이중 연결된 목록을 정렬하는 방법을 알아낼 수 없습니까?

Question

이중 연결된 목록을 오름차순으로 정렬하는 방법을 알아 내려고했지만 내 머리를 감쌀 수 없습니다. 내 머리글 들어, 내가 select_sort 그것을 정렬하는 함수와 함께 다음과 같습니다.

#ifndef INTLIST_H 
#define INTLIST_H 

struct IntNode{ 
    int data; 
    IntNode *next; 
    IntNode(int data) : data(data), next(0) {} 
}; 

class IntList{ 
private: 
    IntNode *head; 
    IntNode *tail; 
public: 
    void select_sort(); 

편집 :

내 끔찍한 기능

void IntList::select_sort(){ 
    for(IntNode *holder = head; holder != NULL; holder = holder -> next){ 
      IntNode *temp2 = holder; 
      for(IntNode *temp = holder -> next; temp!=NULL;temp = temp->next){ 
       if(temp2 -> data > temp -> data){ 
        temp2 = temp; 
       } 
      } 
      int holder2 = tail -> data; 
      tail -> data = temp2 -> data; 
      temp2 -> data = holder2; 
    } 
} 

Answer 1

선택 정렬 기본적 개념에서 이동 목록과 정렬 된 목록의 끝 스왑을의 ​​나머지 부분에서 가장 작은 요소를 발견 목록의 끝에 도달 할 때까지 왼쪽에서 오른쪽으로 외부 루프의 첫 번째 패스 후에는 목록의 첫 번째 요소가 가장 낮은 값을 갖습니다. Wikipedia에는 선택 정렬 작업 중 우수한 애니메이션이 있습니다.

홀더에서 시작하는 값이 가장 작은 노드를 추적하려면 포인터가 필요합니다.

IntNode *min = holder; 

그러면 현재 노드 temp가 min보다 작은 경우 temp를 가리 키도록 min을 업데이트하십시오. inner for 루프 다음에 min과 holder를 바꿀 필요가 있습니다. 목록의 나머지 부분에있는 가장 작은 요소가 이제 정렬 된리스트의 끝에 있습니다.