Exam code:J277
What is a sorting algorithm?
-
In GCSE Computer Science, sorting algorithms are precise step-by-step instructions that a computer can follow to sort data in massive datasets efficiently
-
Three common sorting algorithms are:
-
Bubble sort
-
Merge sort
-
Insertion sort
-
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 |
Instructions |
|---|---|
|
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
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!
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)Merge Sort
What is a merge sort?
-
A merge sort is a sorting algorithm that uses the ‘divide and conquer‘ strategy of dividing a dataset into smaller sub-datasets and merging them back together in the correct order
How do you perform a merge sort?
|
Step |
Instruction |
|---|---|
|
1 |
Divide the dataset into individual datasets by repeatedly splitting the dataset in half (DIVIDE) |
|
2 |
Merge pairs of sub-datasets together by comparing the first value in each dataset (CONQUER) |
|
3 |
REPEAT step 2 until all sub-datasets are merged together into one dataset |
Example
-
Perform a merge sort on the following dataset
Examiner Tips and Tricks
In the exam, the divide stage could already be done for you and you would only need to demonstrate the conquer stage!
Insertion Sort
What is an insertion sort?
-
The insertion sort sorts one item at a time by placing it in the correct position of an unsorted list. This process repeats until all items are in the correct position
-
Values in the dataset can move as many places as they need
How do you perform an insertion sort?
|
Step |
Instruction |
|---|---|
|
1 |
Take the first value in the dataset, this is now the sorted list |
|
2 |
Look at the next value in the dataset and compare it to the first value IF it is smaller
|
|
3 |
ELSE
|
|
4 |
REPEAT steps 2 & 3 until all values in the dataset have been compared, the list should now be in order |
Example
-
Perform an insertion sort on the following dataset
Responses