Description

This app, inspired by Robert Sedgewick's Algorithms text (See [3]), provides visual demonstrations seven sorting algorithms:

• Bubble Sort
• Selection Sort
• Insertion Sort
• Quick Sort
• Shell Sort
• Merge Sort
• Heap Sort

Assume that we have a data set of size $n$ that can be ordered a key associated with each element of the data set. The keys could be integers, strings or something more complex. Then the cost of a sorting algoritm into increasing order is measured by

• The number of comparisons between keys used
• The number of assignments of keys
• The amount of additional space used

Note: Operations related to indexing of loops and other indexing operations involving integers or pointers are not measured as these kinds of computations are highly implementation dependent.

In table below the average and worst case costs in terms of comparisons is listed along with the amount of additional space used.

Sort Algorithm	Worst Case	Average Case	Extra Space
Bubble	$\Theta(n^{2})$	$\Theta(n^{2})$	In Place
Selection	$\Theta(n^{2})$	$\Theta(n^{2})$	In Place
Insertion	$\Theta(n^{2})$	$\Theta(n^{2})$	In Place
Quick	$\Theta(n^{2})$	$\Theta(n \log n)$	$\propto n$
Shell	Depends on the gaps $\{h_{k}\}$ used: I used $h_{k}=\frac{3^k-1}{2} <= \lceil \frac{n}{3}\rceil$	$\Theta(n^{\frac{3}{2}})$	In Place
Merge	$\Theta(n \log n)$	$\Theta(n \log n)$	$n$
Heap	$\Theta(n \log n)$	$\Theta( n \log n) $	In Place

Remarks

• It is known that a sort algorithm uses at least $\lceil \log_{2} n! \rceil$ comparisons in the worst case and at least $\log_{2} n!$ comparisons in the average case where $\log_{2} n! \approx n\log_{2} n + O(n)$.
• The basic sorts Bubble, Selection and Insertion all use $\Theta(n^{2})$-comparisons of keys in the average and worst cases. However, the Insertion Sort is better than the others when the data is sorted or nearly sorted in which case it is nearly linear.
• Quick Sort is the most widely used sort because in the average case it uses $\Theta(n \log n)$-comparisons of keys. However, in the worst it too uses $\Theta(n^{2})$-comparisons of keys and it also uses additional space.
• The Shell Sort is a generalization of Insertion Sort. It repeatedly sorts subsets larger and larger of the data by using a sequence $h_{1} > h_{2} > ... > h_{k}= 1$ of positive integers that decrease to 1. As the integers become closer to one larger and larger subsets of the data are sorted. When $h_{k} = 1$ is reached, the entire set is sorted. It uses fewer comparisons as the sequence decreases because an increasing amount of the data is already sorted. If the sequence is selected carefully, it has shown experimentally that the Shell Sort uses $O(n^{\frac{3}{2}} )$-comparisons.
• The Merge Sort is often used for files rather or linked-lists rather than arrays.

References

[1] Sara Bass, Computer Algorithms: Introduction to Design and Analysis, Addison-Wesley, 1983.
[2] R.L. Kruse, B.P. Leung, C.L. Tondo, Data Structures and Program Design in C, Prentice-Hall , 1991.
[3] Robert Sedgewick, Algorithms, Second Edition, Addison-Wesley, 1988.

Instructions

Use the

• Size menu to select the data size to be either 7, 10, 15, 20, 31, 40, 63, 80, 127 or 160 values.
• Order menu to select the order of the data to be Decreasing, Increasing, or Random.
• Sort Method menu to select one of the seven sorts listed above.
• Display menu to represent the data by either Boxes or Bars.
  Note: If selected size of the data is less than 40, then each box or bar will be labeled with a nonnegative integer. Hopefully, this will make it easier to understand the selected sorting algorithm.
• Animation Rate menu to set the animation rate to Step-by-Step, Slow, Medium, Fast, Faster or Very Fast.

Finally, press the Sort button to begin the animation of the selected sort algorithm.

• If the Step-by-Step item is selected from the Animation Rate menu, the Pause will button change to Step and you must press it to execute the next step of the sort.
• If one of Slow through Very Fast items is selected as the animation rate the Pause will button change to Start and the initial state of the will be displayed. Pres the Start to start the animation.

---