C   36

Quicksort

Guest on 1st August 2022 12:41:53 AM

  1. /* Quicksort algorithm */
  2.  
  3. /* Michel Vallieres
  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. }

Raw Paste

Login or Register to edit or fork this paste. It's free.