--- Revision None +++ Revision 323261616138 @@ -0,0 +1,46 @@ +#include +#include + +using namespace std; + +void swap(int &a, int &b) +{ + int temp; + a = b; + b = temp; +} + +int split_array(vector& array, int pivot, int start_index, int end_index) +{ + int left_boundary = start_index; + int right_boundary = end_index; + + while (left_boundary < right_boundary) { + while (pivot < array[right_boundary] && right_boundary > left_boundary) { + right_boundary--; + } + + swap(array[left_boundary], array[right_boundary]); + + while (pivot >= array[left_boundary] && left_boundary < right_boundary) { + left_boundary++; + } + + swap(array[right_boundary], array[left_boundary]); + } + + return left_boundary; +} + +void quicksort(vector& array, int start_index, int end_index) +{ + int pivot = array[start_index]; + int split_point; + + if (end_index > start_index) { + split_point = split_array(array, pivot, start_index, end_index); + array[split_point] = pivot; + quicksort(array, start_index, split_point-1); + quicksort(array, split_point+1, end_index); + } +}