/* A Fast Bubble sort algorithm for a list. This code has not been tested. */ /* This version sorts the list, instead of swapping the contents of the list. */ 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) { list *h; h = *l1 ; *l1 = *l2 ; *l2 = h ; h = (*l1)->next ; (*l1)->next = (*l2)->next ; (*l2)->next = h ; 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; n_last = first; for (i = first; i < last; i++, l1 = l2, l2 = l2->next) if (comp((*l1)->contents, (*l1)->next->contents) > 0) { list *h; h = *l1 ; *l1 = h->next ; h->next = (*l1)->next ; (*l1)->next = h ; n_last = i; } last = n_last; } }