\f0\b0 is an educational tool to help you learn about sorting algorithms. There are many neat ways to go about sorting a data set, and this little program illustrates six of the standard algorithms. Each sort is graphically animated, so you can watch it in progress. Capitalizing on the magic of Mach threads, the program can run the sorts against one another in parallel to show you a reasonably fair comparison of the efficiency of the sorts. By adjusting the sort parameters, you can explore how the efficiency of each algorithm is related to the size and type of data set used. Intrigued already? Read on.\
The
\b Sort Parameters
\b0 panel has the controls to set up a sort. The
\b Data Set
\b0 box allows you to specify the size of the data set and what percentage of the data is already in sorted order. If you ask for 0% percent sorted data, all elements of the data set will be randomly generated. A 42% sorted data set would have 58% random elements inserted into 42% pre-sorted data. A 100% sorted set is all already in sorted order - try it out and find out which sorts are smart enough to take advantage of data already sorted and which ones aren't! \
The
\b Algorithms
\b0 list indicates which sorts you would like to run. Simply check the boxes for the sorts you want to see. The descriptions of the different algorithms are below.\
You also have the choice of running the sorts in
\b Parallel
\b0 or in
\b Series
\b0 . In series you can watch each algorithm individually, while in parallel you can watch the sorts compete.\
By changing the
\b Value of Sorting Operations
\b0 , you adjust the "tick" cost charged to a sort for the basic operations. You can explore how the sorts perform differently with various weights assigned to the operations. For example, if you were sorting a data set of large records by an integer field, compares would be cheap and moves would be expensive. (Selection sort excels in this situation). Changing the tick costs can also simulate the effects of changing the hardware or the implementation language.\
When you have configured the sort to your preferences, click on the "
\b Go!
\b0 " button to make it all happen. Once the sort has begun, the Go button changes to the "
\b Stop
\b0 " button which you can use to cancel the sorts in progress. \
The algorithms will animate their progress as they sort. The
\b Animate Compares
\b0 switch controls whether the sorts will also highlight in gray the two elements being compared. This provides feedback on the comparisons the algorithms are making. The
\b Animation Speed Slider
\b0 allows you to slow the progress of the sort. You can follow the sorts more carefully in slow motion. \
When a sort finishes, it will fade out and display its running time statistics. The statistics indicate how many compares, moves, and function calls the algorithm used to sort the data, as well as its final tick count.\
\f1\fs48 The Algorithms
\f0\fs28 \
\b Bubble Sort
\b0 \
A classic sort, although not a particularly efficient one.
\fc1\cf1
\pard\fc0\cf0 Its basic strategy is to begin at top and look at the first two elements and move the larger of the two down. Then it looks at the the second and third elements, moves the larger down. It continues like this, "bubbling" the largest element down to the very bottom. Then it returns to the top to do it all over again. It finishes when no more elements need to be exchanged.
\pard\tx520\tx1060\tx1600\tx2120\tx2660\tx3200\tx3720\tx4260\tx4800\tx5320\fc0\cf0 It is the poorest performer of the O(n^2) sorts, although it does improve somewhat on partially sorted data. As Don Knuth said, "
\fc1\cf1 In short, the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it lead to some interesting theoretical problems." If you are ever tempted to use Bubble Sort, wait for the feeling to pass, and then use Insertion Sort which is marginally faster and easier to write.\
\b Insertion Sort
\b0 \
An intuitive sort, if not a fast one. It incrementally builds a sorted list by considering each element in turn and inserting it in its proper place among those already sorted. In the beginning, the first element constitutes the sorted list. Then, inserting second element before or after the first element creates a sorted list length two. Subsequent elements are inserted into the growing list. Each insertion becomes more costly as the sorted list gets longer since it takes longer to find the proper place--notice how insertion sort slows down as it gets to the final elements. It is an O(n^2) sort, but works well on small data sets and takes advantage of partially sorted data. \
\b Merge Sort
\b0 \
A fairly fast and extremely stable recursive algorithm. It divides the data set into two equal halves, recursively sorts those two halves, and then merges the results together. It is very consistent - if makes no difference if the data is sorted or not. Merge Sort is always O(nlogn). As a side note, this sort uses more memory than my other sorts because I create a new array to hold the sorted and merged array. I once heard there was an algorithm to merge the two within the same array, but I couldn't figure that one out.\
\b Quicksort
\b0 \
True to its name, this sort is fast, but it is not without its faults. It works by partitioning a data set into two parts and then recursively sorting the parts. It divides the data by choosing a pivot value and moving all elements less than the pivot into one partition, all elements greater than the pivot go to the other. Each of the partitions are split again with a new pivot, and following the magic trail of recursion it arrives at a sorted data set. It is fast, even with the overhead of recursion. However, with a poor pivot choice, it can slow down enormously. A poor pivot choice is one that divides the data lopsidedly instead of creating two fairly equal partitions. For this reason, Quicksort works particularly poorly on data that is already sorted. Already sorted data is, in fact, its worst case at O(n^2) whereas its average case is O(nlogn).\
\b Selection Sort
\b0 \
Selection sort is not terribly fast, but the algorithm is the easiest to understand. It searchs the data set for the smallest element, and puts it in the first position. Then it seeks out the next smallest element to put in the second position and so forth. Lots and lots of comparision, but very little moving. Another of the O(n^2) variety sorts. As this algorithm is quite stable, it doesn't perform any better or worse on sorted data.\
\b Shellsort
\b0 \
Shellsort is a variation on Insertion Sort that is virtually unbeatable on small data sets. Insertion Sort is slow because it only exchanges adjacent elements. Shellsort circumvents this by allowing the exchange of elements that are farther apart. It works by first performing Insertion Sort on subsets of the data. For example, Shellsort might first sort the set of elements 1, 6, 11, 16... relative to each other--the effect is that the elements in that subset are moved much closer to their final positions. At first the sets are wide-spread, perhaps every fortieth element. Then it repeats using a tighter set, perhaps every fourteenth element, then every fourth element. Each of these passes is much cheaper than a traditional Insertion Sort pass. The effect of the passes is that the data set is mutated to be in "almost sorted" order. The final insertion sort pass can then go very quickly because insertion sort does very well on almost sorted data. In other words, at first the elements take large leaps to the general location they belong and successively smaller steps move the element to its precise place. I call this algorithm "inscrutable sort" because even after having coded the algorithm, I still have trouble following the animation. No one has been able to analyze this algorithm rigorously; the functional form of the running time is conjectured to be O(N^1.25). Shellsort may be a bit mysterious, but it is an good general purpose sort since it has excellent performance and the code you must write is only slightly more complex than Insertion Sort.\
Well, that about does it. \
\b Many thanks for help and inspiration from
\b0 : \
Paul Hegarty & Trey Matteson (programmers extraordinaire)\
(.txt)