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

Selection Sort
Insertion Sort
Bubble Sort
Bucket Sort
Merge Sort

Selection sort and insertion 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.

Numbers 12 , 8, 5, 2, and 9 with interchanging arrows between the numbers 12 and 2.

Step 1

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

Numbers 2 , 8, 5, 12, and 9 with interchanging arrows between the numbers 8 and 5.

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

Numbers 2 , 5, 8, 12, and 9 with interchanging arrows between the numbers 12 and 9.

Step 4

Scan the list of numbers to find the fourth smallest number and swap this number with the fourth number in the list.

Numbers arranged in ascending order: 2, 5, 8, 9, 12.

The list is now sorted in ascending order

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

The following example shows how to sort a list into ascending order (smallest to biggest) using the insertion sort algorithm.

Examples

Example 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

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

Worked Solution

Create a strategy

Move numbers from left to right until they reached their correct position.

Apply the idea

Compare 26 with 72: 26 \lt 72 so we move 26 to the left of 72: 26, \, 72, \, 63, \, 48, \, 31, \, 55, \, 17

Compare 63 with 26 and 72: 26 \lt 63 \lt 72, so we move 63 to the left between 26 and 72: 26, \, 63, \, 72, \, 48, \, 31, \, 55, \, 17

Compare 48 with 26, 63 and 72 : 26 \lt 48 \lt 63 \lt 72, so we move 48 to the left between 26 and 63: 26, \, 48, \, 63, \, 72, \, 31, \, 55, \, 17

Compare 31 with 26,\, 48, \, 63 and 72 : 26 \lt 31 \lt 48 \lt 63 \lt 72, so we move 31 to the left between 26 and 48: 26, \, 31, \, 48, \, 63, \, 72, \, 55, \, 17

Compare 55 with 26,\, 31, \, 48, \, 63 and 72 : 26 \lt 31 \lt 48 \lt 55 \lt 63 \lt 72, so we move 55 to the left between 48 and 63: 26, \, 31, \, 48, \, 55, \, 63, \, 72, \, 17

Compare 17 with 26,\, 31, \, 48, \, 55, \, 63 and 72 : 17\lt 26 \lt 31 \lt 48 \lt 55 \lt 63 \lt 72, so we move 17 to the left before 26: 17, \, 26, \, 31, \, 48, \, 55, \, 63, \, 72

Find the median of the data set.

Worked Solution

Create a strategy

Find the middle value.

Apply the idea

The middle value of the ordered list: 17, \, 26, \, 31, \, 48, \, 55, \, 63, \, 72 is 48.\text{Median} = 48

Idea summary

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

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

Bubble sort and bucket 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:

Numbers 12, 5, 8, 2 and 9 with interchanging arrows between the numbers 12 and 5.

Step 1

Compare the first 2 numbers and swap them if they are out of order.

Numbers 5, 12, 8, 2 and 9 with interchanging arrows between the numbers 12 and 8.

Step 2

Compare the next 2 numbers and swap them if they are out of order.

Numbers 5, 8, 12, 2 and 9 with interchanging arrows between the numbers 12 and 2.

Step 3

Compare the next 2 numbers and swap them if they are out of order.

Numbers 5, 8, 2, 12 and 9 with interchanging arrows between the numbers 12 and 9.

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.

Step 5

Compare the first 2 numbers and swap them if they are out of order.

Numbers 5, 8, 2, 9 and 12 with interchanging arrows between the number 8 and 2.

Step 6

Compare the next 2 numbers and swap them if they are out of order.

Step 7

Compare the next 2 numbers and swap them if they are out of order.

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.

Numbers 5, 2, 8, 9 and 12 with interhchanging arrows between 2 and 5.

Step 8

Compare the first 2 numbers and swap them if they are out of order.

Step 9

Compare the next 2 numbers and swap them if they are out of order.

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.

Step 10

Compare the first 2 numbers and swap them if they are out of order.

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.

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 example shows how to sort a list into ascending order (smallest to biggest) using the bucket sort algorithm.

Examples

Example 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

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

Each number belonging to that column should be entered in the order that they appear in the list.

