Ontario 10 Applied (MFM2P) Sorting Algorithms
Lesson

Sorting is the process of arranging items systematically, into different groups or order.  The main purpose of sorting information is to make it easier to deal with the items or search for information.

Examples of why humans might like to sort items include:

• Sorting cards in your hand to make it easier to find the right card to play
• Sorting coins and notes in a bank to make it easier to determine the total value of money
• Sorting numbers to make it easier to determine the highest, lowest or middle number

Computer programs also need to sort data so that they can locate information and then perform operations on this information.

For our purposes we will be humans pretending to act like computers!

It can be easy to sort items when there are only a small number of items, but it becomes much more difficult when there are many items to sort.  We can use algorithms to make the sorting process more efficient.  There are many sorting algorithms, we will look at the following 5 algorithms:

1. Selection Sort
2. Insertion Sort
3. Bubble Sort
4. Bucket Sort
5. Merge Sort

### Selection Sort

Selection Sort involves systematically finding the numbers in order and swapping them into position until the numbers are in order.

The following steps and example show how to sort a list into ascending order (smallest to biggest) using the selection sort algorithm.

Step 1

Scan the list of numbers to find the smallest number and swap this number with the first number in the list Step 2

Scan the list of numbers to find the second smallest number and swap this number with the second number in the list Step 3

Scan the list of numbers to find the third smallest number and swap this number with the third number in the list (in this case the number is in correct position) Step 4

Scan the list of numbers to find the fourth smallest number and swap this number with the fourth number in the list The list is now sorted in ascending order

2 5 8 9 12

### Insertion Sort

Insertion Sort involves moving from left to right and determining the correct position for each number and inserting into their correct position

The following steps and example show how to sort a list into ascending order (smallest to biggest) using the insertion sort algorithm

Step 1 Compare the second number with the first number and if it’s less than the first number insert it before the first number Step 2 Compare the third number with the first two numbers and insert the number in the correct position so that the first 3 numbers are in ascending order Step 3 Compare the fourth number with the first three numbers and insert the number in the correct position so that the first 4 numbers are in ascending order Step 4 Compare the fifth number with the first four numbers and insert the number in the correct position so that the first 4 numbers are in ascending order The list is now sorted in ascending order
2 5 8 9 12

### Bubble Sort

Bubble sort involves comparing pairs of adjacent elements of the sequence, if they are in the wrong order swap them and do this until there are no swaps to do.

The following steps and example show how to sort a list into ascending order (smallest to biggest) using the bubble sort algorithm

Step 1 Compare the first 2 numbers and swap them if they are out of order. Step 2 Compare the next 2 numbers and swap them if they are out of order Step 3 Compare the next 2 numbers and swap them if they are out of order Step 4 Compare the next 2 numbers and swap them if they are out of order The largest number has now “bubbled” to the end of the list.  Now repeat this process starting at the start again.
5 8 2 9 12
Step 5 Compare the first 2 numbers and swap them if they are out of order.
5 8 2 9 12
Step 6 Compare the first 2 numbers and swap them if they are out of order. Step 7 Compare the first 2 numbers and swap them if they are out of order.
5 2 8 9 12
The second largest number has now “bubbled” to the second last position of the list.  The last 2 numbers do not need to be compared as they are in the correct position.  Now repeat the process starting at the start again.
5 2 8 9 12

Step 8 Compare the first 2 numbers and swap them if they are out of order. Step 9 Compare the first 2 numbers and swap them if they are out of order.
2 5 8 9 12
The third largest number has now “bubbled” to the third last position of the list.  The last 3 numbers do not need to be compared as they are in the correct position.  Now repeat the process starting at the start again.
2 5 8 9 12

Step 10 Compare the first 2 numbers and swap them if they are out of order.
2 5 8 9 12
The fourth largest number has now “bubbled” to the fourth last position of the list.  Therefore the smallest number will also be in the correct position.  The list has now been sorted into ascending order.
2 5 8 9 12

### Bucket Sort

The bucket sort algorithm involves placing data in buckets or bins.  These bins may represent single numbers or they may represent ranges of numbers that then have to be sorted using another sorting algorithm ( eg. insertion)

