LS

10.2 Linear Search & Bubble Sort

Searching values in 1D arrays using Linear Search and sorting elements using Bubble Sort algorithm

Learning Objectives

By the end of this lesson, you will be able to:

  • Implement Linear Search algorithm to search for a value in a 1D array
  • Explain how Linear Search works step by step
  • Implement Bubble Sort algorithm to sort elements in a 1D array
  • Describe how Bubble Sort compares and swaps adjacent elements
  • Trace through algorithms using trace tables
  • Compare the efficiency of Linear Search and Bubble Sort
  • Identify appropriate loop structures for searching and sorting tasks

Key Terms

Linear Search

Searching algorithm that checks each element in sequence until the target is found

Bubble Sort

Sorting algorithm that repeatedly compares adjacent elements and swaps them if they're in wrong order

Array

Data structure that stores multiple values of the same type in contiguous memory locations

Index

Position of an element within an array, usually starting from 0 or 1

Swap

Operation that exchanges the positions of two elements

Pass

One complete iteration through all elements in an array during sorting

Flag (Boolean)

Variable that indicates whether a condition has been met (TRUE/FALSE)

REPEAT...UNTIL Loop

Loop that executes at least once and continues until a condition becomes true

FOR...NEXT Loop

Count-controlled loop that executes a specific number of times

Bubble Sort

Bubble Sort is a simple sorting algorithm that repeatedly compares adjacent elements and swaps them if they're in the wrong order. Each pass through the array places the next largest element in its correct position.

How Bubble Sort Works

Step-by-Step Process

1

Compare 1st and 2nd values. If 1st > 2nd, swap them

2

Compare 2nd and 3rd values. If 2nd > 3rd, swap them

3

Continue comparing adjacent values until last two

4

After first pass, largest value is at the end

5

Repeat process, ignoring already sorted elements

6

Stop when no more swaps are needed

Key Concepts

Pass

One complete iteration through the array (or unsorted portion)

Swap

Exchange positions of two elements that are in wrong order

NoMoreSwaps Flag

Boolean variable that tracks if any swaps occurred in a pass

Optimization

After each pass, the largest element is in correct position, so we can ignore it next time

Why "Bubble" Sort?

Large values "bubble up" to their correct positions, like bubbles rising in water.

Pseudocode Implementation

n ← MaxIndex – 1

REPEAT
NoMoreSwaps ← TRUE
FOR j ← 0 TO n
IF MyList[j] > MyList[j + 1]
THEN
Temp ← MyList[j]
MyList[j] ← MyList[j + 1]
MyList[j + 1] ← Temp
NoMoreSwaps ← FALSE
ENDIF
NEXT j
n ← n – 1
// next time round the inner loop, we don't look at sorted positions
UNTIL NoMoreSwaps = TRUE

Bubble Sort Simulator

Watch how Bubble Sort compares adjacent elements and swaps them if they're in the wrong order.

Original: [42, 17, 8, 31, 25, 13, 19]
Current Pass: 1
Comparisons: 0
Swaps: 0
Ready to sort...

How it works: Bubble Sort makes multiple passes through the array. In each pass, it compares adjacent elements and swaps them if they're in the wrong order. After each pass, the largest unsorted element "bubbles up" to its correct position at the end.

Real-Life Example: Organizing Students by Height

Imagine you need to line up 7 students in order from shortest to tallest (but you can only compare two adjacent students at a time):

Pass 1: Compare student 1 & 2, swap if wrong order. Then compare 2 & 3, swap if needed. Continue to end. Tallest student ends up at the end.
Pass 2: Repeat comparisons, but ignore the last student (already tallest). Second tallest ends up in position 6.
Pass 3: Repeat, ignoring last two students. Third tallest in position 5.
Continue until all students are in order or no swaps are needed.

This is exactly how Bubble Sort works! It's simple but not very efficient for large groups.

Activity 2: Trace Through Bubble Sort

Given the array: [25, 17, 42, 13, 8]

  1. Show the array after the first pass of Bubble Sort
  2. Show the array after the second pass
  3. How many passes are needed to fully sort this array?
  4. How many comparisons are made in the first pass?
  5. How many swaps occur in total?
