1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
| #include <vector> using namespace std; void dnc(vector<int>& array, int l, int r) { if(l >= r) return; if(l + 1 == r) { if(array[l] > array[r]) swap(array[l], array[r]); return; } int pivot = array[r]; int left = l, right = r - 1; while(left <= right) { while(left <= right and array[left] <= pivot) left++; while(left <= right and array[right] >= pivot) right--; if(left <= right and array[left] > array[right]) { swap(array[left++], array[right--]); } } swap(array[left], array[r]); dnc(array, l, left - 1); dnc(array, left + 1, r); }
vector<int> quickSort(vector<int> array) { dnc(array, 0, array.size() - 1); return array; }
|