Standard Sorting Algorithms (OCR GCSE Computer Science)

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

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

5

2

4

1

6

3

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

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)

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

7

4

1

2

6

3

8

5

Step	Instruction
1	Divide the dataset into individual datasets by repeatedly splitting the dataset in half (DIVIDE) 7 4 1 2 6 3 8 5 divide in half (2 datasets of 4 values) 7 4 1 2   6 3 8 5 divide in half again (4 datasets of 2 values) 7 4   1 2   6 3   8 5 divide in half again  (8 datasets of 1 value) 7   4   1   2   6   3   8   5
2	Merge pairs of sub-datasets together by comparing the first value in each dataset (CONQUER) 7   4   1   2   6   3   8   5 Merge into 4 datasets of 2 values 4 7   1 2   3 6   5 8
3	REPEAT step 2 until all sub-datasets are merged together into one dataset Merge into 2 datasets of 4 values 1 2 4 7   3 5 6 8 Merge into 1 dataset of 8 values (in the correct order) 1 2 3 4 5 6 7 8

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

54

27

17

9

40

12

Step	Instruction
1	Take the first value in the dataset, this is now the sorted list 54 27 17 9 40 12
2	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 27 54 17 9 40 12
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 27 54 17 9 40 12 17 27 54 9 40 12 9 17 27 54 40 12 9 17 27 40 54 12 9 12 17 27 40 54