Message Boards Message Boards

Problem visualising quick sort algorithm

Posted 9 years ago

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)

enter image description here

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)

enter image description here

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.

POSTED BY: Erik Mahieu
8 Replies
Posted 9 years ago

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

POSTED BY: Erik Mahieu

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
POSTED BY: Udo Krause
Posted 9 years ago

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: enter image description here

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

POSTED BY: Erik Mahieu

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

POSTED BY: Todd Rowland

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])]

enter image description here

I suspect there is a problem with the iterator $i$.

POSTED BY: Udo Krause

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

enter image description here

POSTED BY: Udo Krause
Posted 9 years ago

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: n=30 OK

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

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!

Attachments:
POSTED BY: Erik Mahieu

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

enter image description here

that could be responsible for the issue.

POSTED BY: Udo Krause
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract