Bubble Sort (AQA GCSE Computer Science)
Revision Note
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 Tip
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!
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)
A bubble sort in python
# unsorted dataset
nums=[66, 7, 69, 50, 42, 80, 71, 321, 67, 8, 39]
# count the length of the dataset
numlength = len(nums)
# sets a flag to initiate the loop
swaps = True
while swaps == True :
swaps = False
# loop through the dataset
for y in range(numlength-1) :
# if the first number is bigger than the second number
if nums[y] > nums[y+1] :
# swap the numbers using a temporary variable
temp = nums[y]
nums[y] = nums[y+1]
nums[y+1] = temp
# sets the flag to true
swaps = True
# prints the sorted list
print (nums)
Last updated:
You've read 0 of your 10 free revision notes
Unlock more, it's free!
Did this page help you?