1  #include <iostream>
  2  using namespace std;
  3  
  4  // Function prototypes
  5  void quickSort(int list[], int arraySize);
  6  void quickSort(int list[], int first, int last);
  7  int partition(int list[], int first, int last);
  8  
  9  void quickSort(int list[], int arraySize)
 10  {
 11    quickSort(list, 0, arraySize - 1);
 12  }
 13  
 14  void quickSort(int list[], int first, int last)
 15  {
 16    if (last > first)
 17    {
 18      int pivotIndex = partition(list, first, last);
 19      quickSort(list, first, pivotIndex - 1);
 20      quickSort(list, pivotIndex + 1, last);
 21    }
 22  }
 23  
 24  // Partition the array list[first..last] 
 25  int partition(int list[], int first, int last)
 26  {
 27    int pivot = list[first]; // Choose the first element as the pivot
 28    int low = first + 1; // Index for forward search
 29    int high = last; // Index for backward search
 30  
 31    while (high > low)
 32    {
 33      // Search forward from left
 34      while (low <= high && list[low] <= pivot)
 35        low++;
 36  
 37      // Search backward from right
 38      while (low <= high && list[high] > pivot)
 39        high--;
 40  
 41      // Swap two elements in the list
 42      if (high > low)
 43      {
 44        int temp = list[high];
 45        list[high] = list[low];
 46        list[low] = temp;
 47      }
 48    }
 49  
 50    while (high > first && list[high] >= pivot)
 51      high--;
 52  
 53    // Swap pivot with list[high]
 54    if (pivot > list[high])
 55    {
 56      list[first] = list[high];
 57      list[high] = pivot;
 58      return high;
 59    }
 60    else
 61    {
 62      return first;
 63    }
 64  }
 65  
 66  int main()
 67  {
 68    const int SIZE = 9;
 69    int list[] = {1, 7, 3, 4, 9, 3, 3, 1, 2};
 70    quickSort(list, SIZE);
 71    for (int i = 0; i < SIZE; i++)
 72      cout << list[i] << " ";
 73  
 74    return 0;
 75  }