快排

#include <iostream>
using namespace std;
void swap(int &a, int &b) {
	int tmp = b;
	b = a;
	a = tmp;
}

// end is inclusive
int partition(int arr[], int start, int end) {
	int i = start;
	int idx = start;
	int pivot = arr[end];
	while (i != end) {
		if (arr[i] < pivot) {
			swap(arr[i], arr[idx]); 
			idx++;
		}
		i++;
	}
	swap(arr[idx], arr[end]);
	return idx;
}

void _sort(int arr[], int start, int end) {
	int idx = partition(arr, start, end);
	if (start < idx) {
		_sort(arr, start, idx - 1);
	}
	if (end > idx) {
		_sort(arr, idx+1, end);
	}
}


int main() {
	int arr[] = {-1, 9, 1, 1, 0, -1, 7, 6, 10, -4, 8, 1, 0, -3, -2 , -1};
	int size = 16;
	_sort(arr, 0, size - 1);
	for (int i = 0; i < size; i++) {
		cout << arr[i] << endl;
	}
	return 0;
}