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

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!

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** 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!

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!

*Practice Problems*

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

`calc_min(arr)`

`selection_sort(arr)`

`bubble_sort(arr)`

`insertion_sort(arr)`

`counting_sort(arr)`

## Leave a Comment