Standard Sorting Algorithms (OCR GCSE Computer Science): Revision Note

What is a sorting algorithm?

• In GCSE Computer Science, sorting algorithms are precise step-by-step instructions that a computer can follow to sort data in massive datasets efficiently

• 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?

Example

• Perform a bubble sort on the following dataset

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?

Example

• Perform a merge sort on the following dataset

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?

Example

• Perform an insertion sort on the following dataset

An insertion sort in Python

# Initialise the list to be sorted
numbers = [12, 11, 13, 5, 6]

# Get the length of the list
length = len(numbers)

# Perform insertion sort
for i in range(1, length):
    key = numbers[i]  # The current element to be inserted in the sorted part of the array
    sorted_index = i - 1  # The last index of the sorted part of the array

    # Move elements of the sorted part of the array that are greater than the key
    # to one position ahead of their current position
    while sorted_index >= 0 and numbers[sorted_index] > key:
        numbers[sorted_index + 1] = numbers[sorted_index]
        sorted_index = sorted_index - 1

    # Place the key in its correct position in the sorted part of the array
    numbers[sorted_index + 1] = key

# Print the sorted list
print("Sorted list:", numbers)