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