58 SORTING ALGORITHMS
sort, bubble sort, shellsort, heapsort, merge sort, and quicksort using the lists
[6, 2, 4, 7, 1, 3, 8, 5] and [15, 4, 10, 8, 6, 9, 16, 1, 7, 3, 11, 14, 2, 5, 12, 13].
You should trace radix sort using three buckets for 1, 2, and 3, and the list
[1113, 2231, 3232, 1211, 3133, 2123, 2321, 1312, 3223, 2332, 1121, 3312].
Additionally, you should try to answer any questions before reading on. A hint
or the answer is in the sentences following the question.n this chapter, we will consider another class of fundamental algorithms
from computing: sorting algorithms. Because of the significant time sav-
ings of binary search over sequential search, software designers will fre-
quently choose to keep information sorted so that searches can be done by
binary or other nonsequential methods.
As in Chapter 2, we will work with a list of records, which have a special
field called the key. All of our sort algorithms will sort the list into increasing
order based on this key value. We will use standard comparisons with these
keys with the full knowledge that when they are used, we might be comparing
integers, strings, or more complex key types. For the sake of simplicity, we will
assume that each of the values in the list is distinct, because the presence of
duplicates will not significantly change any of the analyses that we do in this
chapter. The reader should recognize that changing the comparison of keys
would result in a different ordering. For example, if the less than and greater
than comparisons are swapped, the list will be sorted in decreasing order.
The eight sorting algorithms discussed in this chapter are only a sampling of
the possible sorts, but they exhibit a wide range of behaviors. The first, inser-
tion sort, accomplishes sorting by inserting new elements into the correct
place in a list that is already sorted. Bubble sort compares pairs of elements,
swapping those that are out of order, until the list is sorted. Shellsort is a multi-
pass sort that breaks the list into sublists that are sorted, and on each successive
pass the number of sublists is decreased as their size is increased. Radix sort is a
multipass sort that separates the list into buckets, each pass using a different part
of the key. Heapsort builds a binary tree with list elements so that each node
has a value larger than its children. This places the largest element at the root so
that when it is removed and the heap is fixed, the next largest element moves
to the root. This is repeated until all of the elements are back in the now-sorted
list. Merge sort starts with two sorted lists and creates one sorted list by merg-I