Quick-sort using vector and iterator in STL source codeThis snippet submitted by Jianbao Tao on 2013-03-07. It has been viewed 102659 times.Rating of 7.3 with 555 votes /* * * Quick-sort C++ snippet using vector and iterator in STL. * * By Jianbao Tao @ SSL, UC Berkeley. * * Variable names follow conventions in CLRS. * * Interface: * 1. partition(A, p, r): Return an index q so that each element in A[p:q-1] is less * than A[q] and each element in A[q+1:r] is greater than A[q]. * 2. quickSort(A, p, r): No return. * * Operation flow in *partition*: * 1. Randomly pick an index irandom in [p, r], and swap A[r] with A[irandom]. * 2. Use the new A[r] to be the pivot. * 3. Make a marching index iless so that it points to the last element that is * less than the pivot and A[ismall+1] is greater than the pivot. * 4. Loop over A[p:r-1] with index j. If j > iless and A[j] is less than the pivot, * then swap A[j] and A[iless+1]. * 5. After the loop, swap A[r] and A[iless+1] * 6. Return iless+1 as q, i.e., q is the new position of the pivot. * * Operation flow in *quickSort*. * if p < r: * q = partition(A, p, r); * quickSort(A, p, q-1); * quickSort(A, q+1, r); * * Compile command: * clang++ -stdlib=libc++ -std=c++ -o a.out main.cpp * * Sample output: * -------------- * Original order: * 32 37 16 33 57 81 14 4 73 3 * Sorted order: * 3 4 14 16 32 33 37 57 73 81 * */ #include <iostream> #include <vector> #include <random> #include <ctime> using std::cout; using std::endl; using std::vector; //------------------------------------------------------------------------------ vector<int>::iterator partition(const vector<int> &A, const vector<int>::iterator &p, const vector<int>::iterator &r) { // Get a random element within A[p:r]. auto seed = clock() * clock() * clock(); std::default_random_engine dre(seed); std::uniform_int_distribution<size_t> di(0, r - p); auto random_it = p; random_it = p + di(dre); // Swap values of random_it and r. auto tmp = *random_it; *random_it = *r; *r = tmp; auto pivot = *r; int iless = -1; for(int i = 0; i < r - p; i++) { if(*(p+i) <= pivot) { iless++; if(iless != i) { // Swap *(p+iless) and *(p+i) tmp = *(p+iless); *(p+iless) = *(p+i); *(p+i) = tmp; } } } // Swap *(p+iless+1) and *r *r = *(p+iless+1); *(p+iless+1) = pivot; return p + iless + 1; } //------------------------------------------------------------------------------ void quickSort(const vector<int> &A, const vector<int>::iterator &p, const vector<int>::iterator &r) { if(p < r) { auto q = partition(A, p, r); quickSort(A, p, q-1); quickSort(A, q+1, r); } } //------------------------------------------------------------------------------ int main(int argc, char *argv[]) { // Make a vector to hold a sample array. vector<int> A; // Set up random number generator. auto seed = clock() * clock() * clock(); std::default_random_engine dre(seed); // engine std::uniform_int_distribution<int> di(0, 100); // distribution // Populate A with 10 random number in [0,100]. int num = 10; for(int i = 0; i != num; i++) A.push_back(di(dre)); // Roll the die. // Original order. cout << \"Original order:\" << endl; for(auto it = A.begin(); it != A.end(); it++) cout << *it << \" \"; cout << endl; // Sort. auto p = A.begin(); auto r = A.end() - 1; quickSort(A, p, r); cout << \"Sorted order:\" << endl; for(auto it = A.begin(); it != A.end(); it++) cout << *it << \" \"; cout << endl; return 0; } More C and C++ source code snippets |