# How can I collect data for visualization of quick sort?

I know how to implement quick sort in Mathematica. But I don't know how to get the temp data for visualization, because I used recursion. I want the effect similar to this: qsort[{}] = {};
qsort[{x_, xs___}] := Join[qsort@Select[{xs}, # <= x &], {x}, qsort@Select[{xs}, # > x &]];
qsort@RandomSample@Range@30

• You can get the temp data by Sow and Reap – ssch Jan 25 '13 at 10:34
• You can also use Trace. Have a look at this answer, where I was showing how to trace the execution of merge sort implementation (not quick sort, but also recursive). – Leonid Shifrin Jan 25 '13 at 12:55
• – Szabolcs Jan 28 '13 at 2:42
• @Szabolcs Unbelivable! – Dr. belisarius May 6 '14 at 16:47

## 1 Answer

n = 100; (*number of points*)
s = RandomSample@Range@n; (*the initial set*)
(*some aux functions*)
head[{x_, xs___}] := Select[{xs}, # <= x &];
tail[{x_, xs___}] := Select[{xs}, # > x &];

(*qsort function modified for sowing the information needed*)
qsort[{}] = {};
qsort[l : {x_, ___}] := Module[{lh, lt}, (Sow@{l, lh = head@l, x, lt = tail@l};
Join[qsort@lh, {x}, qsort@lt])];

(*Perform the sort and extract the transformation rules for each step*)
t0 = (Reap@qsort@s) [[2, 1]] /. {l_, h_, x_, t_} :> Thread[l -> Flatten@{h, x, t}];
(*Delete unproductive transformations for speeding up the animation*)
t0 = t0 //. HoldPattern[x_ -> x_] | {} -> Sequence[];
(*Apply the transformations and get the list of succesive states*)
seqs = FoldList[#1 /. #2 &, s, t0];

(*Calculate the elements' paths to highlight them at each step*)
hL = ArrayPad[Unitize@Differences@seqs Rest@seqs, {{0, 1}, {0, 0}}] /. 0 -> Undefined;

(*Plot it*)
pstyle = PlotStyle -> Directive[Red, PointSize@Medium];
ListAnimate[ j = Show[ListPlot[#[], ImageSize -> 500],
ListPlot[#[], pstyle]] & /@ Transpose[{seqs, hL}]]

Export["c://test.gif", j, "DisplayDurations" -> 1] 