quick_sort.cc

gistfile1.txt

#include "sort.h"
#include "utils.h"

int Partition(int *a, int l, int r);

void Sort(int *a, int l, int r) {
  if (r - l > 1) {
    int m = Partition(a, l, r);
    Sort(a, l, m);
    Sort(a, m + 1, r);
  }
}

int Partition(int *a, int l, int r) {
  r--;
  int pivot = a[r];
  int i = l - 1;
  for (int j = l; j < r; j++)
    if (a[j] <=	 pivot)
	  swap(a[++i], a[j]);
  swap(a[++i], a[r]);
  return i;
}