sorting a linked list

[Unregistered]

Hello to all,

I have to write a function, insertionSort(Node* head), that accepts a linked list as its parameters, and sort its data (int key) in ascending order. The structure of detail and the function I have so far coded are as follows:

#include <stdio.h>
#include <stdlib.h>

struct node {
int key;
struct node* next;
};

typedef struct node Node;


/*********************************** */

Node* insertionSort(Node* head) {
Node *previousNode, *currentNode,*nextPtr;
currentNode=head;

while(currentNode != NULL){
previousNode=currentNode;

if(currentNode->next != NULL){
nextPtr=currentNode->next;
currentNode=nextPtr;
}
else
currentNode=currentNode;
if(previousNode->key > currentNode->key){
if(currentNode->next==NULL){
previousNode->next=NULL;
currentNode->next=previousNode;
}
else{
previousNode->next=currentNode->next;
currentNode->next=previousNode;
}
}
}
return head;
}


Can any one point me to the write direction in terms of if I am in right track, and what I have done wrong in the above code.

Thanks,

DTM

[sean345]

There are a couple ways to sort a linked list. You could find out how long this linked list is, create a new linked list and copy over from the first list to the second in the sorted order.

Another way is to start at the beginning and compare the two lists in a row. If the second one is larger then switch the two and continue down the list. Continue looping in this fashion. When you reach the end of the list and none of the items had been switched then the list is sorted.

For example, This is the data in the initial order: 5, 8, 1, 2, 1. First the sorter sees the first two numbers and switches them because 8 is larger. New order: 8, 5, 1, 2, 1. Then the sorter skips 5 and 1 because they are in order. Next 1 and 2 are switched. New Order: 8, 5, 2, 1, 1. 1 and 1 remain the same because there are no changes to make. Looping one more time finds that there is nothing to change and thus the list is softed.

- Sean

[stautze]

I am guessing this is homework, and you have to use the insertion sort type of sort. If so than there is only one alogorithm that will do this.

To do an insertion sort (on a linked list) you have to you have to go through the original list one item at a time and inserting each item it in its proper place in the sorted list as you come to it.

You need to create some pointer Nodes, so you know where you are in the list.

For example:

Node *fu; // first unsorted node
Node *ls; // last sorted node
Node *current, *trailing;

Use the pointer current to search the sorted list to find where to insert fu. If fu goes before current put it there. If not move down the list until current.key >= fu.key and insert fu before current.

To enable insertion before current, keep the pointer trailing one position closer to the head than trailing.

Hope that helps.

[Osama Lives]

struct node_s
{ 
  int key; 
  node_s * next; 
}note _t;

The problem here is that you don't have a record yet. All you have is a key. It isn't too difficult to switch records between nodes, but it would be more difficult to try to disassemble your whole list. So make your example more mature like so:

struct rec
{
   int key;
   char array[30];
   double income;
}rec_t;

struct node_s
{
   struct rec_t rec;
   node_s *next;
}node_t;

Now when you compare keys, you can just switch records (rec_t), rather than disassemble your list.