image provider

Sort Visualizer

home page up jump to foot of page Google search web for more information on this topic Pinterest pin button
©1996-2017 Roedy Green of Canadian Mind Products

Disclaimer

This essay does not describe an existing computer program, just one that should exist. This essay is about a suggested student project in Java programming. This essay gives a rough overview of how it might work. I have no source, object, specifications, file layouts or anything else useful to implementing this project. Everything I have prepared to help you is right here.

This project outline is not like the artificial, tidy little problems you are spoon-fed in school, when all the facts you need are included, nothing extraneous is mentioned, the answer is fully specified, along with hints to nudge you toward a single expected canonical solution. This project is much more like the real world of messy problems where it is up to you to fully the define the end point, or a series of ever more difficult versions of this project and research the information yourself to solve them.

Everything I have to say to help you with this project is written below. I am not prepared to help you implement it; or give you any additional materials. I have too many other projects of my own.

Though I am a programmer by profession, I don’t do people’s homework for them. That just robs them of an education.

You have my full permission to implement this project in any way you please and to keep all the profits from your endeavour.

Please do not email me about this project without reading the disclaimer above.

This is a tool for teaching people how various sorts work. It lets you watch them work. It also lets you see how well they work on already sorted data, or data that is sorted in reverse order. People who like watching Norton SpeedDisk will enjoy the hypnotic effect of this program.

You start with an array 400 elements long. You initialise it like this:

for ( int i=0; i<400; i++ )
   {
   theArray[i] = i;
   }
Then you scramble the array. You can do this by generating random pairs of integers and exchanging those two array elements. Do this 10,000 times. See Random Numbers in the Java & Internet Glossary to see how to generate random numbers 0..399. See also Collections.shuffle.

Then you display the array in a 400 × 400 square grid of pixels. If array[4] == 10 you plot a dot at x=4 y=10.

There is source for RadixSort, HeapSort, QuickSort and ShellSort available to download.

You insert a call to your drawing routine inside the sort. The sort must call it every time it moves an element of the array. You might also insert it more easily on every compare. Some sorts may make a copy of the array or in some other way challenge you with a way to extract the needed data to plot. You might even have to understand how the sort works!

Then you start your sort. Now you can sit back and watch the points skitter about like tiny soldiers racing into order in a straight diagonal line as the sort progresses.

If it turns out you need speed, instead of repainting the entire grid each time, compare the old and new array and notice the differences. Then just adjust just the pixels that need it.

Make it an Applet so that people can play with it on the web. They should be able to choose which sort algorithm to use. You may need to insert a variable delay into your plot routine if the sort is too fast too see.

You might write some el-cheapo sorts that don’t work well on a large number of elements to demonstrate why they should not be used. Write an insertion sort (one at a time it inserts elements, sliding all those above to make room) or a bubble sort that percolates the biggest element to the end via a series of exchanges. On each pass it ignores the previous biggest elements and finds the next biggest. Write a scanner sort that finds the smallest element then copies it to another list and either marks the original void, or slides elements above it down. Then it repeats.

If that was not enough challenge, add this wrinkle. For people with big screens allow the size of the grid to be as big as the screen, or maybe even bigger and allow them to pan around on it. You might even display your scrambling process to give the users something to watch while you scramble the data.

Play with colour, encoding extra information into the dots using hue, saturation and brightness. See HSB (Hue Saturation Brightness) in the Java & Internet Glossary. You might use warmness of the colour to encode how close the dot is to its home position, or how frequently or how recently it has been moved.

Another thing your harness could do it experimentally test if sorts are stable. You can’t prove a sort is stable that way, but you can prove it is unstable. By stable I mean does not disturb existing order in the event of a tie in keys. You can turn an unstable sort into a stable one by using position in the array as a minor key.

This page is posted
on the web at:

 http://mindprod.com/project/sortvis.html

Optional Replicator mirror
of mindprod.com
on local hard disk J:

 J:\mindprod\project\sortvis.html
Canadian Mind Products
Please the feedback from other visitors, or your own feedback about the site.
Contact Roedy. Please feel free to link to this page without explicit permission.

IP:[65.110.21.43]
Your face IP:[18.225.255.134]
You are visitor number