The following steps and example show how to sort a list into ascending order (smallest to biggest) using the bucket sort algorithm

The set of data to be sorted is

2 4 3 7 9 3 7 4 3

#### Solution

Step 1: The data consists of single digit numbers so we would usually sort them into single range bins 0-9.  Move from left to right along the data set and place (or point) each data element into the correct bin

0 1 2 3 4 5 6 7 8 9
2 3 4     7   9
3 4     7
3

Step 2: Remove empty bins and list numbers in order from each bin

2 3 3 3 4 4 7 7 9

Example: Use the bucket sort algorithm to manually sort the following set of data

12 34 33 75 39 23 74 34 38

Step 1: Data is 2 digit numbers so would usually sort into bins representing the tens digit. Move from left to right along data set and place/ point each data element into correct bin

0 1 2 3 4 5 6 7 8 9
12 23 34       75
33       74
39
34
38

Step 2: Use the insertion sort algorithm to sort elements in bins that have multiple elements

a) Sorting the 3's column

0 1 2 3 4 5 6 7 8 9
12 23 33       75
34       74
39
34
38

0 1 2 3 4 5 6 7 8 9
12 23 33       75
34       74
39
34
38
0 1 2 3 4 5 6 7 8 9
12 23 33       75
34       74
34
39
38
0 1 2 3 4 5 6 7 8 9
12 23 33
34
34
38
39

b) Sorting the 7's column

0 1 2 3 4 5 6 7 8 9
12 23 33       74
34       75
34
38
39

Step 3: Remove empty bins and list numbers in order from each bin

12 23 33 34 34 38 39 74 75

### Merge sort

The merge sort algorthm divides the list of numbers into smaller and smaller groups, orders them then combines them back together.

Example: Use the merge sort algorithm to manually sort the following set of data

23 53 4 34 76 45 23 14

Step 1: Divide the list into two lists of equal size (or nearly equal if there are an odd number of items).

23 53 4 34   76 45 23 14

Step 2: Continue to divide the lists until they are the smallest unit (1 element)

23 53   4 34   76 45   23 14
23   53   4   34   76   45   23   14

Step 3: Compare each element with the adjacent list and merge together sorted in order

23 53   4 34   45 76   14 23

Step 4: Continue to merge adjacent lists by comparing the first numbers of each list and listing the numbers in order

4 23 34 53   14 23 45 76
4 14 23 23 34 45 53 76

#### Worked Examples

##### Question 1

We want to use the insertion sort algorithm to manually sort the following set of data and then find the median.

$72,26,63,48,31,55,17$72,26,63,48,31,55,17

1. Use the insertion sort algorithm to arrange these numbers in ascending order.

Write one step of the insertion sort at a time, separating the numbers in the step with commas.

2. Hence find the median of the data set.

##### Question 2

We want to use the bucket sort algorithm to manually sort the following set of data and then find the median.

$81,31,12,94,65,28,47,54,76,93,71,11,35,27,85,42,66,56$81,31,12,94,65,28,47,54,76,93,71,11,35,27,85,42,66,56

1. Sort the numbers into the buckets below based on their tens digit.

When entering numbers in a column, each number belonging to that column should be entered in the order that they appear in the list. For example, if $12$12 appears before $11$11 in the list, then $12$12 should be before $11$11 in the column.

Bucket $1$1 $2$2 $3$3 $4$4 $5$5 $6$6 $7$7 $8$8 $9$9
$\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$
$\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$
2. Sort the numbers in each bucket in ascending order from top to bottom.

Bucket $1$1 $2$2 $3$3 $4$4 $5$5 $6$6 $7$7 $8$8 $9$9
$\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$
$\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$
3. Arrange the data set in ascending order.

$\editable{}$,$\editable{}$,$\editable{}$,$\editable{}$,$\editable{}$,$\editable{}$,$\editable{}$,$\editable{}$,$\editable{}$,$\editable{}$,$\editable{}$,$\editable{}$,$\editable{}$,$\editable{}$,$\editable{}$,$\editable{}$,$\editable{}$,$\editable{}$

4. Hence find the median of the data set.