Bubble & Merge Sort
Unit 3 Summary - part 5
There are Many Types of Sorting
Pay attention to the top left corner of this video
Bubble Sort
Sorts from the left, one item at a time.
When it's done, it starts sorting from the left again, one item at a time.
-
Advantage: Simple and easy to code
-
Disadvantage: Slow to sort if there are many items in the list.
If Bubble Sort were made into a folk dance,
it would look like this:
Merge Sort
Keeps on dividing the list into two, and then merge the parts together.
-
Advantage: Very fast to sort if there are many items in the list.
-
Disadvantage: More complicated to code, so it takes up more storage space.
If Merge Sort were a folk dance,
it would be entertaining:
BUBBLE SORT CODING
One Comparison
This coding will compare the first item with the second item only and then swap them:
One Pass
This coding will compare items from left to right, and swap them, one time (one pass) only.
The highest/biggest number will be placed at the end of the list.
Keep Passing
This coding will compare items from left to right, and swap them, and will repeat until all numbers are fully sorted.
Big O Notation
Oxford AQA IGCSE 2019
07.
Figure 5 shows a list of numbers that will be sorted from smallest to largest using the box bubble sort algorithm so that the smallest number will be at the left-hand end.
Figure 5
07.1.
Complete Table 1 to show the results of pass 2 and pass 3 of the bubble sort algorithm through the list from Figure 5.
The results of pass 1 and pass 4 have been completed for you. [2 marks]
Table 1
07.2.
Why will the bubble sort algorithm complete another pass, even though the list is sorted after four passes? [1 mark]
__________________________________________________________________________________
Alternative answers:
-
To check that the list is fully sorted;
-
Six (list length -1) passes are needed to guarantee that the items are sorted
-
Because there needs to be a pass through the list when no swaps were made (in order to know that the list is sorted)
07.3.
For each statement tick one box to indicate if the statement is true or false. [2 marks]
Answers:
-
False;
-
True
