# partition the given section by fixing the anchor def partition(A, le, ri): pivot = A[ri] # immutable pivotPos = i = ri while i > le: i -= 1 if A[i] <= pivot: continue swap(A, pivotPos-1, i) swap(A, pivotPos-1, pivotPos) #print 'after swap ...', A[le:ri+1] pivotPos -= 1 return pivotPos def recurse(A, le, ri): if le>=ri: return print 'entering partition()...', print(A[le:ri+1]), ' pivotVal =', A[ri] anchor = partition(A, le, ri) print '...after partition() ', print(A[le:ri+1]) recurse(A, le, anchor-1) recurse(A, anchor+1, ri) def swap(A, x,y): tmp = A[x] A[x] = A[y] A[y] = tmp def qsort(A): recurse(A, 0, len(A)-1) print(A) qsort([222,55,33,11,66,8,144,99,7,66])

Above is py, below is c++

</pre> #include <iostream> #include <vector> std::vector<int> A{77, 11, 66,22,33,99,44,88, 77, 55, 0}; int const size = A.size(); void dump(int l=0, int r=size-1) { for (int i = l; i <= r; ++i) std::cout << A[i] << ' '; std::cout <<std::endl; } template <typename T> void swap(int pos1, int pos2) { if (A[pos1] == A[pos2]) return; T tmp = A[pos1]; A[pos1] = A[pos2]; A[pos2] = tmp; } /*partition the region [l,r] such that all elements smaller than pivotValue are on the left of pivotPosition */ template <typename T> int partitionUsing1stInefficient(int l, int r) { T const pivotVal = A[l]; int pivotPos = l; for (int i = l+ 1; i <= r; ++i) { if (A[i] >= pivotVal) continue; swap<int>(pivotPos + 1, i); swap<int>(pivotPos + 1, pivotPos); ++pivotPos; } return pivotPos; } template <typename T> int partitionUsingLastInefficient(int l, int r) { T const pivotVal = A[r]; int pivotPos = r; for (int i = r - 1; i >= l; --i) { if (A[i] <= pivotVal) continue; swap<int>(pivotPos - 1, i); swap<int>(pivotPos - 1, pivotPos); --pivotPos; } return pivotPos; } /*based on [[Algorithms unlocked]] Lime zone -- items smaller than pivot value Red zone -- items bigger than pivot value Ugly zone -- items yet to be checked */ template <typename T> int partitionMinimalSwap(int le, int ri) { T const pivotVal = A[ri]; // two boundaries exist between zones int redStart = le; // we start with redStart == uglyStart == l, which means item at le is Unknown for (int uglyStart = le; uglyStart < ri; ++uglyStart) { if (A[uglyStart] < pivotVal) { swap<int>(uglyStart, redStart); redStart++; } } swap<int>(ri, redStart); return redStart; } template <typename T> void recurse(int l, int r) { if (l >= r) return; // recursion exit condition int const anchor = partitionMinimalSwap<T>(l, r); recurse<T>(l, anchor-1); recurse<T>(anchor+1, r); } int main() { recurse<int>(0, size-1); dump(); return 0; }

Advertisements