1 #include <iostream> 2 #include <vector> 3 4 #define VECTOR_ELEMENT_LIMIT 20 5 6 void vector_random_populate(std::vector<int>& v) { 7 srand (time(NULL)); 8 for(size_t i = 0; i < v.size(); ++i) 9 v[i] = (int)(rand() % VECTOR_ELEMENT_LIMIT); 10 } 11 12 void vector_print(const std::vector<int> v) { 13 std::cout << "["; 14 for(size_t i = 0; i < v.size(); ++i) { 15 std::cout << v[i] << ((v.size() == i+1) ? "" : ", "); 16 } 17 std::cout << "]\n"; 18 } 19 20 void swap(int *a, int *b) 21 { 22 int tmp; 23 tmp = (*a); 24 (*a) = (*b); 25 (*b) = tmp; 26 } 27 28 void quick_sort_partition(std::vector<int> &v, int low, int &middle, int high) { 29 int i, j, pivot; 30 pivot = high; 31 32 for(i = j = low; i < high; i++) 33 if(v[i] < v[pivot]) 34 swap(&v[j++], &v[i]); 35 36 swap(&v[j], &v[pivot]); 37 middle = j; 38 } 39 40 void quick_sort(std::vector<int>& v, int low, int high) { 41 int pivot; 42 43 if ((high - low) > 0) { 44 quick_sort_partition(v, low, pivot, high); 45 quick_sort(v, low, pivot - 1); 46 quick_sort(v, pivot + 1, high); 47 } 48 } 49 50 int main (void) { 51 std::vector<int> v(10); 52 vector_random_populate(v); 53 vector_print(v); 54 quick_sort(v, 0, v.size()); 55 vector_print(v); 56 return 0; 57 }
