qsort.cc

#include <iostream>
#include <vector>

void PrintArray(std::vector<int>& arr) {
  int len = arr.size();
  std::cout << "[";
  for (int i = 0; i < len; ++i) {
    std::cout << arr[i];
    if (i != len - 1) {
      std::cout << ", ";
    }
  }
  std::cout << "]" << std::endl;
}

int Partition(std::vector<int>& arr, int low, int high) {
  int pivot = arr[high];
  int i = low;
  for (int j = low; j < high; ++j) {
    if (arr[j] < pivot) {
      std::swap(arr[i++], arr[j]);
    }
  }
  std::swap(arr[i], arr[high]);
  return i;
}

void QSortInternal(std::vector<int>& arr, int low, int high) {
  if (low < high) {
    int pos = Partition(arr, low, high);
    QSortInternal(arr, low, pos - 1);
    QSortInternal(arr, pos + 1, high);
  }
}

void QSort(std::vector<int>& arr) {
  int len = arr.size();
  if (len <= 1) return;
  QSortInternal(arr, 0, len -  1);
}

int main(int argc, const char* argv[]) {
  std::vector<int> arr{3, 1, 6, 5, 9, 0, 8, 2, 4, 7};
  PrintArray(arr);
  QSort(arr);
  PrintArray(arr);
  return 0;
}