Standard Sorting Algorithms

What is a sorting algorithm?

Sorting algorithms are precise step-by-step instructions that a computer can follow to efficiently sort data in massive datasets
Three common sorting algorithms are:
- Bubble sort
- Merge sort
- Insertion sort

Bubble Sort

What is a bubble sort?

A bubble sort is a simple sorting algorithm that starts at the beginning of a dataset and checks values in 'pairs' and swaps them if they are not in the correct order
One full run of comparisons from beginning to end is called a 'pass', a bubble sort may require multiple 'passes' to sort the dataset
The algorithm is finished when there are no more swaps to make

How do you perform a bubble sort?

Step	Instruction
1	Compare the first two values in the dataset
2	IF they are in the wrong order... Swap them
3	Compare the next two values
4	REPEAT step 2 & 3 until you reach the end of the dataset (pass 1)
5	IF you have made any swaps... REPEAT from the start (pass 2,3,4...)
6	ELSE you have not made any swaps... STOP! the list is in the correct order

Example

Perform a bubble sort on the following dataset

Step

Instruction

Compare the first two values in the dataset

IF they are in the wrong order...

Swap them

Compare the next two values

REPEAT step 2 & 3 until you reach the end of the dataset

5 & 4 SWAP!

5 & 1 SWAP!

5 & 6 NO SWAP!

6 & 3 SWAP!

End of pass 1

IF you have made any swaps...

REPEAT from the start
End of pass 2 (swaps made)

End of pass 3 (swaps made)

End of pass 4 (no swaps)

ELSE you have not made any swaps...

STOP! the list is in the correct order

Exam Tip

In the exam you do not have to show every swap that takes place in a bubble sort. You can show the outcome of a bubble sort at the end of each pass. If you have the outcome of each pass correct then a bubble sort has been implemented correctly and all marks will be given!

Worked example

A program uses a file to store a list of words.

A sample of this data is shown

Milk

Eggs

Bananas

Cheese

Potatoes

Grapes

Show the stages of a bubble sort when applied to data shown [2]

How to answer this question

We need to sort the values in to alphabetical order from A-Z
You CAN use the first letter of each word to simplify the process

Answer

E, B, C, M, G, P (pass 1)
B, C, E, G, M, P (pass 2)

A bubble sort in python

# unsorted dataset
nums=[66, 7, 69, 50, 42, 80, 71, 321, 67, 8, 39]

# count the length of the dataset
numlength = len(nums)

# sets a flag to initiate the loop
swaps = True

while swaps == True :
swaps = False
# loop through the dataset
for y in range(numlength-1) :
# if the first number is bigger than the second number
if nums[y] > nums[y+1] :
# swap the numbers using a temporary variable
temp = nums[y]
nums[y] = nums[y+1]
nums[y+1] = temp
# sets the flag to true
swaps = True

# prints the sorted list
print (nums)

Merge Sort

What is a merge sort?

A merge sort is a sorting algorithm that uses the 'divide and conquer' strategy of dividing a dataset into smaller sub-datasets and merging them back together in the correct order

How do you perform a merge sort?

Step	Instruction
1	Divide the dataset into individual datasets by repeatedly splitting the dataset in half (DIVIDE)
2	Merge pairs of sub-datasets together by comparing the first value in each dataset (CONQUER)
3	REPEAT step 2 until all sub-datasets are merged together into one dataset

Example

Perform a merge sort on the following dataset

Step

Instruction

Divide the dataset into individual datasets by repeatedly splitting the dataset in half (DIVIDE)

divide in half (2 datasets of 4 values)

divide in half again (4 datasets of 2 values)

divide in half again (8 datasets of 1 value)

Merge pairs of sub-datasets together by comparing the first value in each dataset (CONQUER)

Merge into 4 datasets of 2 values

REPEAT step 2 until all sub-datasets are merged together into one dataset

Merge into 2 datasets of 4 values

Merge into 1 dataset of 8 values (in the correct order)

Exam Tip

In the exam, the divide stage could already be done for you and you would only need to demonstrate the conquer stage!

Insertion Sort

What is an insertion sort?

The insertion sort sorts one item at a time by placing it in the correct position of an unsorted list. This process repeats until all items are in the correct position
Values in the dataset can move as many places as they need

How do you perform an insertion sort?

Step	Instruction
1	Take the first value in the dataset, this is now the sorted list
2	Look at the next value in the dataset and compare it to the first value IF it is smaller insert it into the correct position to the left
3	ELSE Keep in the same position
4	REPEAT steps 2 & 3 until all values in the dataset have been compared, the list should now be in order

Example

Perform an insertion sort on the following dataset

Step

Instruction

Take the first value in the dataset, this is now the sorted list

Look at the next value in the dataset (27) and compare it to the first value (is 27 < 54?)

IF it is smaller (YES!)

insert it into the correct position on the left of the first

ELSE

Keep in the same position

REPEAT steps 2 & 3 until all values in the dataset have been compared, the list should now be in order

Exam Tip

Remember that in any sorting algorithm question, you make be asked to demonstrate a sort using words instead of numbers. The process is the same, the order will be alphabetically from A-Z unless stated in the question.

You may also abbreviate words using just their first letter as long as two values don't share the same first letter!