Computational Thinking, Searching & Sorting Algorithms (OCR GCSE Computer Science): Revision Notes
Standard Sorting Algorithms
Sorting algorithms are used to arrange the elements of a list in a specific order, usually ascending or descending. The three standard sorting algorithms you need to know are Bubble Sort, Merge Sort, and Insertion Sort.
Bubble Sort
Bubble Sort compares adjacent items in the list and swaps them if they are in the wrong order. This process continues through the list until all the items are sorted.
Method
- Start by comparing the first two items in the list.
- If they are out of order, swap them.
- Move to the next pair (items 2 and 3) and repeat step 2.
- Continue until you reach the end of the list.
- Repeat the process for all items until no more swaps are needed (i.e., the list is sorted).
Worked Example
In the image below, the list is gradually sorted as adjacent items are compared and swapped when necessary. Blue indicates items being compared, and red shows the final sorted item.
Starting on the left, the pairs of items are compared and swapped if needed (in blue). We then move to the next pair and repeat until we get to the end of the list.
This is the first pass. The largest item will be at the end of the list after the first pass.
Red indicates the item is sorted.
This is repeated until all items are in order.
Key Points
- Simple to implement but inefficient for large lists.
- Best used when the list is small or nearly sorted.
- Requires n-1 passes for a list of length n.
Merge Sort
Merge Sort is a divide-and-conquer algorithm that splits a list into smaller sub-lists until each sub-list contains a single item. It then merges the sub-lists back together in order.
Method
- Divide the list into two halves.
- Repeat this process until each sub-list has only one item.
- Merge the sub-lists, sorting them as you go.
- Continue merging until the entire list is sorted.
Worked Example
The image below shows how the list is split into sub-lists and then merged in order until the entire list is sorted.
The list is split in half and this is repeated until you have sub-lists with only 1 item. The pairs of sub-lists are then merged together in order.
This is repeated until they are all merged in order
Key Points
- Efficient for large lists.
- Requires extra memory to store the sub-lists.
- Ideal for data that needs to be sorted quickly.
Insertion Sort
Insertion Sort builds the sorted list one item at a time by repeatedly taking the next unsorted item and inserting it into the correct position.
Method
- Start with the second item in the list.
- Compare it with the items before it and insert it into its correct position.
- Move to the next item and repeat the process until the whole list is sorted.
Worked Example
In the image, each red item is inserted into its correct position within the grey sorted portion of the list.
Each item is taken in turn starting from the left. The red item is taken and inserted into the correct position on the left side of the list.
You have 2 lists:
- The unsorted list to the right
- The sorted list to the left of the item. You repeat the steps until it is sorted
Key Points
- More efficient than Bubble Sort on small or nearly sorted lists.
- Uses less memory than Merge Sort.
- Simple to implement, but slow on large lists.
Comparing Bubble Sort, Merge Sort, and Insertion Sort
| Bubble Sort | Merge Sort | Insertion Sort |
|---|---|---|
| Compares pairs of items and swaps if needed. | Divides list into smaller sub-lists, then merges in order. | Inserts each item into its correct place. |
| Inefficient for large lists. | Efficient for large lists. | More efficient than Bubble Sort for small, nearly sorted lists. |
| Simple but slow. | Requires extra memory. | Uses less memory than Merge Sort. |
| Suitable for small, unsorted lists. | Best for large datasets. | Best for small, nearly sorted lists. |
Key Points to Remember
- Bubble Sort is the slowest and simplest, mostly used for small datasets or when checking if a list is already sorted.
- Merge Sort is the fastest and most efficient for large datasets but requires extra memory.
- Insertion Sort works well for small datasets or lists that are nearly sorted, using less memory than Merge Sort.