Simple Sorting
This chapter is from the book
This chapter is from the book
This chapter is from the book
In This Chapter
-
How Would You Do It?
-
Bubble Sort
-
Selection Sort
-
Insertion Sort
-
Sorting Objects
-
Comparing the Simple Sorts
As soon as you create a significant database, you'll probably think of reasons to sort it in various ways. You need to arrange names in alphabetical order, students by grade, customers by ZIP code, home sales by price, cities in order of increasing population, countries by GNP, stars by magnitude, and so on.
Sorting data may also be a preliminary step to searching it. As we saw in Chapter 2, "Arrays," a binary search, which can be applied only to sorted data, is much faster than a linear search.
Because sorting is so important and potentially so time-consuming, it has been the subject of extensive research in computer science, and some very sophisticated methods have been developed. In this chapter we'll look at three of the simpler algorithms: the bubble sort, the selection sort, and the insertion sort. Each is demonstrated with its own Workshop applet. In Chapter 7, "Advanced Sorting," we'll look at more sophisticated approaches: Shellsort and quicksort.
The techniques described in this chapter, while unsophisticated and comparatively slow, are nevertheless worth examining. Besides being easier to understand, they are actually better in some circumstances than the more sophisticated algorithms. The insertion sort, for example, is preferable to quicksort for small files and for almost-sorted files. In fact, an insertion sort is commonly used as a part of a quicksort implementation.
The example programs in this chapter build on the array classes we developed in the preceding chapter. The sorting algorithms are implemented as methods of similar array classes.
Be sure to try out the Workshop applets included in this chapter. They are more effective in explaining how the sorting algorithms work than prose and static pictures could ever be.
How Would You Do It?
Imagine that your kids-league baseball team (mentioned in Chapter 1, "Overview") is lined up on the field, as shown in Figure 3.1. The regulation nine players, plus an extra, have shown up for practice. You want to arrange the players in order of increasing height (with the shortest player on the left) for the team picture. How would you go about this sorting process?
){kind=link}
FIGURE 3.1 The unordered baseball team.
As a human being, you have advantages over a computer program. You can see all the kids at once, and you can pick out the tallest kid almost instantly. You don't need to laboriously measure and compare everyone. Also, the kids don't need to occupy particular places. They can jostle each other, push each other a little to make room, and stand behind or in front of each other. After some ad hoc rearranging, you would have no trouble in lining up all the kids, as shown in Figure 3.2.
){kind=link}
FIGURE 3.2 The ordered baseball team.
A computer program isn't able to glance over the data in this way. It can compare only two players at one time because that's how the comparison operators work. This tunnel vision on the part of algorithms will be a recurring theme. Things may seem simple to us humans, but the algorithm can't see the big picture and must, therefore, concentrate on the details and follow some simple rules.
The three algorithms in this chapter all involve two steps, executed over and over until the data is sorted:
Compare two items.
Swap two items, or copy one item.
However, each algorithm handles the details in a different way.