topic Re: link-list sorting in Operating System - Linux

link-list sorting

amit mehta_2 — Wed, 05 Dec 2007 13:48:46 GMT

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

Re: link-list sorting

amit mehta_2 — Wed, 05 Dec 2007 13:50:25 GMT

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

~amit

Re: link-list sorting

Hemmetter — Wed, 05 Dec 2007 18:03:14 GMT

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

Re: link-list sorting

Sandman! — Wed, 05 Dec 2007 18:25:38 GMT

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.

Re: link-list sorting

A. Clay Stephenson — Wed, 05 Dec 2007 20:41:29 GMT

... 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.

Re: link-list sorting

Dennis Handly — Thu, 06 Dec 2007 01:26:22 GMT

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();

Re: link-list sorting

amit mehta_2 — Thu, 06 Dec 2007 06:31:50 GMT

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

Re: link-list sorting

Dennis Handly — Thu, 06 Dec 2007 07:05:22 GMT

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.

Re: link-list sorting

Dennis Handly — Thu, 06 Dec 2007 07:08:44 GMT

>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.

Re: link-list sorting

amit mehta_2 — Thu, 06 Dec 2007 07:32:33 GMT

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

Re: link-list sorting

amit mehta_2 — Thu, 06 Dec 2007 09:19:45 GMT

Closing the thread.