Show understanding of insertion sort and bubble sort methods

19.1 Algorithms

Learning objective

Show understanding of the following algorithms, including their operation, step‑wise refinement, structured English, flow‑charts, efficiency (time & space), stability, best/average/worst‑case behaviour and typical use‑cases:

• Linear search
• Binary search
• Insertion sort
• Bubble sort

---

1 Search algorithms

1.1 Linear search

Identifier	Type	Purpose
A[]	array of comparable items	data set to be searched
n	integer	number of elements in A
key	same type as A[]	value being looked for
i	integer	loop index
found	boolean	set to true when the key is located

Structured English

SET found ← FALSE
FOR i FROM 0 TO n‑1 DO
    IF A[i] = key THEN
        SET found ← TRUE
        EXIT FOR
    END‑IF
END‑FOR

Flow‑chart

Pseudocode

found ← false
FOR i ← 0 TO n‑1
    IF A[i] = key THEN
        found ← true
        BREAK
    END IF
END FOR

Step‑wise refinement

1. Initialise found to false.
2. Examine each element of the array in order:
   • Compare the current element with key.
   • If they are equal, set found to true and terminate the loop.
3. When the loop finishes, found indicates whether the key exists.

Complexity analysis

• Best case (key is the first element): Θ(1)
• Average & worst case (key absent or at the end): Θ(n)
• Space: O(1) (in‑place)
• Stability: not applicable (search does not reorder data)

When to use

Small or unsorted data sets where a simple linear scan is acceptable. It is also the first algorithm introduced to develop algorithmic thinking.

---

1.2 Binary search (iterative)

Identifier	Type	Purpose
A[]	sorted array	data set to be searched
n	integer	size of A
key	same type as A[]	value being looked for
low, high	integer	current interval limits
mid	integer	middle index of the interval
found	boolean	result flag

Structured English

SET low ← 0, high ← n‑1, found ← FALSE
WHILE low ≤ high AND NOT found DO
    SET mid ← (low + high) DIV 2
    IF A[mid] = key THEN
        SET found ← TRUE
    ELSE IF A[mid] < key THEN
        SET low ← mid + 1
    ELSE
        SET high ← mid – 1
    END‑IF
END‑WHILE

Flow‑chart

Pseudocode

found ← false
low ← 0
high ← n‑1
WHILE low ≤ high AND NOT found
    mid ← (low + high) DIV 2
    IF A[mid] = key THEN
        found ← true
    ELSE IF A[mid] < key THEN
        low ← mid + 1
    ELSE
        high ← mid - 1
    END IF
END WHILE

Step‑wise refinement

1. Set the search interval to the whole array: [low,high] = [0,n‑1].
2. Repeat while the interval is non‑empty and the key has not been found:
   • Compute the middle index mid.
   • Compare A[mid] with key.
   • If they match, set found to true; otherwise discard the half that cannot contain the key.
3. When the loop ends, found tells whether the key was present.

Complexity analysis

• Best case (key is the middle element): Θ(1)
• Average & worst case: Θ(log n) comparisons.
• Space: O(1) (iterative version); O(log n) for the recursive version (call stack).
• Stability: not applicable.

When to use

When the data is already sorted and fast look‑ups are required. It exemplifies divide‑and‑conquer and logarithmic time.

---

2 Sorting algorithms

2.1 Insertion sort

Identifier	Type	Purpose
A[]	array of comparable items	data to be sorted
n	integer	size of A
i, j	integer	loop indices
key	same type as A[]	element currently being inserted

Structured English

FOR i FROM 1 TO n‑1 DO
    SET key ← A[i]
    SET j ← i‑1
    WHILE j ≥ 0 AND A[j] > key DO
        SET A[j+1] ← A[j]          /* shift larger element right */
        SET j ← j‑1
    END‑WHILE
    SET A[j+1] ← key                /* insert key */
END‑FOR

Flow‑chart

Pseudocode

FOR i ← 1 TO n‑1
    key ← A[i]
    j ← i‑1
    WHILE j ≥ 0 AND A[j] > key
        A[j+1] ← A[j]
        j ← j‑1
    END WHILE
    A[j+1] ← key
END FOR

Step‑wise refinement

