### 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.

For another view of insertion, selection, and bubble sorts, see
these color plates. In these views,
the algorithms progress from top to bottom, with square chips sorted
according to their color at the bottom. Your challenge is to determine
which algorithm is which in these views.