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

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)

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

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

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)