This menu permits you to select what sorting algorithm will be
employed. As of this writing, the following algorithms are
implemented in this program:by Michael J. Fromberger, Copyright © 2003 All Rights Reserved.
The Sorting Laboratory is a program to help you visualize the behaviour of various sorting algorithms. It simulates the behaviour of the selected algorithm, and keeps track of how many times the algorithm compares two values (comparisons) and how many times the algorithm moves a data value (moves). In this way, you can get a feel for the time complexity of the various algorithms.
The following controls are available:
This menu permits you to select what sorting algorithm will be
employed. As of this writing, the following algorithms are
implemented in this program:
The difference between the (R) and (M3) variations of QuickSort is in how the pivot element is chosen for partitioning. In QuickSort (M3), the "median of three" algorithm is used. With QuickSort (R), a pivot is chosen at random. The QuickSort (M3) Hybrid algorithm uses median-of-three partitioning, but on ranges containing twenty elements or fewer, the Insertion Sort algorithm is used instead of continuing the recursive partitioning. This generally makes the algorithm perform a little faster (fewer comparisons, but more data movement).
This slider controls how fast the algorithm will proceed when you
click the Run button (see
below). At "Crawl", there is about a half-second pause after each
step; at "Hyper", the pause is about 5 milliseconds. You can adjust
this value while the sort is running.
This slider indirectly lets you control how many points are to be
sorted. You do this by setting how large they are, on a scale from 1
to 30 pixels. The program includes as many points as will fit in the
visible area of the program's window.
This menu lets you control how the data are initially ordered before
you begin sorting them. By default, this is set to "Random", which
causes the data to be shuffled pseudo-randomly. You can also choose
"Ascending" or "Descending" (as these orderings are corner cases for
certain algorithms such as Insertion Sort and Quicksort).
These buttons control the execution of the algorithm. Clicking the
Step button causes the algorithm to take a single
step (usually, a single comparison operation). Clicking the
Run button causes it to take steps automatically,
until either the data set is completely sorted, or until you click
Run a second time.
The Reset button causes the sorting process to "start over", clearing the number of comparisons and moves to zero and restoring the elements to their original unsorted positions.
The Reset button restores the data to the same order each time it is selected. To change the ordering, select the Reseed button, which will cause a new random permutation to be chosen. Note that the initial ordering also depends upon how many data points there are, so if you change the size of the points, choosing Reset will choose a new permutation based upon the same seed.
This diagram illustrates the main window of the sorting laboratory.
Each datum is represented by a black dot or vertical bar. The
horizontal (X) axis represents the position of the element,
while the vertical (Y) axis represents its value. Each value
in the data set is unique, so it has a unique destination in the final
ordering.
In order that you can see what is happening while an algorithm is being simulated, the sorting laboratory paints the points representing the last values that were compared in blue, while the last positions that were moved are painted red. A point that was both compared and moved recently is painted half-red and half-blue.
In addition, a horizontal line is drawn through each blue point, and a vertical line is drawn through each red point. The vertical lines give you a sense of where the algorithm's "attention" is focused within the data being sorted.
While an sort is in progress, you can get information about how many
comparisons and data moves have been performed from the status readout
on the bottom right of the screen. The Comparisons
field tells you how many times two elements have been compared. The
Moves field tells you how many times a data element
has been moved or copied (note that a "swap" operation, exchanging two
distinct elements, counts as two moves). And, finally, the
Elements field tells you how many data points are
currently being displayed and sorted.
Last updated: 19-Dec-2007 at 01:52 AM