15.10 Sorting algorithms

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 five 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 three 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 two numbers and swap them if they are out of order.
Step 2	Compare the next two numbers and swap them if they are out of order
Step 3	Compare the next two numbers and swap them if they are out of order
Step 4	Compare the next two 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 two numbers and swap them if they are out of order.	5 8 2 9 12
Step 6	Compare the first two numbers and swap them if they are out of order.
Step 7	Compare the first two 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 two 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 two numbers and swap them if they are out of order.
Step 9	Compare the first two 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 three 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 two 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$0-$9$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 two-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

 

 

Practice questions

Question 1

Question 2