Selection, Bubble, Insertion, and Counting Sort

by Justin Skycak (x.com/justinskycak) on

Some of the simplest methods for sorting items in arrays.

This post is part of the book Introduction to Algorithms and Machine Learning: from Sorting to Strategic Agents. Suggested citation: Skycak, J. (2021). Selection, Bubble, Insertion, and Counting Sort. In Introduction to Algorithms and Machine Learning: from Sorting to Strategic Agents. https://justinmath.com/selection-bubble-insertion-and-counting-sort/

Want to get notified about new posts? Join the mailing list.

There are many different methods for sorting items in arrays. Let’s go over some of the simplest methods.

Selection Sort

The absolute simplest sorting method, selection sort, involves building up a separate sorted array by repeatedly taking the minimum element from the original array. To illustrate, let’s sort the array [3, 5, 8, 2, 5] using selection sort.

  • Our original array is [3, 5, 8, 2, 5] and our sorted array is empty [ ] since we just started. The minimum element of our original array is 2, and we move this element to the sorted array.
  • Our original array is now [3, 5, 8, 5] and our sorted array is [2]. The minimum element of our original array is 3, and we move this element to the sorted array.
  • Our original array is now [5, 8, 5] and our sorted array is [2, 3]. The minimum element of our original array is 5, and we move this element to the sorted array.
  • Our original array is now [8, 5] and our sorted array is [2, 3, 5]. The minimum element of our original array is 5, and we move this element to the sorted array.
  • Our original array is now [8] and our sorted array is [2, 3, 5, 5]. The minimum element of our original array is 8, and we move this element to the sorted array.
  • Our original array is now empty [ ] and our sorted array is [2, 3, 5, 5, 8]. We're done!

Bubble Sort

Another simple sorting method, bubble sort involves repeatedly looping through all pairs of consecutive elements in the array and swapping them if they are out of order. Let’s sort the array [3, 5, 8, 2, 5] using bubble sort.

  1. First pass
    • [(3, 5), 8, 2, 5] - The first pair of consecutive elements is (3,5). These elements are in the correct order, so we do nothing.
    • [3, (5, 8), 2, 5] - The next pair of consecutive elements is (5,8). These elements are in the correct order, so we do nothing.
    • [3, 5, (8, 2), 5] - The next pair of consecutive elements is (8,2). These elements are out of order, so we swap them. Our updated array is [3, 5, 2, 8, 5].
    • [3, 5, 2, (8, 5)] - The next pair of consecutive elements is (8,5). These elements are out of order, so we swap them. Our updated array is [3, 5, 2, 5, 8].
  2. Since we made a swap in the first pass, we proceed to a second pass.
    • [(3, 5), 2, 5, 8]
    • [3, (5, 2), 5, 8] - Swap. The array is now [3, 2, 5, 5, 8].
    • [3, 2, (5, 5), 8]
    • [3, 2, 5, (5, 8)]
  3. Since we made a swap in the second pass, we proceed to a third pass.
    • [(3, 2), 5, 5, 8] - Swap. The array is now [2, 3, 5, 5, 8].
    • [2, (3, 5), 5, 8]
    • [2, 3, (5, 5), 8]
    • [2, 3, 5, (5, 8)]
  4. Since we made a swap in the third pass, we proceed to a fourth pass.
    • [(2, 3), 5, 5, 8]
    • [2, (3, 5), 5, 8]
    • [2, 3, (5, 5), 8]
    • [2, 3, 5, (5, 8)]
  5. Since we made no swaps in the fourth pass, we are done!

Insertion Sort

Insertion sort is similar to bubble sort, with one key difference. Whenever we find something out of order, instead of carrying out just one swap, we repeatedly swap the out-of-order element backwards until it is in the correct position. Let’s illustrate.

  • [(3, 5), 8, 2, 5]
  • [3, (5, 8), 2, 5]
  • [3, 5, (8, 2), 5] - Swap and note where we left off. We will now start looking backwards, continuing to swap the 2 until it is in the correct position.
  • [3, (5, 2), 8*, 5] - Swap and continue looking backwards.
  • [(3, 2), 5, 8*, 5] - Swap. Normally we would continue looking backwards, but we can't go backwards any more since we're at the beginning of the array. So, we're done dealing with the 2 and we can pick up from where we left off.
  • [2, 3, 5, (8, 5)] - Swap and note where we left off. We will now start looking backwards, continuing to swap the 5 until it is in the correct position.
  • [2, 3, (5, 5), 8*] - No swap needed. The 5 is in the correct position. Normally we would pick up from where we left off, but we left off at the end of the array, so we're done!

Counting Sort

