Java Reference
In-Depth Information
7
Internal Sorting
We sort many things in our everyday lives: A handful of cards when playing Bridge;
bills and other piles of paper; jars of spices; and so on. And we have many intuitive
strategies that we can use to do the sorting, depending on how many objects we
have to sort and how hard they are to move around. Sorting is also one of the most
frequently performed computing tasks. We might sort the records in a database
so that we can search the collection efficiently. We might sort the records by zip
code so that we can print and mail them more cheaply. We might use sorting as an
intrinsic part of an algorithm to solve some other problem, such as when computing
the minimum-cost spanning tree (see Section 11.5).
Because sorting is so important, naturally it has been studied intensively and
many algorithms have been devised. Some of these algorithms are straightforward
adaptations of schemes we use in everyday life. Others are totally alien to how hu-
mans do things, having been invented to sort thousands or even millions of records
stored on the computer. After years of study, there are still unsolved problems
related to sorting. New algorithms are still being developed and refined for special-
purpose applications.
While introducing this central problem in computer science, this chapter has
a secondary purpose of illustrating issues in algorithm design and analysis. For
example, this collection of sorting algorithms shows multiple approaches to us-
ing divide-and-conquer. In particular, there are multiple ways to do the dividing:
Mergesort divides a list in half; Quicksort divides a list into big values and small
values; and Radix Sort divides the problem by working on one digit of the key at
a time. Sorting algorithms can also illustrate a wide variety of analysis techniques.
We'll find that it is possible for an algorithm to have an average case whose growth
rate is significantly smaller than its worse case (Quicksort). We'll see how it is
possible to speed up sorting algorithms (both Shellsort and Quicksort) by taking
advantage of the best case behavior of another algorithm (Insertion sort). We'll see
several examples of how we can tune an algorithm for better performance. We'll
see that special case behavior by some algorithms makes them a good solution for
223
