Group Abstract

Message Boards

WOLFRAM COMMUNITY

13K Views

8 Replies

5 Total Likes

View groups...

Follow this post

Share this post:

GROUPS:

Computer Science Mathematics Mathematica Dynamic Interactivity Modeling Tuning and Debugging

Problem visualising quick sort algorithm

Erik Mahieu

Posted 10 years ago

POSTED BY: Erik Mahieu

8 Replies

Sort By:

Erik Mahieu

Posted 10 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

Udo Krause

Udo Krause, NOrganization

Posted 10 years ago

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

Erik Mahieu

Posted 10 years ago

POSTED BY: Erik Mahieu

Todd Rowland

Todd Rowland, Zeta Cubed

Posted 10 years ago

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

Udo Krause

Udo Krause, NOrganization

Posted 10 years ago

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])] I suspect there is a problem with the iterator $i$.

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