Quadratic Sorting

This chapter covers three quadratic sorting algorithms: selection sort, bubble sort, and insertion sort. For each one we count the comparisons and swaps on different inputs, and then we compare the three sorts and decide which of them are stable.

After reading this chapter, you should be able to:

  • Trace bubble sort and insertion sort on an array by hand
  • Implement selection sort, bubble sort, and insertion sort in place on an int array
  • State the loop invariant each of the three sorts keeps
  • Count each sort’s comparisons and swaps, using the number of inversions in the input to count the swaps of bubble sort and insertion sort
  • Compare the three sorts by their comparisons and swaps on sorted, reverse-sorted, random, and nearly sorted input
  • Add early termination to bubble sort and shifting to insertion sort, and say what each refinement changes and what it does not
  • Define a stable sort and decide which of the three sorts are stable

You can download the accompanying code for this chapter: starter and solution.

Sections

  1. Selection Sort, Again
  2. Selection Sort: Comparisons and Swaps
  3. Bubble Sort: The Idea
  4. Implementing Bubble Sort
  5. Bubble Sort: Comparisons and Swaps
  6. Bubble Sort with Early Termination
  7. Insertion Sort: The Idea
  8. Implementing Insertion Sort
  9. Insertion Sort: Comparisons and Swaps
  10. Insertion Sort: Shifting Instead of Swapping
  11. Classifying the Sorts We Have Written
  12. Stable Sorting