import random # partition the given section by fixing the anchor def partitionUsingFarRight(A, le, ri): pivotValue = A[ri] # immutable value pivotPos = i = ri while True: if (i <= le): return pivotPos i -= 1 if A[i] > pivotValue: swap(A, pivotPos-1, i) swap(A, pivotPos-1, pivotPos) pivotPos -= 1 def partitionUsingFarLeft(A, le, ri): # optional: swap a random object to the far left swap(A, random.randint(le, ri), le) benchmark=A[le] ret = i = le while True: if i == ri: return ret i +=1 #move pointer if A[i] < benchmark: # 3-step adjustment swap(A, ret+1, i) swap(A, ret+1, ret) ret +=1 def partition(A, le, ri): return partitionUsingFarLeft(A, le,ri) 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,77,6,55,3,11,5,2,88,9,66,22,8,44,1,33,99,7,66])

Above is py, below is c++

#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 partitionUsing1st(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 partitionUsingLast(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]], should but doesn't minimize swaps! 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