Problem visualising quick sort algorithm

Questions
, , , ,
1

Quicksort is a popular sorting algorithm that recursively divides a list into two sublists: the parts of list smaller than and the parts larger than (or equal to) a chosen pivot. The pivot can be any member of the list or any number (mean, median,…) within the range of the list.
My goal is to visualise this algorithm by means of a live bar chart representing the list being sorted.

The idea is to do this by means of Animate or a Manipulate with Trigger or Animator as a control.
However, already in the simple case of dividing the list in two parts, I encounter problems: The example is very simple: I use an unsorted list of 30 or 50 random numbers between 1 and 100 and use as pivot either 15 or 50.
The following Manipulate is supposed to animate the progressive division of the list in parts that are smaller and parst larger than the pivot:

Manipulate[Module[{pivot, sample},
  pivot = n/2; sample = lst[[i]];
  If[sample < pivot,
   PrependTo[lst, sample]; lst = Delete[lst, i + 1]]; 
  BarChart[lst, GridLines -> {None, {pivot}}, BarSpacing -> 1]],
 {{i, 1}, 1, n, 1, Trigger, DisplayAllSteps -> True, 
  AnimationRunning -> False, AnimationRepetitions -> 1},
 {{n, 30}, None},
 Initialization :> (lst = RandomSample[Range[n], n])]

Now with n=30 (or any number smaller than 30), this works fine as one can see by running the Manipulate or see from this end result: The chart is divided into 2 sets of bars either smaller than or larger than the pivot (15)

8484nis30.png
8484nis30.png540×330 3.01 KB

But, with n=50 (or any number >35), this does not work right as seen from this end result: The division is not correct since some of the smaller bars are in the part with the supposedly larger bars (pivot is 25)

7113nis50.png
7113nis50.png540×330 2.98 KB

This may not be the right way to do this but it should work?!
I would appreciate help in finding out what I am doing wrong? or indication of a better procedure to visualise this sorting algorithm.

2

You won’t believe it, but 30 is hard coded

6519comm582897.PNG
6519comm582897.PNG503×237 6.93 KB

that could be responsible for the issue.

3

Thanks for your observation, Udo. I am aware of the n=3 being hard coded but (maybe I explained it wrongly?) my problem is that when I (again hard coded) change to {{n,50},None}, I get no longer a separation between the bars larger than and smaller than the pivot.
As can be seen from this gif with n=30 first where the sort is ok and the bars are neatly separated:

nis30.gif

and now with n=50 where I have a problem as you can see:

nis50.gif

I realise that a Manipulate/Trigger combination may be the wrong way to do this but there must be something I am missing here and I want to understand. Maybe you can help with your expertise.
By the way, love yr website zahlenteppich!
[1]: http://community.wolfram.com//c/portal/getImageAttachment?filename=nis30.gif&userId=68637
[2]: http://community.wolfram.com//c/portal/getImageAttachment?filename=nis50.gif&userId=68637

4

It seems that also n=30 is not immune against failure

5247comm582897.PNG
5247comm582897.PNG630×551 8.18 KB

5

Start the manipulation with an ordered set to see that only the first two entries become interchanged forever: i does not escalate beyond 2 …

Manipulate[Module[{pivot, sample},
      pivot = n/2; sample = lst[[i]];
      If[sample < pivot,
       PrependTo[lst, sample]; lst = Delete[lst, i + 1]]; 
      BarChart[lst, GridLines -> {None, {pivot}}, BarSpacing -> 1]],
     Row[{Control[{{i, 1}, 1, n, 1, Trigger, DisplayAllSteps -> True, 
         AnimationRunning -> False, AnimationRepetitions -> 1}], 
       Dynamic@i}],
     {{n, 30}, None},

 Initialization :> (lst =(* RandomSample[Range[n],n]) *) Range[n]) ]

The iteration took place if I resized the notebook!

Manipulate[With[{pivot = n/2, cut = n/2, sample = lst[[i]]},
      If[sample < pivot,
       lst = Join[RotateRight[Take[lst, i]], Take[lst, i - n]]
      ];
      BarChart[lst, GridLines -> {None, {pivot}}, BarSpacing -> 1]],
     Row[{Control[{{i, 1}, 1, n, 1, Trigger, DisplayAllSteps -> True, 
         AnimationRunning -> False, AnimationRepetitions -> 1}], 
       Dynamic@i}],
     {{n, 50}, None},
     Initialization :> (lst =(* RandomSample[Range[n],n] *) Range[n])]

comm582897_2.PNG
comm582897_2.PNG724×535 8.86 KB

I suspect there is a problem with the iterator i.

6

One approach is to use a static visualization of the algorithm. Besides helping you debug what is happening, a static one might be preferable to what you are making in the first place. The simplest such is to use ArrayPlot on the evolution history {init, step 1, step 2, …, final step}.

Here is a link to a bunch of different sorting visualizations from the 2004 NKS conference http://www.wolframscience.com/conference/2004/presentations/material/jsmith-randscape.pdf

7

Thank you Udo, thank you Todd. With your observations in mind, I started to realise that:

  1. there is a problem with all values of n but less so with smaller values
  2. there is indeed something with the iterator i. I started noticing that there is a discrepancy between the evaluation speed of the If[] and the subsequent BarChart[]. Furthermore, using (the faster?) ArrayChart gives less of a problem. I tried several things such as SynchronousUpdating etc but the only thing that worked is to set the animation refresh rate with AnimationRate->1 or <1. Higher than 1 or Automatic does not give (always) a correct sort.

Here is a gif of a working example with the added AnimationRate->1:

sorttest-2.gif

It works but I do not completely understand why. It must have something to do with Evaluation speed or evaluation order…?

8

This works

With[{nGiven = 63},
  Manipulate[Dynamic[With[{p0 = n/2, p1 = 2 n - 1, sample = lst[[i]]},
    lst = If[sample < p0,
      lst = Join[RotateRight[Take[lst, i]], Take[lst, i - n]],
      lst
    ];
    Graphics[{Polygon[
        Transpose[{Flatten[{#, #}& /@ Range[0, p1]], Flatten[{0, #, #, 0}& /@ lst]}]
      ], 
      {Blue, Line[{{0, p0}, {p1, p0}}]}, Line[{{0, 0}, {p1, 0}}], 
      {Red, Disk[{2 i - 3/2, -1}, 1]}}, 
      Frame -> True]
    ], TrackedSymbols -> {i}],
    {{i, 2, ""}, 2, n, 1, ControlType -> Trigger, DisplayAllSteps -> True, AnimationRunning -> False, 
      AnimationRepetitions -> 1, AnimationRate -> 7},
    {{n, nGiven}, None},
    Initialization :> (lst = RandomSample[Range[n], n]),
    FrameLabel -> StringJoin["n = ", ToString[nGiven]]
  ]
]
  • took advantage of an answer to Trigger autorunning when not supposed to, thanks to Mr. Wizard
  • key is the usage of TrackedSymbols within Dynamic with iterator i only
  • if TrackedSymbols -> {i, lst} is used, irregularities show up
  • one may wonder why lst keeps tracked: possibly because of the TrackedSymbols -> All default option of Manipulate
  • possibly you can get rid of the Polygon construction invented because a slow BarChart was suspected as problem host
  • capable to run with high performance AnimationRate such as 7 per second
  • hitting the Pause icon for the second time does not continue the animation
  • hitting the Reset icon does not select another random sample to sort out
9

This does it! You are way ahead of me, Udo. Up to me now to do some further experimenting.