Elementary Sorting Algorithms

These demos are intended to supplement (not replace!) Chapter 6 of Sedgewick's Algorithms book. You can find detailed descriptions, code, and other information about the algorithms in the book.

Each demo is a dynamic representation of the algorithm in action, sorting an array a containing a permutation of the integers 1 through N. For each i, the array element a[i] is depicted as a black dot plotted at position (i, a[i]). Thus, the end result of each sort is a diagonal of black dots going from (1, 1) at the bottom left to (N, N) at the top right. Each time an element is moved, a green dot is left at its old position. Thus the moving black dots give a dynamic representation of the progress of the sort and the green dots give a history of the data-movement cost.

Insertion sort maintains a ordered subarray that appears as a diagonal of black dots that moves from left to right sweeping up each new element that it encounters. Each new element is inserted into the diagonal.

Selection sort builds the final diagonal by exchanging the next-smallest element into position. The main cost of selection sorts is the comparisons required to find that element. Comparisons are not depicted in this representation except for a delay to make the time take for a comparison comparable to the cost of an exchange. The algorithm is slow at the beginning (because it has to scan through most of the array to find the next minimum) and fast at the end (because it has to scan through only a few elements).

Bubble sort works like selection sort, but its cost is explicit in this representation because it uses exchanges (data movement) to move the minimum element from right to left, one position at a time.

Shellsort is clearly much faster than the others, even (for example) for a file that is initially in reverse order or for a file that is ten times larger.