This is a discussion on Sorting list performances within the C Programming forums, part of the General Programming Boards category; Originally Posted by iMalc MergeSort is certainly very good for lists, better than quicksort really since that cant tend towards ...
Bucket sort is just a sort where you separate the data into buckets, sort the buckets, and then rebuild a new sorted data structure. One example is here.
Insertion sort on an array has O(n^2) time complexity because the insertion takes linear time even though finding the insertion point can be done in O(log n) time. Insertion sort on a linked list would still have O(n^2) time complexity because while the insertion takes constant time, finding the insertion point takes linear time.Originally Posted by manasij7479
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
Hello again,
I do some tests and i don't undersrand the results, i used the merge sort algorithm described here :
Mergesort For Linked Lists
And compared it to an insertion sort algorithm :
merge sort algorithm :
The insertion sort code :Code:#include <stdio.h> #include <stdlib.h> #include <sys/time.h> #define FALSE 0 #define TRUE 1 struct element { struct element *next, *prev; int i; }; int cmp(struct element *a, struct element *b) { return a->i - b->i; } struct element* listsort(struct element *list) { struct element *p, *q, *e, *tail, *oldhead; int insize, nmerges, psize, qsize, i; /* * Silly special case: if `list' was passed in as NULL, return * NULL immediately. */ if (!list) return NULL; insize = 1; while (1) { p = list; oldhead = list; /* only used for circular linkage */ list = NULL; tail = NULL; nmerges = 0; /* count number of merges we do in this pass */ while (p) { nmerges++; /* there exists a merge to be done */ /* step `insize' places along from p */ q = p; psize = 0; for (i = 0; i < insize; i++) { psize++; q = q->next; if (!q) break; } /* if q hasn't fallen off end, we have two lists to merge */ qsize = insize; /* now we have two lists; merge them */ while (psize > 0 || (qsize > 0 && q)) { if (psize == 0) { /* p is empty; e must come from q. */ e = q; q = q->next; qsize--; } else if (qsize == 0 || !q) { /* q is empty; e must come from p. */ e = p; p = p->next; psize--; } else if (cmp(p,q) <= 0) { /* First element of p is lower (or same); * e must come from p. */ e = p; p = p->next; psize--; } else { /* First element of q is lower; e must come from q. */ e = q; q = q->next; qsize--; } /* add the next element to the merged list */ if (tail) { tail->next = e; } else { list = e; } tail = e; } /* now p has stepped `insize' places along, and q has too */ p = q; } tail->next = NULL; /* If we have done only one merge, we're finished. */ if (nmerges <= 1) /* allow for nmerges==0, the empty list case */ return list; /* Otherwise repeat, merging lists twice the size */ insize *= 2; } } struct element *addnode(int number, struct element *next) { struct element *tnode; tnode = (struct element*)malloc(sizeof(struct element)); if(tnode != NULL) { tnode->i = number; tnode->next = next; } return tnode; } int main(void) { struct element *head; struct element *current; struct element *next; int j; struct timeval tbegin,tend; double texec=0.; // Start timer gettimeofday(&tbegin,NULL); head = NULL; /* insert some numbers into the linked list */ for (j = 1000001; j >= 0; j--) head = addnode(j, head); head = listsort(head); /* print the list */ printf(" before after\n"), j = 1000001; for(current = head; current != NULL; current = current->next) printf("%4d\t%4d\n", j--, current->i); /* free the list */ for(current = head; current != NULL; current = next) next = current->next, free(current); // End timer gettimeofday(&tend,NULL); // Compute execution time texec=((double)(1000*(tend.tv_sec-tbegin.tv_sec)+((tend.tv_usec-tbegin.tv_usec)/1000)))/1000.; printf("Elapsed time = %f\n", texec); /* done... */ return 0; }
and on my machine :Code:#include <stdio.h> #include <stdlib.h> #include <sys/time.h> struct node { int number; struct node *next; struct node *prev; }; struct node *head = NULL; /* insert a node directly at the right place in the linked list */ void insert_node(int value); int main(void) { struct node *current = NULL; struct node *next = NULL; int i = 0; struct timeval tbegin,tend; double texec=0.; // Start timer gettimeofday(&tbegin,NULL); /* insert some numbers into the linked list */ for(i = 100001; i >= 0 ; i--) insert_node(i); /* print the list */ printf(" before after\n"), i = 100001; for(current = head; current != NULL; current = current->next) printf("%4d\t%4d\n", i--, current->number); /* free the list */ for(current = head; current != NULL; current = next) next = current->next, free(current); // End timer gettimeofday(&tend,NULL); // Compute execution time texec=((double)(1000*(tend.tv_sec-tbegin.tv_sec)+((tend.tv_usec-tbegin.tv_usec)/1000)))/1000.; printf("Elapsed time = %f\n", texec); return 0; } void insert_node(int value) { struct node *new_node = NULL; struct node *cur_node = NULL; struct node *last_node = NULL; int found; new_node = (struct node *)malloc(sizeof(struct node )); if(new_node == NULL) { printf("memory problem\n"); } new_node->number = value; /* If the first element */ if (head == NULL) { new_node->next = NULL; new_node->prev = NULL; head = new_node; } else if (new_node->number < head->number) { new_node->next = head; head->prev = new_node; new_node->prev = NULL; head = new_node; } else { cur_node = head; found = 0; while (( cur_node != NULL ) && ( found == 0 )) { if( new_node->number < cur_node->number ) { found = 1; } else { last_node = cur_node; cur_node = cur_node->next; } } if( found == 1 ) { new_node->prev = cur_node->prev; new_node->next = cur_node; cur_node->prev->next = new_node; cur_node->prev = new_node; } else { last_node->next = new_node; new_node->next = NULL; new_node->prev = last_node; } } }
Can someone explain to me this results thanks.Code:./insertion_sort Elapsed time = 0.940000 ./merge_sort Elapsed time = 9.445000
Regards.
When testing merge sort, you insert 1000002 elements into the linked list; when testing with insertion sort, you insert 100002 elements into the linked list.
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)