Lastly, counting sort is quite different from all the sorting methods we’ve covered so far. It’s more involved, so we will outline the procedure before showing an example. The procedure is as follows:

  1. Identify the minimum number in the array and then subtract it from all numbers in the array. This way, the updated array has a minimum of 0 and all other elements are positive.
  2. Let N be the maximum number in the array. Create another array, counts, with N+1 entries, all initialized to 0.
  3. Loop through the array. For each number n that you encounter, increment counts[n]. This way, the value of counts[n] represents the amount of times that you encountered the number n
  4. Read off the counts array into a sorted array that contains counts[n] instances of each number n.
  5. In the first step, you subtracted the minimum number of the original array. Undo that by adding the minimum number to each element in your sorted array. Finally, we're done!


Below is an example of applying counting sort to sort the array [3, 5, 8, 2, 5].

  1. The minimum number is 2. Subtracting 2 from all numbers in the array, the updated array is [1,3,6,0,3].
  2. The maximum number in the new array is 6. So, we let counts = [0,0,0,0,0,0,0].
  3. We loop through the array [1,3,6,0,3] and increment counts.
    • The first element is 1, so we increment counts[1]. Now we have counts = [0,1,0,0,0,0,0].
    • The next element is 3, so we increment counts[3]. Now we have counts = [0,1,0,1,0,0,0].
    • The next element is 6, so we increment counts[6]. Now we have counts = [0,1,0,1,0,0,1].
    • The next element is 0, so we increment counts[6]. Now we have counts = [1,1,0,1,0,0,1].
    • The next element is 3, so we increment counts[6]. Now we have counts = [1,1,0,2,0,0,1].
  4. We read off the array counts = [1,1,0,2,0,0,1] as follows: 1 zero, 1 one, 0 twos, 2 threes, 0 fours, 0 fives, 1 six. So, we have a sorted array [0, 1, 3, 3, 6].
  5. In the first step, we subtracted 2. Now we add that back to each item of the sorted array and get [2, 3, 5, 5, 8]. We're done!

Time Complexity

It’s common to refer to time complexity when talking about the speed of various algorithms. Selection, bubble, and insertion sort all have average-case time complexity $O(n^2),$ pronounced order of $n$ squared. Loosely speaking, this means that if we were to create a mathematical expression for the average number of operations required to sort a list of $n$ elements, the variable part of the dominating term would be $n^2.$

To understand why selection sort is $O(n^2),$ remember that selection sort involves repeatedly building up a separate sorted array by repeatedly taking the minimum element from the original array. The original array initially consists of $n$ elements, and we need to check each of them when computing the minimum, so there are $n$ operations. Once we’ve computed the minimum and moved it to the sorted array, we need to repeat the procedure on the remaining $n-1$ elements. Continuing the pattern and adding up all the operations, we get the following expression:

$\begin{align*} &n + (n-1) + (n-2) + \ldots + 1 \\[5pt] &= \dfrac{n(n+1)}{2} \\[5pt] &= \dfrac{1}{2}n^2 + \dfrac{1}{2}n \end{align*}$


Indeed, the dominating term is $\dfrac{1}{2}n^2,$ and its variable part is $n^2.$ The time complexities of bubble and insertion sort can be derived in a similar way.

Counting sort is generally faster than selection, bubble, and insertion sort. However, the drawback is that it can require lots of memory.

Exercises

First, write a function calc_min(arr) that calculates the minimum element of an array by looping through and keeping track of the smallest element that has been found. Then, for each sorting method described above, write a function that takes an input array and sorts it using the described procedure.

Do not use the built-in min() function; instead, use your calc_min function. Be sure to write plenty of tests that cover a variety of cases (negative numbers, repeated numbers, duplicates, decimals, etc).

  1. Write calc_min(arr).
  2. Write selection_sort(arr).
  3. Write bubble_sort(arr).
  4. Write insertion_sort(arr).
  5. Write counting_sort(arr).
  6. Derive the average-case time complexity of bubble sort.
  7. Derive the average-case time complexity of insertion sort.
  8. Derive the average-case time complexity of counting sort.
  9. Construct an example in which counting sort requires drastically more memory than selection, bubble, and insertion sort. (Hint: what would cause the counts array to become enormous?)

This post is part of the book Introduction to Algorithms and Machine Learning: from Sorting to Strategic Agents. Suggested citation: Skycak, J. (2021). Selection, Bubble, Insertion, and Counting Sort. In Introduction to Algorithms and Machine Learning: from Sorting to Strategic Agents. https://justinmath.com/selection-bubble-insertion-and-counting-sort/


Want to get notified about new posts? Join the mailing list.