\text{Bucket}	1	2	3	4	5	6	7	8	9
	⬚	⬚	⬚	⬚	⬚	⬚	⬚	⬚	⬚
	⬚	⬚	⬚	⬚	⬚	⬚	⬚	⬚	⬚

Worked Solution

Create a strategy

Put each number in the list in the column for its tens digit.

Apply the idea

\text{Bucket}	1	2	3	4	5	6	7	8	9
\text{}	12	28	31	47	54	65	76	81	94
\text{}	11	27	35	42	56	66	71	85	93

Sort the numbers in each bucket in ascending order from top to bottom.

Worked Solution

Create a strategy

Use the table from part (a) and compare the numbers in each column.

Apply the idea

\text{Bucket}	1	2	3	4	5	6	7	8	9
\text{}	11	27	31	42	54	65	71	81	93
\text{}	12	28	35	47	56	66	76	85	94

Arrange the data set in ascending order.

Worked Solution

Create a strategy

Use the table in part (b).

Apply the idea

List the number in each column from top to bottom from the left column to the last column to the right.

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

Find the median of the data set.

Worked Solution

Create a strategy

Find the middle score.

Apply the idea

There are 18 values in the data set. Since 18 is even, the median is the average of the two middle values, which are the 9th and the 10th value in the ordered list.

\displaystyle \text{median}	\displaystyle =	\displaystyle \dfrac{54 + 56}{2}	Average the 9th and 10th values
	\displaystyle =	\displaystyle 55	Evaluate

Idea summary

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.

Bucket sort 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.

Merge sort

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

Examples

Example 3

We want to use the merge sort algorithm to manually sort the following set of data and then find the median.78,\,12,\,6,\,63,\,24,\,49,\,9,\,5

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

Worked Solution

Create a strategy

Divide the list of numbers into smaller and smaller groups, order the groups, then combine them.

Apply the idea

Divide the list into two lists of equal size: 78, \, \, 12, \, \, 6, \, \, 63, \, \, \, \, \, \, \, \, 24, \, \, 49, \, \, 9,\, \, 5

Divide the lists again into lists of equal size: 78, \, \, 12, \, \, \, \, \, \, \, \, 6, \, \, 63, \, \, \, \, \, \, \, \, 24, \, \, 49, \, \, \, \, \, \, \, \, 9,\, \, 5

Continue to divide each list until they have only 1 element each:78, \, \, \, \, \, \, \, \, 12, \, \, \, \, \, \, \, \, 6, \, \, \, \, \, \, \, \, 63, \, \, \, \, \, \, \, \, 24, \, \, \, \, \, \, \, \, 49, \, \, \, \, \, \, \, \, 9, \, \, \, \, \, \, \, \,5

Compare each element with the adjacent list and merge together sorted in order: 12, \, \, 78, \, \, \, \, \, \, \, 6, \, \, 63, \, \, \, \, \, \, \, 24, \, \, 49, \, \, \, \, \, \, \, 5, \, \, 9

Merge the adjacent lists once again by comparing the numbers of each list and listing the numbers in order. 6, \, \, 12, \, \, 63, \, \, 78, \, \, \, \, \, \, \, \, 5, \, \, 9, \, \, 24, \, \, 49

Continue merging adjacent lists until the set of data are sorted. 5, \, \, \, \, 6, \, \, \, \, 9, \, \, \, \, 12, \, \, \, \, 24, \, \, \, \, 49, \, \, \, \, 63, \, \, \, \, 78

Hence find the median of the data set.

Worked Solution

Create a strategy

Find the middle score of the ordered list.

Apply the idea

The ordered list of numbers is: 5, \, 6, \, 9, \, 12, \, 24, \, 49, \, 63, \, 78Since there are 8 scores, the median will be the average of the two middle scores: 12 and 24.

\displaystyle \text{Median}	\displaystyle =	\displaystyle \dfrac{12+24}{2}	Find the average
	\displaystyle =	\displaystyle 18	Evaluate

Idea summary

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

12.13 Sorting algorithms

Introduction

Ideas

Selection sort and insertion sort

Examples

Example 1

Bubble sort and bucket sort

Examples

Example 2

Merge sort

Examples

Example 3

What is Mathspace

About Mathspace