単数のリンクリストの選択ソート

Question

単数のリンクリストの選択ソートを行うアルゴリズムを開発する必要があります。これは割り当てや解放をしません。以下のコードはそうしていますか？ whileループの代わりにループ用にこのコードを変更するにはどうすればよいですか？

/************************** SortList ************************************ 

Description Arranges the singly linked list pointed to by List in 
natural order. It is assumed that the list has a dummy 
head node. 

The algorithm used is a linked variation of the selection 
sort and works like this: 
Start with EndSorted aimed at first node of list 

repeat 
Find smallest char between EndSorted and end of list 
Swap smallest element with char in EndSorted 
Change EndSorted to next node 
until we get to end of list 

None of the pointers in linked list are changed 

Parameters 
IN, List A pointer to a singly linked list with a dummy head node 
-----------------------------------------------------------------------*/ 
typedef Node* NodePtr; 
void SortList(NodePtr List) 
{ 
    NodePtr SmallNode;  //points to smallest char 
    NodePtr SearchNode;  //used to search each node in list 
    NodePtr EndSorted;  //points to list to sort 
    char TempCh; 
if (List->Link != NULL) //List is not empty 
    EndSorted = List->Link; //make EndSorted point to the beginning of List 

else //List is empty 
    EndSorted = List; //EndSorted points to dummy head Node and the following loop 

         //will never execute 

while (EndSorted->Link != NULL) //make sure EndSorted is not at the end of List 

{ 
    SmallNode = EndSorted; //give SmallNode a starting value 

    SearchNode = EndSorted->Link; //make SearchNode point to the Node after EndSorted 

    while (SearchNode != NULL) //make sure SearchNode is not at the end of List 
    { 
     if (SearchNode->Ch < SmallNode->Ch) //check the Ch value of the two Nodes 

      SmallNode = SearchNode; //if SearchNode -> Ch is smaller then SmallNode -> Ch 

            //make SmallNode point to SearchNode 

     SearchNode = SearchNode->Link; //advance SearchNode to the next Node 
    } 

    TempCh = EndSorted->Ch; //place the Ch value in EndSorted in TempCh 

    EndSorted->Ch = SmallNode->Ch; //swap SmallNode -> Ch with EndSorted -> Ch 

            //This places the smallest unsorted value in List at the beginning 
    SmallNode->Ch = TempCh; 

    EndSorted = EndSorted->Link; //advance EndSorted to the next Node 
} 
} 

だからこのようになりますか？

void SortList(NodePtr List) 
{ 
    NodePtr SmallNode;  //points to smallest char 
    NodePtr SearchNode;  //used to search each node in list 
    NodePtr EndSorted;  //points to list to sort 
    char TempCh; 

    if (List->Link != NULL) //Makes sure the list is not empty 
    { 
     /* (Points EndSorted at the first non-dummy node node; While EndSorted is not at the end of the list; 
     Advance EndSorted to the next node) */ 

     for (EndSorted = List->Link; EndSorted->Link != NULL; EndSorted = EndSorted->Link) 

     { 

      SmallNode = EndSorted; //Start SmallNode with the data of the first (Non-Dummy) Node 


      /*Points SearchNode at the Node after the Current EndSorted location; While Search Node is not at the end of the list; 
      Advance SearchNode to The next node*/ 

      for (SearchNode = EndSorted->Link; SearchNode != NULL; SearchNode = SearchNode->Link) 
      { 
       if (SearchNode->Ch < SmallNode->Ch) //compares the values of the two nodes 
       { 

        SmallNode = SearchNode; //if search node is smaller, swap them 
       }       //to update the smallest node on this pass 
              //once all values have been checked, and the smallest is found 
              //it will be moved to the front of the list, or, after the node 
              //it is slightly larger than 



      } //smallest node has been found, begin swap and end the inner while loop 

      TempCh = EndSorted->Ch; //TempCh holds the value of the Ch held by EndSorted 

      EndSorted->Ch = SmallNode->Ch; //EndSorted now holds the smallest unsorted node's value 

      SmallNode->Ch = TempCh; //SmallNode now holds the value EndSorted originally held 


     }        
    } 
} 

Answer 1

選択のためのアルゴリズムの一種である：私は概念が適用され、アレイ のためではなく、リンクリストのために行っている

int min;// min element is declared 
for (int i = 0; i < size; ++i) 
{ 
    min=i; 
    for (int j = i + 1; j < size+1; ++j) 
     { 
     if (ar[j] < ar[min]) 
      { 
      min = j; 
      } 
     } 
     swap (ar[i],ar[min]); 
} 

が同じになりますちょうどトラバーサルのために使用される任意の変数が存在することになるとar [i]はノードの値を返す関数に置き換えられます。そして、エンドノードがnode.next（）！= nullを意味するまで、リストはトラバースされます。 アルゴリズムについては、次のリンクをご覧ください： http://www.sanfoundry.com/cplusplus-program-implement-selection-sort/