QuikSort.cpp

#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
	std::vector<int> sort(std::vector<int> v) {
		std::vector<int> result(v);
		quickSort(result, 0, result.size()-1);
		return result;
	}

private:
	void quickSort(std::vector<int> &v, int left, int right) {
		if (left < right) {
			int p = partition(v, left, right);
			quickSort(v, left, p-1);
			quickSort(v, p+1, right);
		}
	}

	int partition(std::vector<int> &v, int left, int right) {
		int pivot = v[right];
		int result = left;
		for (int i=left; i<right; i++) {
			if (v[i] <= pivot) {
				swap(v[result], v[i]);
				result++;
			}
		}
		swap(v[result], v[right]);
		return result;
	}

	void swap(int &a, int &b) {
		if (a != b) {
			a = a+b;
			b = a-b;
			a = a-b;
		}
	}
};

int main(int argc, char *argv[]) {
	Solution sol;
	int int_arrays[] = {2,8,7,1,3,5,6,4};
	vector<int> v(int_arrays, int_arrays+sizeof(int_arrays)/sizeof(int));
	std::vector<int> result = sol.sort(v);
	for(int i=0; i<result.size(); i++) {
		cout << result[i] << " ";
	}
	cout << endl;
}