Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | Download | RSS feed

  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 :*/
  84.