Re: link-list sorting (54 Views)
Reply
Regular Advisor
amit mehta_2
Posts: 119
Registered: ‎07-05-2006
Message 1 of 11 (54 Views)
Accepted Solution

link-list sorting

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
Please use plain text.
Regular Advisor
amit mehta_2
Posts: 119
Registered: ‎07-05-2006
Message 2 of 11 (54 Views)

Re: link-list sorting

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

~amit
Please use plain text.
Esteemed Contributor
Hemmetter
Posts: 284
Registered: ‎10-17-2000
Message 3 of 11 (54 Views)

Re: link-list sorting

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

Please use plain text.
Honored Contributor
Sandman!
Posts: 2,220
Registered: ‎01-13-2005
Message 4 of 11 (54 Views)

Re: link-list sorting

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.
Please use plain text.
Acclaimed Contributor
A. Clay Stephenson
Posts: 17,825
Registered: ‎07-16-1998
Message 5 of 11 (54 Views)

Re: link-list sorting

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

If it ain't broke, I can fix that.
Please use plain text.
Acclaimed Contributor
Dennis Handly
Posts: 24,402
Registered: ‎03-06-2006
Message 6 of 11 (54 Views)

Re: link-list sorting

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

Please use plain text.
Regular Advisor
amit mehta_2
Posts: 119
Registered: ‎07-05-2006
Message 7 of 11 (54 Views)

Re: link-list sorting

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
Please use plain text.
Acclaimed Contributor
Dennis Handly
Posts: 24,402
Registered: ‎03-06-2006
Message 8 of 11 (54 Views)

Re: link-list sorting

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.
Please use plain text.
Acclaimed Contributor
Dennis Handly
Posts: 24,402
Registered: ‎03-06-2006
Message 9 of 11 (54 Views)

Re: link-list sorting

>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.
Please use plain text.
Regular Advisor
amit mehta_2
Posts: 119
Registered: ‎07-05-2006
Message 10 of 11 (54 Views)

Re: link-list sorting

Thanks Dennis,and also to everyone else.
Points to follow :)
Please use plain text.
Regular Advisor
amit mehta_2
Posts: 119
Registered: ‎07-05-2006
Message 11 of 11 (54 Views)

Re: link-list sorting

Closing the thread.
Please use plain text.
The opinions expressed above are the personal opinions of the authors, not of HP. By using this site, you accept the Terms of Use and Rules of Participation