Showing results for
Do you mean

SOLVED

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*/
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*/
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 }

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 }
155 }

~amit
1 ACCEPTED SOLUTION
Acclaimed Contributor

for (i = length; i > 1; --i) {
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;
}
}

Note SortList should really be declared as:

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

~amit
Esteemed Contributor

Hi Amit,

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

you miss something like

/* 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

Honored Contributor

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

... 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.
Highlighted
Acclaimed Contributor

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

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){
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
19
20 second->data = 2;
21 second->next = third;
22
23 third->data = 7;
24 third->next = NULL;
25
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
Acclaimed Contributor

for (i = length; i > 1; --i) {
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;
}
}

Note SortList should really be declared as:

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

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