O LevelComputer ScienceCambridge (CIE)Revision Notes7. Algorithm Design & Problem-SolvingStandard Methods of a SolutionLinear Search & Bubble Sort

Linear Search & Bubble Sort (Cambridge (CIE) O Level Computer Science)

Revision Note

Test yourselfFlashcards
Robert Hampton

Written by: Robert Hampton

Reviewed by: James Woodhouse

What is a searching algorithm?

  • Searching algorithms are precise step-by-step instructions that a computer can follow to efficiently locate specific data in massive datasets

  • A linear search starts with the first value in a dataset and checks every value one at a time until all values have been checked

  • A linear search can be performed even if the values are not in order

Step

Instruction

1

Check the first value

2

IF it is the value you are looking for

  • STOP!

3

ELSE move to the next value and check

4

REPEAT UNTIL you have checked all values and not found the value you are looking for

Examiner Tips and Tricks

You will not be asked to perform a linear search on a dataset in the exam, you will be expected to understand how to do it and know the advantages and disadvantages of performing it

A linear search in Pseudocode

# Identify the dataset, target value, and set the initial flag
DECLARE data : ARRAY[1:5] OF INTEGER 
DECLARE target : INTEGER 
DECLARE found : BOOLEAN 

data ← [5, 2, 8, 1, 9]
target ← 11
found ← FALSE

# Loop through each element in the data
FOR index ← 1 TO 5 DO
    IF data[index] = target THEN
        # If found, output message
        found ← TRUE
        OUTPUT "Target found"
        BREAK
    ENDIF
NEXT index

# If the target is not found, output a message
IF found = FALSE THEN
    OUTPUT "Target not found"
ENDIF

A linear search in Python code

# Identify the dataset to search, the target value and set the initial flag
data = [5, 2, 8, 1, 9]
target = 11
found = False

# Loop through each element in the data
for index in range(0, len(data)):  # loop to go through all elements
    # Check if the current element matches the target
    if data[index] == target:
        # If found, output message
        found = True
        print("Target found")
        break  # Exit the loop if the target is found

# If the target is not found, output a message
if not found:
    print("Target not found")

Bubble Sort

What is a sorting algorithm?

  • Sorting algorithms are precise step-by-step instructions that a computer can follow to efficiently sort data in massive datasets

What is a bubble sort?

  • A bubble sort is a simple sorting algorithm that starts at the beginning of a dataset and checks values in 'pairs' and swaps them if they are not in the correct order

  • One full run of comparisons from beginning to end is called a 'pass', a bubble sort may require multiple 'passes' to sort the dataset

  • The algorithm is finished when there are no more swaps to make

How do you perform a bubble sort?

Step

Instruction

1

Compare the first two values in the dataset

2

IF they are in the wrong order...

  • Swap them

3

Compare the next two values

4

REPEAT step 2 & 3 until you reach the end of the dataset (pass 1)

5

IF you have made any swaps...

  • REPEAT from the start (pass 2,3,4...)

6

ELSE you have not made any swaps...

  • STOP! the list is in the correct order

7-3-standard-methods-standard-methods-02

Example

  • Perform a bubble sort on the following dataset

5

2

4

1

6

3

Step

Instruction

1

Compare the first two values in the dataset

5

2

4

1

6

3

2

IF they are in the wrong order...

  • Swap them

2

5

4

1

6

3

3

Compare the next two values

2

5

4

1

6

3

4

REPEAT step 2 & 3 until you reach the end of the dataset

  • 5 & 4 SWAP!

2

4

5

1

6

3

  • 5 & 1 SWAP!

2

4

1

5

6

3

  • 5 & 6 NO SWAP!

2

4

1

5

6

3

  • 6 & 3 SWAP!

2

4

1

5

3

6

  • End of pass 1

5

IF you have made any swaps...

  • REPEAT from the start

  • End of pass 2 (swaps made)

2

1

4

3

5

6

  • End of pass 3 (swaps made)

