Sorting algorithms applet
This page displays an applet demonstrating the behavior of various sorting algorithms. To display the tree, click on the bluish button, labeled "Run the sorts".
Depending on your security setting, a yellow bar at the top of the page may appear warning you that running this
applet ("ActiveX controls" it will say) maybe dangerous. In that case, click on this yellow bar and allow the applet to be run. Trust me. In any case,
after you click on the bluish button, the tree will appear in a separate window. You may resize the window, minimize it, in which case
its icon will appear in the bottom tray so you can restore it, or close it altogether. If this last action is taken, you must click on the bluish
button again to restore the applet.
I realize that just about every Data Structures and Algorithms class has a sorting assignment, and there are
probably more programs demonstrating various sorting schemes than there as Viagra adds in your e-mail in-box, but this one
is fairly instructive, and cute. (At least that's what I think.) The applet shows how the sorting algorithms evolve. The array to be
sorted is 800 int's long, and whichever algorithm is used, it stops every 500 comparisons or so to display the current status
of the array. It does not stop exactly at every multiple of 500 comparison, it does it at the next convenient spot. For example, the splits are allowed to be completed in
the quick sort, etc.
It also stops at various other interesting points:
- After a split is done in the quick sort
- After the heap is constructed in the heap sort
- After the array was sorted using one of the increments in the Shell sort
- After two subarrays were merged in the non-recursive merge sort
You can skip the stops by pressing "Finish" button in the bottom panel.
The sorts covered are:
- Insertion sort
- Quick sort, both the classical ("just splitting") as well as one with all the
enhancements:
- Sorting short arrays by hand using insertion sort
- "Median of the three" choice of the pivot
- Fancy split method: "Burning candle at both ends"
- Using stack instead of recursion
- Shell sort with increments 364, 121, 40, 13, 4, 1
(= (3^k - 1)/2, suggested by D. Knuth)
- Non-recursive merge sort
- Heap sort
The only novelty, if any, is the non-recursive merge sort: You successively merge adjacent
fragments. You start with fragments of length 1, and at each iteration you double the size
of the fragment. Push it off the cliff to see how it works. The controls are fairly self-explanatory.
Give it a try. Any comments are always welcomed: drobotv@gmail.com