quicksort.cpp

// quicksort implementation

#include <vector>


int partition(std::vector<int>& v, int start, int end) {
	int pivot = v[end];
	int current = start;

	for (int i = start; i < end; ++i) {
		if (v[i] < pivot) {
			std::swap(v[current], v[i]);
			++current;
		}
	}
	std::swap(v[current], v[end]);

	return current;
}

void quicksort(std::vector<int>& v, int start, int end) {
	while (start < end) {
		int pivot = partition(v, start, end);
		if (end - pivot > pivot - start) {
			quicksort(v, start, pivot - 1);
			start = pivot + 1;
		} else {
			quicksort(v, pivot + 1, end);
			end = pivot - 1;

		}
	}
}