Data Structures & Algorithms in Python

3. Simple Sorting

In This Chapter

• How Would You Do It?

• Bubble Sort

• Selection Sort

• Insertion Sort

• Comparing the Simple Sorts

As soon as you create a significant database, you’ll probably think of reasons to sort the records in various ways. You need to arrange names in alphabetical order, students by grade, customers by postal code, home sales by price, cities in order of population, countries by land mass, stars by magnitude, and so on.

Sorting data may also be a preliminary step to searching it. As you 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 ...