Solution:
  1. After first pass:
    Compare 25 & 17: swap → [17, 25, 42, 13, 8]
    Compare 25 & 42: no swap → [17, 25, 42, 13, 8]
    Compare 42 & 13: swap → [17, 25, 13, 42, 8]
    Compare 42 & 8: swap → [17, 25, 13, 8, 42]
    Result: [17, 25, 13, 8, 42]
  2. After second pass:
    Compare 17 & 25: no swap → [17, 25, 13, 8, 42]
    Compare 25 & 13: swap → [17, 13, 25, 8, 42]
    Compare 25 & 8: swap → [17, 13, 8, 25, 42]
    (Ignore last element)
    Result: [17, 13, 8, 25, 42]
  3. Passes needed: 4 passes (for 5 elements, worst case needs n-1 passes)
  4. Comparisons in first pass: 4 comparisons (comparing indices 0-1, 1-2, 2-3, 3-4)
  5. Total swaps: 6 swaps (3 in pass 1, 2 in pass 2, 1 in pass 3, 0 in pass 4)

Exam Style Question

ESQ: An array contains 100 integer values. An algorithm will find the maximum and minimum values stored in the array.

(a) A programmer has started to write this program using a conditional loop. Name a more appropriate loop structure for this task and justify your choice.

Name: count controlled / FOR...NEXT loop
Justification: Known / fixed number of iterations // all elements of array need to be checked.

(b) Outline steps program will need to follow to implement algorithm. Do not write pseudocode or program code.

1. Apply a sort routine to the values in the array
2. Swapping consecutive elements (as necessary) // until no more swaps
3. Min will be the first / last element and max will be the last / first element

Check Your Understanding: Bubble Sort

Answer
  • [1 mark] To detect when the array is fully sorted (no swaps were made in a complete pass)
  • [1 mark] It makes the algorithm more efficient by stopping early if the array becomes sorted before all passes are completed
  • [Additional] Initialized to TRUE at start of each pass, set to FALSE if any swap occurs
Answer
  • [1 mark] To reduce the range of the inner loop after each pass
  • [1 mark] Because after each pass, the largest element is in its correct position at the end, so we don't need to check it again
  • [Additional] This optimization makes the algorithm slightly more efficient
Answer
  • [1 mark] (n-1) + (n-2) + ... + 1 comparisons
  • [1 mark] Which is n(n-1)/2 comparisons
  • [Additional] For example, for 100 elements: 100×99/2 = 4950 comparisons in worst case
Answer
  • [1 mark] To temporarily store the value of MyList[j] before overwriting it
  • [1 mark] Without Temp, we would lose the original value when we do MyList[j] ← MyList[j + 1]
  • [Additional] This is a standard three-step swap: Temp ← A, A ← B, B ← Temp
Answer
  • [1 mark] With the NoMoreSwaps flag, it will make only one pass
  • [1 mark] It will make n-1 comparisons but 0 swaps, then stop
  • [Additional] This is the best-case scenario for Bubble Sort

Key Takeaways

  • Linear Search checks each element sequentially until the target is found or all elements are checked
  • Linear Search efficiency: Best case: 1 comparison, Worst case: n comparisons, Average case: n/2 comparisons
  • Bubble Sort repeatedly compares adjacent elements and swaps them if they're in wrong order
  • Bubble Sort efficiency: Worst case: O(n²) comparisons and swaps, Best case (with flag): O(n) comparisons
  • NoMoreSwaps flag makes Bubble Sort more efficient by stopping early when array is sorted
  • REPEAT...UNTIL loops are useful when we need to execute at least once and stop when condition is met
  • FOR...NEXT loops are appropriate when number of iterations is known/fixed
  • Swap operation requires a temporary variable to hold one value during exchange
  • Array indexing typically starts at 0 (0:6 means indices 0 through 6, total 7 elements)
  • Boolean flags (like Found, NoMoreSwaps) are essential for controlling loop execution
  • Algorithm tracing involves step-by-step execution to understand how algorithms work
  • Linear Search works on both sorted and unsorted arrays
  • Bubble Sort is simple but inefficient for large datasets compared to other sorting algorithms

