tests/tmp_tests/Frontend/quicksort.c

   1
   2 #define SIZE 5
   3
   4 void swap (int a[], int i, int j) {
   5   int t;
   6   t = a[i] ; a[i] = a[j] ; a[j] = t;
   7 }
   8
   9 int partition (int a[], int l, int r) {
  10    int pivot, i, j;
  11    pivot = a[l];
  12    i = l; j = r+1;
  13
  14    while (1) {
  15      while (i <= r && a[i] <= pivot) ++i;
  16      do --j; while (a[j] > pivot);
  17      if (i >= j) break;
  18      swap(a, i, j);
  19    }
  20    swap(a, l, j);
  21    return j;
  22 }
  23
  24 void quicksort (int a[], int l, int r) {
  25    int j;
  26
  27    if (l < r) {
  28      j = partition(a, l, r);
  29      quicksort(a, l, j-1);
  30      quicksort(a, j+1, r);
  31    }
  32 }
  33
  34 void print_tab (int tab[], int size) {
  35   int i;
  36
  37   for (i = 0 ; i < size ; i++) {
  38     print_sint(tab[i]);
  39     space();
  40   }
  41   newline();
  42 }
  43
  44 int is_sorted (int tab[], int size) {
  45   int i, res = 1;
  46
  47   for (i = 0 ; i < size-1 ; i++) res = res && (tab[i] <= tab[i+1]);
  48
  49   return res;
  50 }
  51
  52 int main () {
  53   int tab[SIZE] = {26, -21, 43, -62, 8};
  54
  55   quicksort(tab, 0, SIZE-1);
  56   print_tab(tab, SIZE);
  57   print_sint(is_sorted(tab, SIZE));
  58   newline();
  59
  60   return (is_sorted(tab, SIZE));
  61 }