1

mrahmedcomputing

KS3, GCSE, A-Level Computing Resources

Lesson 3. Sorting Algorithms

Lesson Objective

  • Understand how to use the bubble sort algorithm.
  • Understand how to use the insertion sort algorithm.
  • Understand how to use the merge sort algorithm.
  • Understand how to use the quick sort algorithm.
  • Identify the time complexity of the bubble, insertion, merge and quick sort algorithms.

Lesson Notes

Bubble Sort

Imagine you have a messy list of items.

  1. Start at the beginning: Compare each item to the one next to it.
  2. Swap if bigger: If an item is bigger than its neighbor, swap their positions in the list.
  3. Move on, but leave the biggest behind: After comparing everything, the biggest item will be at the end.
  4. Repeat, shrinking the list: Do the same comparisons again, but skip the end (already the biggest). This moves the next biggest item back one step.
  5. Keep going until sorted: Continue comparing and swapping, moving towards the front of the list, until all items are in order from smallest to biggest (or biggest to smallest, depending on the sorting goal).

This process is like bubbles of larger items constantly "floating" to the end as the list gets more ordered.

Result of the first pass

9 5 4 15 3 8 11 2
5 9 4 15 3 8 11 2
5 4 9 15 3 8 11 2
5 4 9 15 3 8 11 2
5 4 9 3 15 8 11 2
5 4 9 3 8 15 11 2
5 4 9 3 8 11 15 2
5 4 9 3 8 11 2 15

Result of the second pass

5 4 9 3 8 11 2 15
4 5 9 3 8 11 2 15
4 5 9 3 8 11 2 15
4 5 3 9 8 11 2 15
4* 5 3 8 9 11 2 15
4 5 3 8 9 11 2 15
4 5 3 8 9 2 11 15
4 5 3 8 9 2 11 15

Pseudocode

function bubbleSort(array):
  for i = 0 to length(array) - 1:
    for j = 0 to length(array) - 2:
      if array[j] > array[j + 1]:
        temp = array[j]
        array[j] = array[j + 1]
        array[j + 1] = temp

Python Implementation

def bubble_sort(array):
  for i in range(len(array)):
    for j in range(len(array) - 1):
      if array[j] > array[j + 1]:
        array[j], array[j + 1] = array[j + 1], array[j]

  return array

Insertion Sort

This algorithm sorts one data item at a time. One item is taken from the list, and placed in the correct position. This is repeated until there are no more unsorted items in the list. Example below:

9 5 4 15 3 8 11 2
5 9 4 15 3 8 11 2
4 5 9 15 3 8 11 2
4 5 9 15 3 8 11 2
3 4 5 9 15 8 11 2
3 4 5 8 9 15 11 2
3 4 5 8 9 11 15 2
2 3 4 5 8 9 11 15

Pseudocode

function insertionSort(array):
  for i = 1 to length(array):
    current = array[i]
    j = i - 1
    while j >= 0 and array[j] > current:
      array[j + 1] = array[j]
      j = j - 1
    array[j + 1] = current

Python Implementation

def insertion_sort(array):
  for i in range(1, len(array)):
    current = array[i]
    j = i - 1
    while j >= 0 and array[j] > current:
      array[j + 1] = array[j]
      j -= 1
    array[j + 1] = current

Merge Sort

Merge sort solves a sorting problem by dividing the list to be sorted into smaller sub-lists, recursively conquering each sub-list by sorting it, and then combining the conquered sub-lists in a specific way to ensure the overall list is sorted.

1. Split the list into individual items

39 17 24 43 12 8 48 31

2. Merge into pairs

17 39 24 43 8 12 31 48

3. Merge into sublists

17 24 39 43 8 12 31 48

4. Merge into final sorted list

8 12 17 24 31 39 43 48

Note: The split process has not been included in this example.

Pseudocode

mergeSort(array, left, right):
  if left < right:
    mid = (left + right) // 2
    mergeSort(array, left, mid)
    mergeSort(array, mid + 1, right)
    i = left
    j = mid + 1
    k = left
    while i <= mid and j <= right:
      if array[i] <= array[j]:
        temp[k] = array[i]
        i += 1
      else:
        temp[k] = array[j]
        j += 1
      k += 1
    while i <= mid:
      temp[k] = array[i]
      i += 1
      k += 1
    while j <= right:
      temp[k] = array[j]
      j += 1
      k += 1
    for i in range(left, right + 1):
      array[i] = temp[i]

Python Implementation

def merge_sort(array, left, right):
    if left < right:
        mid = (left + right) // 2
        merge_sort(array, left, mid)
        merge_sort(array, mid + 1, right)
        i = left
        j = mid + 1
        k = left
        temp = [0] * len(array)  # Create a temporary array to store merged elements

        while i <= mid and j <= right:
            if array[i] <= array[j]:
                temp[k] = array[i]
                i += 1
            else:
                temp[k] = array[j]
                j += 1
            k += 1

        while i <= mid:
            temp[k] = array[i]
            i += 1
            k += 1

        while j <= right:
            temp[k] = array[j]
            j += 1
            k += 1

        for i in range(left, right + 1):
            array[i] = temp[i]

Quick Sort

Pseudocode

procedure quick_sort(array, low, high)
    if low < high
        pivot = array[high]
        i = low - 1
        for j = low to high - 1
            if array[j] <= pivot
                i = i + 1
                swap array[i] and array[j]
            end if
        end for
        swap array[i + 1] and array[high]
        pivot = i + 1
        quick_sort(array, low, pivot - 1)
        quick_sort(array, pivot + 1, high)
    end if
end procedure

Python Implementation

def quick_sort(array, low, high):
    if low < high:
        pivot = array[high]
        i = low - 1
        for j in range(low, high):
            if array[j] <= pivot:
                i += 1
                array[i], array[j] = array[j], array[i]
        array[i + 1], array[high] = array[high], array[i + 1]
        pivot = i + 1
        quick_sort(array, low, pivot - 1)
        quick_sort(array, pivot + 1, high)

# Example usage:
array = [5, 2, 4, 1, 3]
quick_sort(array, 0, len(array) - 1)
print(array)  # Output: [1, 2, 3, 4, 5]

Sort Comparisons

Choosing the right sorting algorithm depends on your data size and needs. For small lists or partially sorted data, Insertion Sort shines, while Bubble Sort is simple but slow for larger datasets. Merge Sort reigns supreme for large datasets due to its speed, but it requires more memory. Think of them as tools: Insertion Sort for quick fixes, Bubble Sort for simple needs, and Merge Sort for heavy-duty tasks. Remember, the best algorithm depends on your specific situation!

© mrahmedcomputing. All rights reserved.

3