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;
}