- How Would You Do It?
- Bubble Sort
- Selection Sort
- Insertion Sort
- Sorting Objects
- Comparing the Simple Sorts
- Summary
- Questions
- Experiments
- Programming Projects
This chapter is from the book
This chapter is from the book
This chapter is from the book
Comparing the Simple Sorts
There's probably no point in using the bubble sort, unless you don't have your algorithm book handy. The bubble sort is so simple that you can write it from memory. Even so, it's practical only if the amount of data is small. (For a discussion of what "small" means, see Chapter 15, "When to Use What.")
The selection sort minimizes the number of swaps, but the number of comparisons is still high. This sort might be useful when the amount of data is small and swapping data items is very time-consuming compared with comparing them.
The insertion sort is the most versatile of the three and is the best bet in most situations, assuming the amount of data is small or the data is almost sorted. For larger amounts of data, quicksort is generally considered the fastest approach; we'll examine quicksort in Chapter 7.
We've compared the sorting algorithms in terms of speed. Another consideration for any algorithm is how much memory space it needs. All three of the algorithms in this chapter carry out their sort in place, meaning that, besides the initial array, very little extra memory is required. All the sorts require an extra variable to store an item temporarily while it's being swapped.
You can recompile the example programs, such as bubbleSort.java, to sort larger amounts of data. By timing them for larger sorts, you can get an idea of the differences between them and the time required to sort different amounts of data on your particular system.