Java Reference
In-Depth Information
Key = 42
Key = 42
Key = 5
Key = 5
Key = 23
Key = 23
Key = 10
Key = 10
(a)
(b)
Figure7.4
An example of swapping pointers to records. (a) A series of four
records. The record with key value 42 comes before the record with key value 5.
(b) The four records after the top two pointers have been swapped. Now the record
with key value 5 comes before the record with key value 42.
advantageous when the cost to do a swap is high, for example, when the elements
are long strings or other large records. Selection Sort is more efficient than Bubble
Sort (by a constant factor) in most other situations as well.
There is another approach to keeping the cost of swapping records low that
can be used by any sorting algorithm even when the records are large. This is
to have each element of the array store a pointer to a record rather than store the
record itself. In this implementation, a swap operation need only exchange the
pointer values; the records themselves do not move. This technique is illustrated
by Figure 7.4. Additional space is needed to store the pointers, but the return is a
faster swap operation.
7.2.4
The Cost of Exchange Sorting
Figure 7.5 summarizes the cost of Insertion, Bubble, and Selection Sort in terms of
their required number of comparisons and swaps
1
in the best, average, and worst
cases. The running time for each of these sorts is (n
2
) in the average and worst
cases.
The remaining sorting algorithms presented in this chapter are significantly bet-
ter than these three under typical conditions. But before continuing on, it is instruc-
tive to investigate what makes these three sorts so slow. The crucial bottleneck
is that only adjacent records are compared. Thus, comparisons and moves (in all
but Selection Sort) are by single steps. Swapping adjacent records is called an ex-
change. Thus, these sorts are sometimes referred to as exchange sorts. The cost
of any exchange sort can be at best the total number of steps that the records in the
1
There is a slight anomaly with Selection Sort. The supposed advantage for Selection Sort is its
low number of swaps required, yet Selection Sort's best-case number of swaps is worse than that for
Insertion Sort or Bubble Sort. This is because the implementation given for Selection Sort does not
avoid a swap in the case where recordiis already in positioni. One could put in a test to avoid
swapping in this situation. But it usually takes more time to do the tests than would be saved by
avoiding such swaps.
