# sorting apstring help

• 03-13-2002
Unregistered
sorting apstring help
I have a linked list of several US capitals in which I need to put in alpha order. Each node of my linked list looks like this....

struct node
{
apstring capital;
node *next;
};

and the capitals are....

Richmond
Hartford
Annapolis
Montgomery
Albany
Harrisburg
Sacramento
Atlanta
Bizmark
Providence

any help would be GREATLY appreciated
• 03-13-2002
Prelude
What is your problem exactly? My crystal ball has been decommissioned.

-Prelude
• 03-13-2002
Unregistered
how to do it depends on what type of list you are using and what methods are available in apstring.

If you are using a list which is an instance of the STL list class, then you can use the generic STL function called sort() or a list member function called sort(), I belive. If you have an aplist class it might have similar functionality.

Otherwise, you can write your own sorting function. I prefer to sort at time of insertion. But you could develop your own "bubble sort" to work with a list too, I suppose. It might look something like this (code not compiled or tried):

Code:

```//use a node called current nd previous to help keep your place node * current; node * previous; //if your list's head node is not already a "blank" holding node, make it so. node * blank = new node; blank->next = head; head = blank; delete blank; blank = NULL; //likewise create a blank end node node * end = new node; end->next = NULL; //and put it in place current = head->next; while(current-next != NULL) {   current = current->next; } current->next = end; //now bubble the "largest" node capital to the spot before end while(end != head->next->next)//need two nodes to compare! {   //each time through list (re)set current and previous   current = head->next;   previous = head;   while(current->next != end) //need two nodes to compare!   {     //compare nodes using the > operator if available in apstring     if(current->capital > current->next->capital)     //if > not overloaded in apstring use strcmp()     //if(strcmp(current->capital, current->next->capital) > 0)     {       //switch nodes current and current-next to get bubble effect       blank = current->next->next;       previous->next = current->next;       current->next->next = current;       current->next = blank;     }     else     {       current = current->next;     }   }   //advance end one to the left   end = current->next; }```
• 03-13-2002
Unregistered
after posting my code above, I've had the nagging feeling I left something out. Now I know what it is. You should put a blank node called tail at the end of the list, and assign tail to end before you start sorting the list. That way there will always be a tail with NULL at the last pointer called next. If you just keep shifting end to the left each time through the outer loop, then there won't be a NULL at the "tail end" of the list.