Data Structures and Algorithms in Java, 2nd Edition

3. Simple Sorting

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 ...