Linear Search & Bubble Sort (Cambridge (CIE) IGCSE Computer Science)
Revision Note
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
Linear Search
What is a linear search?
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
How do you perform a linear search?
Step | Instruction |
---|---|
1 | Check the first value |
2 | IF it is the value you are looking for
|
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 Python code |
---|
# Identify the dataset to search, the target value and set the initial flag # Loop through each element in the data #If the target is not found, output a message |
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
Bubble Sort
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...
|
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...
|
6 | ELSE you have not made any swaps...
|
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
| ||||||||||||||||||||||||
2 | IF they are in the wrong order...
| ||||||||||||||||||||||||
3 | Compare the next two values
| ||||||||||||||||||||||||
4 | REPEAT step 2 & 3 until you reach the end of the dataset
| ||||||||||||||||||||||||
5 | IF you have made any swaps...
| ||||||||||||||||||||||||
6 | ELSE you have not made any swaps...
|
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 Python code |
---|
# unsorted dataset # count the length of the dataset # sets a flag to initiate the loop
# prints the sorted list |
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 10 free revision notes
Unlock more, it's free!
Did this page help you?