1. Initialise the sorted portion to the first element (A[0]).
2. Select key: take the element at position i.
3. Shift phase: move each element of the sorted part that is larger than key one position to the right.
4. Insert phase: place key into the vacated slot (j+1).
5. Repeat steps 2‑4 for i = 1 … n‑1.

Complexity analysis

• Best case (already sorted): Θ(n) – one comparison per outer iteration.
• Average & worst case: Θ(n²) comparisons and moves.
• Space: O(1) (in‑place).
• Stability: stable – equal elements retain their original order.

Typical use‑cases

• Very small data sets (generally < 20 elements).
• Nearly sorted inputs where the number of inversions is low.
• Final “clean‑up” phase of hybrid algorithms such as Timsort or Introsort.

Recursive version (A‑Level extension)

FUNCTION InsertionSortRecursive(A, n)
    IF n ≤ 1 THEN RETURN
    CALL InsertionSortRecursive(A, n‑1)      // sort first n‑1 items
    key ← A[n‑1]
    j ← n‑2
    WHILE j ≥ 0 AND A[j] > key
        A[j+1] ← A[j]
        j ← j‑1
    END WHILE
    A[j+1] ← key
END FUNCTION

The recursive calls use O(log n) stack space; the algorithm remains in‑place and stable.

---

2.2 Bubble sort

Identifier	Type	Purpose
A[]	array of comparable items	data to be sorted
n	integer	size of A
i	integer	index for the inner loop
swapped	boolean	detects whether a pass made any exchanges

Structured English

SET swapped ← TRUE
WHILE swapped DO
    SET swapped ← FALSE
    FOR i FROM 0 TO n‑2 DO
        IF A[i] > A[i+1] THEN
            SWAP A[i] WITH A[i+1]
            SET swapped ← TRUE
        END‑IF
    END‑FOR
END‑WHILE

Flow‑chart

Pseudocode

do
    swapped ← false
    for i ← 0 TO n‑2
        if A[i] > A[i+1] then
            swap A[i] and A[i+1]
            swapped ← true
        end if
    end for
while swapped

Step‑wise refinement

1. Set swapped to true to guarantee at least one pass.
2. Enter the outer while loop:
   • Reset swapped to false.
   • Scan the array from left to right (inner for loop). For each adjacent pair, swap if they are out of order and set swapped to true.
3. If a complete pass makes no swaps, swapped stays false and the algorithm terminates.

Complexity analysis

• Best case (already sorted, early‑exit flag active): Θ(n).
• Average & worst case: Θ(n²) comparisons and swaps.
• Space: O(1) (in‑place).
• Stability: stable – swaps occur only between adjacent elements.

Typical use‑cases

• Educational demonstrations of sorting concepts.
• Very tiny data sets where implementation simplicity outweighs performance.
• Lists that are almost sorted, allowing the early‑exit optimisation to achieve linear time.

Recursive version (optional A‑Level extension)

FUNCTION BubbleSortRecursive(A, n)
    IF n = 1 THEN RETURN
    FOR i ← 0 TO n‑2
        IF A[i] > A[i+1] THEN
            SWAP A[i] WITH A[i+1]
        END IF
    END FOR
    CALL BubbleSortRecursive(A, n‑1)   // largest element now at position n‑1
END FUNCTION

Each recursive call reduces the unsorted portion by one, giving a recursion depth of n and O(n) stack space.

---

3 Algorithm‑comparison matrix (search + sort)

Algorithm	Category	Best‑case	Average‑case	Worst‑case	Space	Stability	Typical use‑case
Linear search	Search	Θ(1)	Θ(n)	Θ(n)	O(1)	N/A	Unsorted or very small data sets; introductory teaching.
Binary search	Search	Θ(1)	Θ(log n)	Θ(log n)	O(1) (iterative) / O(log n) (recursive)	N/A	Fast look‑ups in a sorted collection.
Insertion sort	Sort	Θ(n)	Θ(n²)	Θ(n²)	O(1)	Stable	Very small or nearly sorted lists; final phase of hybrid sorts.
Bubble sort	Sort	Θ(n)	Θ(n²)	Θ(n²)	O(1)	Stable	Teaching tool; tiny or almost‑sorted data sets where simplicity matters.