Question Bank

Marking Scheme & Answer
  • [1 mark] Linear Search: Works on both sorted and unsorted arrays. Checks each element sequentially.
  • [1 mark] Binary Search: Only works on sorted arrays. Repeatedly divides search interval in half.
  • [1 mark] Use Linear Search when: Array is small or unsorted, or when searching infrequently.
  • [1 mark] Use Binary Search when: Array is large and sorted, and frequent searches are needed.
  • [Additional] Linear Search: O(n) time complexity. Binary Search: O(log n) time complexity.
Marking Scheme & Answer
  • [1 mark] Index 0: Compare 10 with 42 → not equal
  • [1 mark] Index 1: Compare 25 with 42 → not equal
  • [1 mark] Index 2: Compare 8 with 42 → not equal
  • [1 mark] Index 3: Compare 42 with 42 → equal, found at index 3
  • [Additional] Found flag set to TRUE, search terminates, output "Value found at location: 3"
Marking Scheme & Answer
  • [1 mark] Bubble Sort only requires a constant amount of additional memory space
  • [1 mark] It sorts the array by swapping elements within the original array, without creating a separate copy
  • [Additional] The only extra memory needed is for the Temp variable used in swaps, and a few control variables
Marking Scheme & Answer
  • [1 mark] Worst-case time complexity is O(n²)
  • [1 mark] For n elements, it makes (n-1) passes
  • [1 mark] In each pass i, it makes (n-i) comparisons
  • [Additional] Total comparisons = (n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ n²/2, which is O(n²)
Marking Scheme & Answer
DECLARE Count, Index : Integer
INPUT SearchValue
Count ← 0
FOR Index ← 0 TO MaxIndex
IF MyList[Index] = SearchValue
THEN
Count ← Count + 1
ENDIF
NEXT Index
OUTPUT "Value appears " Count " times"
Marking Scheme & Answer
  • [1 mark] Its time complexity is O(n²), which becomes very slow as n increases
  • [1 mark] For large arrays, more efficient algorithms like QuickSort or MergeSort (O(n log n)) are much faster
  • [Additional] Example: For 1000 elements, Bubble Sort needs ~500,000 comparisons, while QuickSort needs ~10,000
Marking Scheme & Answer
  • [1 mark] Change the comparison condition in the IF statement
  • [1 mark] Instead of IF MyList[j] > MyList[j + 1], use IF MyList[j] < MyList[j + 1]
  • [Additional] This will swap when the left element is smaller, causing larger elements to move left instead of right
Marking Scheme & Answer
  • [1 mark] Original: [5, 1, 4, 2, 8]
  • [1 mark] Pass 1: Compare 5-1(swap), 5-4(swap), 5-2(swap), 5-8(no) → [1, 4, 2, 5, 8]
  • [1 mark] Pass 2: Compare 1-4(no), 4-2(swap), 4-5(no) → [1, 2, 4, 5, 8] (ignore last)
  • [1 mark] Pass 3: Compare 1-2(no), 2-4(no) → [1, 2, 4, 5, 8] (no swaps)
  • [1 mark] Result: Sorted array [1, 2, 4, 5, 8]
Marking Scheme & Answer
  • [1 mark] Standard Linear Search stops at the first occurrence it finds
  • [1 mark] It returns the index of the first matching element and doesn't check the rest
  • [Additional] To find all occurrences, you would need to modify the algorithm to continue searching after finding a match
Marking Scheme & Answer
  • [1 mark] [1,2,3,4,5] (already sorted): 0 swaps (with NoMoreSwaps flag, stops after 1 pass)
  • [1 mark] [5,4,3,2,1] (reverse sorted): Maximum number of swaps
  • [1 mark] For reverse sorted: 4+3+2+1 = 10 swaps (worst case)
  • [Additional] This shows Bubble Sort's performance varies greatly depending on initial order