sorting a linked list

[prophetjohn]

so, i was just introduced to linked lists and most of the basic operations, i have down pretty well. i'm having a little difficulty coming up with algorithms for sorting and shuffling a linked list, though.

i've got two algorithms in mind for sorting, but i keep getting myself turned around when trying to implement them. any input on which is easier to implement or if you have a better suggestion, that's cool too.

1) something like selection sort. traverse the list to find the smallest value, traverse it again to find it again and remove it, then traverse it again to insert it where it belongs

2) create a new empty list. traverse the original list to find the smallest value. traverse it again to find/remove it. append the value to the end of the new list. then at the end say head = newHead

thanks

[D80DSL3A]

Are you sorting in descending order then? Highest value first, lowest value last?
If so, then:
1) Selection sort: Traverse entire list to find the highest value then move it to the beginning of the list. Next, traverse the list starting from the 2nd node to find the 2nd highest value then move it to 2nd in the list. Repeat this for the remainder of the list.

i keep getting myself turned around when trying to implement them.

Yeah, it's easy to get confused with link lists. I find it helps a lot to make a sketch (a circle for each node with arrows joining them) to help keep track of it all.

If you want the list to always be sorted then I think the simplest way is to always insert a new node where it belongs in the list instead of at the head. This way the list is maintained in a sorted state. No later sorting is needed.

[prophetjohn]

thanks for your input. i ended up getting the second algorithm to work.

unfortunately, getting the list into a sorted state and keeping it there isn't possible. this is for a class. i'm implementing the storage portion of an mp3 player and have to demonstrate sorting and shuffling algorithms

here's the code i ended up with if anyone wants to add any input:

void TsuPod::sortSongList() {
    int numElements = 0;
    Node * previousNode = NULL,     //the node prior to the one being check
         * nodePtr = NULL,          //the node being checked
         * smallest = NULL,         //the smallest node left in the list
         * newHead = NULL,          //beginning of new, temporary list
         * lastNew = NULL,          //end of new, temporary list
         * beforeSmall = NULL,      //the node prior to the smallest in the list
         dummy;                     //temporary first node in temporary list

    if (!head || !(head->next))     //a list of size 0 or 1 is already sorted
    	return;
    
    nodePtr = smallest = head;      //assume 1st element is smallest
    newHead = &dummy;               //initalize the new, empty list
    newHead->next = NULL;           //    "      "   "     "    "
    
    lastNew = newHead;              //establish the end of the temp list

    while (nodePtr) {               //count the number of elements in the list
        numElements++;
        nodePtr = nodePtr->next;
    }     

    for (int i = 0; i < numElements; i++) {
        smallest = head;            //assume first element is smallest
        nodePtr = head;             //reset nodePtr to list head
        previousNode = NULL;        //no node prior to first
        beforeSmall = NULL;         //same as previoudNode
        while (nodePtr) {           //while not at end of list
            //compare each node to the current smallest node
            if (nodePtr->song < smallest->song) {
                smallest = nodePtr;             //store address of smaller node
                beforeSmall = previousNode;     //store address of previous node
            }
            previousNode = nodePtr;             //increment previousNode
            nodePtr = nodePtr->next;            //increment nodePtr
        }
        if (beforeSmall == NULL) {              //first element is smallest
            head = smallest->next;              //chop out the first node
        }
        else {                                  //first element is not smallest
            beforeSmall->next = smallest->next; //chop out the smallest
        }
        lastNew->next = smallest;   //append smallest to temp list
        lastNew = lastNew->next;    //increment lastNew
        lastNew->next = NULL;       //make end of list point to NULL
    }
    head = newHead->next;           //at the end make the original list point
                                    //to the sorted list
}