Quick Sort

Here we go.

The quicksort is a recursive algorithm.  On each pass, a part of the list from a left index to a right index is partially sorted in relation to a "pivot" which is put in the right place.  That is, everything to the left of the pivot goes to the left, and everything to the right goes to the right.  How you choose the pivot is pretty arbitrary; somewhere in the middle works fine.  Then you do the same thing on the unsorted parts.

The rest is my work in progress in putting this into Mathematica - speak

But there is a nice animation at the end...

Definitions

list = {};   (* 
      All of these following routines work on this global list *) 
loopCount = 0;
verbose = True;
pictures = False;

swap[a_, b_] := 
        Module[{temp}, 
temp = 
            list[[a]]; 
list[[a]] = 
            list[[b]]; 
list[[b]] = 
            temp; 
If[pictures, 
            BarChart[list]];
];

\(\(\( (*\ 
      partial\ sort\ Global`list\ from\ list[\([left]\)]\ to\ list[\([right]\)], \ 
making\ sure\ that\ list[\([pivot]\)]\ ends\ up\ in\ the\ correct\ place\ *) \)\(
\)\(partialSort[left_, right_, pivot_] := 
        Module[{pivotValue, \ newPivot}, 
pivotValue\  = \ 
            list[\([pivot]\)]; \ \ \  (*\ 
            remember\ pivot\ value\ *) 
If[verbose, 
            Print[\ " pivot value is "\  <> \ 
                ToString[pivotValue]]]; 
swap[pivot, 
            right]; \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  (*\ 
            store\ pivot\ at\ right\ end\ of\ list\ *) 
If[
            verbose, 
            Print[" pivot moved to right  "\  <> \ 
                ToString[list]]]; 
newPivot\  = \ 
            left; \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  (*\ tentative\ new\ pivot\ position\ *) 
Do[
\(loopCount++\); 
If[\ 
              list[\([k]\)] ≤ 
                pivotValue, 
\ \ \ \ \ \  (*\ then\ *) \ 
              swap[k, newPivot]; \ \ \(newPivot++\); \ 
If[
                verbose, 
                Print[\ "k=" <> ToString[k] <> ", newPivot = " <> 
                    ToString[newPivot], ", list=" <> 
                    ToString[
                      list]]]
]
, {k, 
              left, right - 1}
]; 
swap[
            right, newPivot]; 
Return[
            newPivot];
];\)\)\)

verbose = True;
list = {20, 30, 40, 100, 12, 14, 15};
finalPivot  =  partialSort[1, 7, 1];
{finalPivot,  list}

quicksortRecur[left_, right_] := 
        Module[{pivot}, 
If[
              right > left, 
pivot  =  
                middle[left, right]; 
newPivot  =  
                partialSort[left,  right,  
                  pivot]; 
quicksortRecur[left,  
                newPivot - 1]; 
quicksortRecur[
                newPivot + 1, 
                right];
];
];

quicksort[theList_] := 
        Module[{}, 
loopCount = 
            0; 
list  =  
            theList; 
quicksortRecur[1, 
            Length[list]]; 
Return[
            list];
];

middle[a_, b_] := 
        Module[{}, 
Return[
              Floor[(a + b)/2]];
];

Scratch

quicksort[{3, 10, 20, 7, 10, 2}]

middle[10, 20]

verbose = False;

    quicksort[Table[Random[Integer, {1, 200}], {20}]]

loopCount

results = {};

    Do[
n = (10^logn); 
verbose = 
        False; 
quicksort[
        Table[Random[Integer, {1, 10 n}], {n}]]; 
AppendTo[
        results, {n, 
          loopCount}]; 
Print[" n, loopCount = "  <>  
          ToString[{n, loopCount}]]
, {logn, 1, 
        5}]

Length[list]

Short[list]

list

?barPlot

?*bar*

?*Bar*

<< Graphics`Graphics`;

BarChart[list]

verbose = False;
quicksort[Table[Random[Integer, {1, 200}], {20}]]

loopCount

pictures = True

Do this, then collapse all the pictures, then double click to animate it.

quicksort[Table[Random[Integer, {1, 200}], {10}]]