tests2/25_quicksort.c

   1 #include <stdio.h>
   2
   3 int array[16];
   4
   5 //Swap integer values by array indexes
   6 void swap(int a, int b)
   7 {
   8    int tmp  = array[a];
   9    array[a] = array[b];
  10    array[b] = tmp;
  11 }
  12
  13 //Partition the array into two halves and return the
  14 //index about which the array is partitioned
  15 int partition(int left, int right)
  16 {
  17    int pivotIndex = left;
  18    int pivotValue = array[pivotIndex];
  19    int index = left;
  20    int i;
  21
  22    swap(pivotIndex, right);
  23    for(i = left; i < right; i++)
  24    {
  25       if(array[i] < pivotValue)
  26       {
  27          swap(i, index);
  28          index += 1;
  29       }
  30    }
  31    swap(right, index);
  32
  33    return index;
  34 }
  35
  36 //Quicksort the array
  37 void quicksort(int left, int right)
  38 {
  39    if(left >= right)
  40       return;
  41
  42    int index = partition(left, right);
  43    quicksort(left, index - 1);
  44    quicksort(index + 1, right);
  45 }
  46
  47 int main()
  48 {
  49    int i;
  50
  51    array[0] = 62;
  52    array[1] = 83;
  53    array[2] = 4;
  54    array[3] = 89;
  55    array[4] = 36;
  56    array[5] = 21;
  57    array[6] = 74;
  58    array[7] = 37;
  59    array[8] = 65;
  60    array[9] = 33;
  61    array[10] = 96;
  62    array[11] = 38;
  63    array[12] = 53;
  64    array[13] = 16;
  65    array[14] = 74;
  66    array[15] = 55;
  67
  68    for (i = 0; i < 16; i++)
  69       printf("%d ", array[i]);
  70
  71    printf("\n");
  72
  73    quicksort(0, 15);
  74
  75    for (i = 0; i < 16; i++)
  76       printf("%d ", array[i]);
  77
  78    printf("\n");
  79
  80    return 0;
  81 }
  82
  83 /* vim: set expandtab ts=4 sw=3 sts=3 tw=80 :*/