link-list sorting

[amit mehta_2]

Hi,

Pasted below is my procedure(SortList) to sort the singly link-list,but this is not working.
i might be doing something stupid,and i would really appreciate if you guys
can let me realize the mistake in my code(a silly code with no importance)

4 struct node{
5 int data;
6 struct node *next;
7 };

29 /* returns the length of the link list*/
30 int Length(struct node* head){
31 struct node *current = head;
32 int count = 0;
33 while(current != NULL){
34 count++;
35 current = current->next;
36 }
37 return(count);
38 }

40 /* prints the data field of the each node*/
41 void LinkTraverse(struct node* head){
42 struct node* current = head;
43 int i = 1;
44 while(current != NULL){
45 printf("element %d is %d\n",i,current->data);
46 i++;
47 current = current->next;
48 }
49 }


140 /*sort the link*/
141 void SortList(struct node** headRef){
142 struct node* current = *headRef;
143 int i,j,temp,length;
144 length = Length(current);
145 for(i = length;i >= 1 ; i--){
146 for(j = 1; j <= i; j++){
147 if(current->data > current->next->data){
148 temp = current->data;
149 current->data = current->next->data;
150 current->next->data = temp;
151 }
152 }
153 }
154 LinkTraverse(head);
155 }

~amit

[amit mehta_2]

please read LinkTraverse(head);
as LinkTraverse(current);

~amit

[Hemmetter]

Hi Amit,

you never move your current pointer through the list and always compare the same current with current->next;

you miss something like

145.5 current=*headRef;
/* begin the walk trough the list each for-i-iteration */

and

150.5 current=current->next;
/* step one listelement foreward each for-j iteration */


Hint: dont exchange data but pointers, imagine your data is not only "int" but something multi megabyte sized.


rgds
HGH

[Sandman!]

Few questions regarding your post. Why do you want to singly-link integers when they can all be put into a big array? Unless you are allocating memory for each of them dynamically but for that I see no calls to malloc(3C). Also have you looked at either quick sort or binary sort. Those algorithms have been tried and tested for integer data. Might be better to run your data through them before developing a new kind of sort.

[A. Clay Stephenson]

... and most implementations of linked lists that do need to be ordered insert the elements in the correct location so that no sorting is ever required.

[Dennis Handly]

You may want to use a real language like C++ to do all of this:

std::list i_list; // doubly linked list
i.size()

std::ostream& operator<<(std::ostream o, std::list l) {
for (std::list::iterator i = l.begin(); i != l.end(); ++i)
std::cout << *i;
}

i.sort();

[amit mehta_2]

Thanks to all of you for these suggestions.

Sandman, pasted below is a small code for depiciting bubble sort:

1 #include
2 #include
3
4 void BubbleSort(int numbers[],int arraySize){
5 int i,j,temp;
6 for(i = (arraySize - 1) ; i >= 0 ; i--){
7 for(j = 1; j <= i; j++){
8 if(numbers[j - 1] > numbers[j]){
9 temp = numbers[j - 1];
10 numbers[j - 1] = numbers[j];
11 numbers[j] = temp;
12 }
13 }
14 }
15 i = 0;
16 while(i != arraySize){
17 printf("%d\n",numbers[i]);
18 i++;
19 }
20 }
21 int main(void){
22 int numbers[5] = {2,12,4,3,9};
23 BubbleSort(numbers,5);
24 exit(EXIT_SUCCESS);
25 }

Also in my previous post i missed to post the list building function,in which i have used malloc for getting memory from the heap.

10 struct node* BuildOneTwoThree(void){
11 struct node *head,*second,*third;
12 third = second = head = NULL;
13 head = (struct node*)malloc(sizeof(struct node));
14 second = (struct node*)malloc(sizeof(struct node));
15 third = (struct node*)malloc(sizeof(struct node));
16
17 head->data = 12;
18 head->next = second;
19
20 second->data = 2;
21 second->next = third;
22
23 third->data = 7;
24 third->next = NULL;
25
26 return(head);
27 }

HGH,
thanks a lot for pointing the mistake(current pointer left unincremented), after doing the same,still there was no change in the output :(

~amit

[Dennis Handly · Accepted solution]

Change your loops to:
for (i = length; i > 1; --i) {
current = *headRef;
for (j = 1; j < i; ++j){
register struct node *n = current->next;
if (current->data > n->data){
temp = current->data;
current->data = n->data;
n->data = temp;
}
current = n;
}
}
LinkTraverse(*headRef);

Note SortList should really be declared as:
void SortList(struct node *head);

Unless you are going to do the pointer interchange as HGH hinted.

[Dennis Handly]

>pasted below is a small code for depicting bubble sort:

I forgot to mention, the only use of a bubble sort is to put on a wanted poster of a poster child of what not to do. :-)
A shell sort is much faster and about as easy to program. Especially if you have random access iterators as in your array.

[amit mehta_2]

Thanks Dennis,and also to everyone else.
Points to follow :)