A-Level Computer Science - 19.1 Algorithms

Objective: Understanding Insertion Sort and Bubble Sort

Introduction

Algorithms are step-by-step procedures for solving a problem. This section focuses on two fundamental sorting algorithms: Insertion Sort and Bubble Sort. These algorithms are often used for educational purposes due to their simplicity, although they are not the most efficient for large datasets.

1. Insertion Sort

Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It iterates through the input array, taking each element and inserting it into its correct position in the already sorted portion of the array.

How Insertion Sort Works

1. Start with the second element of the array (index 1).
2. Compare the current element with the elements in the sorted portion to its left.
3. If the current element is smaller than an element in the sorted portion, shift the larger element to the right.
4. Repeat this process until the correct position for the current element is found.
5. Move to the next unsorted element and repeat the process.

Pseudocode

function insertionSort(array)
  for i from 1 to length(array) - 1 do
    key = array[i]
    j = i - 1
    while j >= 0 and array[j] > key do
      array[j + 1] = array[j]
      j = j - 1
    end while
    array[j + 1] = key
  end for

Example

Consider the array: {5, 2, 4, 6, 1, 3}

The Insertion Sort process would be:

1. {5, 2, 4, 6, 1, 3} - Insert 2 into {5} -> {2, 5, 4, 6, 1, 3}
2. {2, 5, 4, 6, 1, 3} - Insert 4 into {2, 5} -> {2, 4, 5, 6, 1, 3}
3. {2, 4, 5, 6, 1, 3} - Insert 6 into {2, 4, 5} -> {2, 4, 5, 6, 1, 3}
4. {2, 4, 5, 6, 1, 3} - Insert 1 into {2, 4, 5, 6} -> {1, 2, 4, 5, 6, 3}
5. {1, 2, 4, 5, 6, 3} - Insert 3 into {1, 2, 4, 5, 6} -> {1, 2, 3, 4, 5, 6}

Time Complexity

The time complexity of Insertion Sort is:

• Best Case: $O(n)$ - When the array is already sorted.
• Average Case: $O(n^2)$
• Worst Case: $O(n^2)$ - When the array is sorted in reverse order.

2. Bubble Sort

Bubble Sort is another simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The largest element "bubbles" to the end of the list with each pass.

How Bubble Sort Works

The algorithm performs multiple passes over the list. In each pass, it compares adjacent elements and swaps them if they are in the wrong order. The largest element in the unsorted portion of the list "bubbles" to its correct position at the end of the unsorted portion.

Pseudocode

function bubbleSort(array)
  n = length(array)
  for i from 0 to n - 2 do
    for j from 0 to n - i - 2 do
      if array[j] > array[j + 1] then
        swap(array[j], array[j + 1])
      end if
    end for
  end for

Example

Consider the array: {5, 2, 4, 6, 1, 3}

The Bubble Sort process would be:

1. Pass 1: {5, 2, 4, 6, 1, 3} -> {2, 5, 4, 6, 1, 3} -> {2, 4, 5, 6, 1, 3} -> {2, 4, 5, 1, 6, 3} -> {2, 4, 1, 5, 6, 3} -> {2, 1, 4, 5, 6, 3} -> {1, 2, 4, 5, 6, 3}
2. Pass 2: {1, 2, 4, 5, 6, 3} -> {1, 2, 4, 5, 3, 6} -> {1, 2, 4, 3, 5, 6} -> {1, 2, 3, 4, 5, 6}

Time Complexity

The time complexity of Bubble Sort is:

• Best Case: $O(n)$ - When the array is already sorted.
• Average Case: $O(n^2)$
• Worst Case: $O(n^2)$ - When the array is sorted in reverse order.

Comparison of Insertion Sort and Bubble Sort

Feature	Insertion Sort	Bubble Sort
Approach	Builds sorted subarray incrementally	Repeatedly swaps adjacent elements
Number of Swaps	Generally fewer swaps	Potentially many swaps
Performance	More efficient for nearly sorted arrays	Less efficient overall
Space Complexity	$O(1)$ - In-place sorting	$O(1)$ - In-place sorting

Conclusion

Both Insertion Sort and Bubble Sort are simple to understand and implement. However, their $O(n^2)$ time complexity makes them inefficient for large datasets. More advanced sorting algorithms like Merge Sort and Quick Sort offer significantly better performance for larger inputs.