src/sorting/quicksort.c

   1 /* Quicksort algorithm */
   2
   3 /* Michel Vallieres, 2009
   4  *
   5  *  ref: http://cprogramminglanguage.net/quicksort-algorithm-c-source-code.aspx
   6  *       Numerical Recipes
   7  */
   8
   9 void swap(double *x, double *y)
  10 {
  11         double temp;
  12         temp = *x;
  13         *x = *y;
  14         *y = temp;
  15 }
  16
  17 int choose_pivot(int i, int j)
  18 {
  19         return i + (j - i) / 2;
  20 }
  21
  22 /* sort the list from list[m] to list[n] */
  23 void quicksort(double list[], int m, int n)
  24 {
  25         int i, j, k;
  26         double key;
  27
  28         if (m < n) {
  29                 k = choose_pivot(m, n);
  30                 swap(&list[m], &list[k]);
  31                 key = list[m];
  32
  33                 i = m + 1;
  34                 j = n;
  35                 while (1) {
  36                         while ((i <= n) && (list[i] <= key))
  37                                 i++;
  38                         while ((j >= m) && (list[j] > key))
  39                                 j--;
  40                         if (i >= j)
  41                                 break;
  42                         swap(&list[i], &list[j]);
  43                 }
  44
  45                 // put the pivot back in
  46                 swap(&list[m], &list[j]);
  47
  48                 // recursively sort the sub-lists
  49                 quicksort(list, m, j - 1);
  50                 quicksort(list, j + 1, n);
  51         }
  52 }
  53
  54 void sort(int list_size, double *list)
  55 {
  56         quicksort(list, 0, list_size - 1);
  57 }