# Selection, Bubble, Insertion, and Counting Sort

*Some of the simplest methods for sorting items in arrays.*

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

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.

- 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]`

.

- 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)]`

- 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)]`

- 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)]`

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

- 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. - Let
`N`

be the maximum number in the array. Create another array,`counts`

, with`N+1`

entries, all initialized to`0`

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

- Read off the
`counts`

array into a sorted array that contains`counts[n]`

instances of each number`n`

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

.

- The minimum number is
`2`

. Subtracting`2`

from all numbers in the array, the updated array is`[1,3,6,0,3]`

. - The maximum number in the new array is
`6`

. So, we let`counts = [0,0,0,0,0,0,0]`

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

.

- The first element is
- 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]`

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

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

- Write
`calc_min(arr)`

. - Write
`selection_sort(arr)`

. - Write
`bubble_sort(arr)`

. - Write
`insertion_sort(arr)`

. - Write
`counting_sort(arr)`

. - Derive the average-case time complexity of bubble sort.
- Derive the average-case time complexity of insertion sort.
- Derive the average-case time complexity of counting sort.
- 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 a chapter in the book Introduction to Algorithms and Machine Learning: from Sorting to Strategic Agents.* *Suggested citation:* Skycak, J. (2021). Selection, Bubble, Insertion, and Counting Sort. *Introduction to Algorithms and Machine Learning: from Sorting to Strategic Agents.* https://justinmath.com/selection-bubble-insertion-and-counting-sort/