Chapter 12. Sorting and Searching
Sorting means arranging a set of elements in a prescribed order. Normally a sort is thought of as either ascending or descending. An ascending sort of the integers {5, 2, 7, 1}, for example, produces {1, 2, 5, 7}, whereas a descending sort produces {7, 5, 2, 1}. In general, sorting serves to organize data so that it is more meaningful. Although the most visible application of sorting is sorting data to display it, often sorting is used to organize data in solving other problems, sometimes as a part of other formal algorithms.
In general, sorting algorithms are divided into two classes: comparison sorts and linear-time sorts. Comparison sorts rely on comparing elements to place them in the correct order. Surprisingly, not all sorting algorithms rely on making comparisons. For those that do, it is not possible to sort faster than in O (n lg n) time. Linear-time sorts get their name from sorting in a time proportional to the number of elements being sorted, or O (n). Unfortunately, linear-time sorts rely on certain characteristics in the data, so we cannot always apply them. Some sorts use the same storage that contains the data to store output as the sort proceeds; these are called in-place sorts . Others require extra storage for the output data, although they may copy the results back over the original data at the end.
Searching is the ubiquitous task of locating an element in a set of data. The simplest approach to locating an element takes very little thought: we simply scan the set from one end to the other. This is called linear search . Generally, it is used with data structures that do not support random access very well, such as linked lists (see Chapter 5). An alternative approach is to use binary search, which is presented in this chapter. Other approaches rely on data structures developed specifically for searching, such as hash tables (see Chapter 8) and binary search trees (see Chapter 9). This chapter covers:
- Insertion sort
Although not the most efficient sorting algorithm, insertion sort has the virtue of simplicity and the ability to sort in place. Its best application is for incremental sorting on small sets of data.
- Quicksort
An in-place sorting algorithm widely regarded as the best for sorting in the general case. Its best application is for medium to large sets of data.
- Merge sort
An algorithm with essentially the same performance as quicksort, but with twice its storage requirements. Ironically, its best application is for very large sets of data because it inherently facilitates working with divisions of the original unsorted set.
- Counting sort
A stable, linear-time sorting algorithm that works with integers for which we know the largest value. Its primary use is in implementing radix sort.
- Radix sort
A linear-time sorting algorithm that sorts elements digit by digit. Radix sort is well suited to elements of a fixed size that can be conveniently broken into pieces, expressible as integers.
- Binary search
An effective way to search sorted data in which we do not expect frequent insertions or deletions. Since resorting a set of data is expensive relative to searching it, binary search is best when the data does not change.
Some applications of sorting and searching algorithms are:
- Order statistics
Finding the i th smallest element in a set. One simplistic approach is to select the i th element out of the set once it has been sorted.
- Binary search
An efficient search method that relies on sorted data. Binary search works fundamentally by dividing a sorted set of data repeatedly and inspecting the element in the middle of each division.
- Directory listings (illustrated in this chapter)
Listings of files in a file system that have been organized into groups. Generally, an operating system will sort a directory listing in some manner before displaying it.
- Database systems
Typically, large systems containing vast amounts of data that must be stored and retrieved quickly. The amount of data generally stored in databases makes an efficient and flexible approach to searching the data essential.
- Spell checkers (illustrated in this chapter)
Programs that check the spelling of words in text. Validation is performed against words in a dictionary. Since spell checkers frequently deal with long strings of text containing many thousands of words, they must be able to search the set of acceptable words efficiently.
- Spreadsheets
An important part of most businesses for managing inventory and financial data. Spreadsheets typically contain diverse data that is more meaningful when sorted.