1

2

3

4

5

6

  • End of pass 4 (no swaps)

1

2

3

4

5

6

6

ELSE you have not made any swaps...

  • STOP! the list is in the correct order

Examiner Tips and Tricks

In the exam you do not have to show every swap that takes place in a bubble sort. You can show the outcome of a bubble sort at the end of each pass. If you have the outcome of each pass correct then a bubble sort has been implemented correctly and all marks will be given!

A bubble sort in Pseudocode

# Unsorted dataset
DECLARE nums : ARRAY[1:11] OF INTEGER 
nums ← [66, 7, 69, 50, 42, 80, 71, 321, 67, 8, 39]

# Count the length of the dataset
DECLARE numlength : INTEGER 
numlength ← 11

# Set a flag to initiate the loop
DECLARE swaps : BOOLEAN 
swaps ← TRUE

WHILE swaps DO  # While any swap is made, continue
    swaps ← FALSE
    # Loop through the dataset
    FOR y ← 1 TO numlength - 1 DO
        IF nums[y] > nums[y + 1] THEN  # If the first number is bigger
            # Swap the numbers
            DECLARE temp : INTEGER 
            temp ← nums[y]
            nums[y] ← nums[y + 1]
            nums[y + 1] ← temp
            swaps ← TRUE  # Mark that a swap was made
        ENDIF
    NEXT y
    # Each iteration confirms that the last element is in place
    numlength ← numlength - 1
ENDWHILE

# Print the sorted list
OUTPUT nums

A bubble sort in Python code

# Unsorted dataset
nums = [66, 7, 69, 50, 42, 80, 71, 321, 67, 8, 39]

# Count the length of the dataset
numlength = len(nums)

# Set a flag to initiate the loop
swaps = True

while swaps:  # While any swap is made, continue
    swaps = False
    # Loop through the dataset
    for y in range(numlength - 1):  # Compare adjacent elements
        if nums[y] > nums[y + 1]:  # If the first number is bigger
            # Swap the numbers using a temporary variable
            nums[y], nums[y + 1] = nums[y + 1], nums[y]
            swaps = True  # Mark that a swap was made

    # Each iteration confirms that the last element is in place
    numlength -= 1

# Print the sorted list
print(nums)

Worked Example

A program uses a file to store a list of words.

A sample of this data is shown

Milk

Eggs

Bananas

Cheese

Potatoes

Grapes

Show the stages of a bubble sort when applied to data shown  [2]

How to answer this question

  • We need to sort the values in to alphabetical order from A-Z

  • You CAN use the first letter of each word to simplify the process

Answer

  • E, B, C, M, G, P (pass 1)

  • B, C, E, G, M, P (pass 2)

Last updated:

You've read 0 of your 5 free revision notes this week

Sign up now. It’s free!

Join the 100,000+ Students that ❤️ Save My Exams

the (exam) results speak for themselves:

    Test yourselfFlashcards

    Did this page help you?

    Previous:Explaining AlgorithmsNext:Other Standard Methods of a Solution
    Author
    Reviewer
    Robert Hampton

    Author: Robert Hampton

    Expertise: Computer Science Content Creator

    Rob has over 16 years' experience teaching Computer Science and ICT at KS3 & GCSE levels. Rob has demonstrated strong leadership as Head of Department since 2012 and previously supported teacher development as a Specialist Leader of Education, empowering departments to excel in Computer Science. Beyond his tech expertise, Robert embraces the virtual world as an avid gamer, conquering digital battlefields when he's not coding.

    James Woodhouse

    Author: James Woodhouse

    Expertise: Computer Science

    James graduated from the University of Sunderland with a degree in ICT and Computing education. He has over 14 years of experience both teaching and leading in Computer Science, specialising in teaching GCSE and A-level. James has held various leadership roles, including Head of Computer Science and coordinator positions for Key Stage 3 and Key Stage 4. James has a keen interest in networking security and technologies aimed at preventing security breaches.