逻辑引擎

Reinvent wheels, my quick sort implementation, just for fun

Not deeply optimized.
The depth of the recursion is restricted , because the recursion is only performed for the partition with less element. Even under the worst case, the stack depth will still be under control.
Tail recursion is eliminated.

Brief explanation:
[cc lang=”cpp”]
initial state:
p<<< # p=== # | p>>>
p… |
|—————————————–|
……………………………………#

state after choosing the pivot:
p<<< # p=== # | p>>>
|p… |
||—————————————-|
=…………………………………..#

the middle state during partitioning:
p<<< # | p=== # | | p>>> #
| | p… | #
|——–|———|—————-|—–#
<<<<<<<<<==========.................>>>>>>#

the final state after partition:
p<<< # | p=== # | | p>>> #
| | p… #
|—————|—————|———#
<<<<<<<<<<<<<<<<================>>>>>>>>>>#

Then, recurse.
[/cc]
Pointer “p<<<" points to the begining of the "<<<" area in which each element is preceding to the pivot. Pointer "p===" points to the begining of the "===" area in which each element is equivalent to the pivot. Pointer "p>>>” points to the begining of the “>>>” area in which each element is succeeding to the pivot.
Pointer “p…” points to the begining of the “…” area in which each element is unprocessed.

The code:
[cc lang=”cpp”]
template
class QuickSort {
public:
static void sort(Elem pp[], size_t n) {
Elem *pe, *pu, *ps;
// pp:”p<<<", pe:"p===", ps:"p>>>”, pu:”p…”
do {
// recursion exit, use other sort algorithm to process small array
// recommendation: use sorting network algorithm when array size less than 9
if(n < Cutoff) { ShortSort::sort(pp, n);
return;
}

pe = pp;
pu = pp;
ps = pp+n;

// choosing pivot
swap(pe, pivot(pp, n));
pu++;

// partitioning
while(pu < ps) { while((*pe == *pu) && (pu < ps)) ++pu; while((*pe < *pu) && (pu < ps)) { --ps; swap(pu, ps); } while((*pu < *pe) && (pu < ps)) { swap(pe, pu); ++pe; ++pu; } } // recursion only for the partition with less elements if((pe - pp) < (n - (ps - pp))) { sort(pp, pe - pp); n = n - (ps - pp); pp = ps; } else { sort(ps, n - (ps - pp)); n = pe - pp; } // tail recursion elimination } while(true); } private: static Elem *pivot(Elem pp[], size_t n) { if(n < 10) return pp + n/2; else return pp + random(n); // random(n) should return a uniformly distributed random number in [0, n) } }; [/cc]