/* A Fast Bubble sort algorithm for a list. This code has not been tested. */ /* assumes */ typedef struct list_T { struct list_T *next; void *contents; } list_t; void bsort(list, nr, comp) list_t *list; int nr; /* int (*comp)(const void *, const void *); */ int (*comp)(); { int last, first; int d = nr / 2 + 1; /* Quick bubble sort: */ while (d > 1) { int nr_swapped = 0, i; list_t *l1 = list, *l2 = list; for (i = 0; i < d; i++) l2 = l2->next; last = nr - d; for (i = 0; i < last; i++, l1 = l1->next, l2 = l2->next) if (comp(l1->contents, l2->contents) > 0) { swap(l1->contents, l2->contents); nr_swapped++; } if (nr_swapped == 0) d = d / 3; else { double nd = (double)nr_swapped/(double)last; nd = (1 + sqrt(nd))/2; d = (int)( d * nd ); } if (d < 1) d = 1; } /* Normale bubble-sort algorithme: */ first = 0; last = nr - 1; while (first < last) { int n_first, n_last, i; list_t *l1 = list, *l2 = l1->next; n_last = first; for (i = first; i < last; i++, l1 = l2, l2 = l2->next) if (comp(l1->contents, l2->contents) > 0) { swap(l1->contents, l2->contents); n_last = i; } last = n_last; } }