Edexcel IAL - Decision Mathematics 1- 1.2 Sorting and Searching Algorithms- Study notes - New syllabus
Edexcel IAL – Decision Mathematics 1- 1.2 Sorting and Searching Algorithms -Study notes- New syllabus
Edexcel IAL – Decision Mathematics 1- 1.2 Sorting and Searching Algorithms -Study notes -Edexcel A level Maths- per latest Syllabus.
Key Concepts:
- 1.2 Sorting and Searching Algorithms
Standard Algorithms
Students are expected to be familiar with the ideas and operation of several standard algorithms. The emphasis is on understanding how the algorithms work and being able to follow or implement them when given in words, pseudocode, or flow-chart form.
Analysis of efficiency or order of algorithms is not required.
Bin Packing
Bin packing is a problem-solving algorithm used to place items of different sizes into containers (bins) of fixed capacity, using as few bins as possible.
A commonly used approach is the first-fit method:
- Items are considered one at a time in a given order
- Each item is placed into the first bin that has enough remaining space
- If no existing bin can hold the item, a new bin is opened
Bin packing is often used in scheduling, storage, and resource allocation problems.
Bubble Sort
Bubble sort is a simple sorting algorithm that repeatedly steps through a list, comparing adjacent items and swapping them if they are in the wrong order.
The process continues until no swaps are needed, indicating that the list is sorted.
Key features:
- Only adjacent elements are compared
- Larger values gradually move (“bubble”) towards the end of the list
- Multiple passes through the list are required
Bubble sort is easy to understand but inefficient for large lists.
Quick Sort
Quick sort is a divide-and-conquer sorting algorithm.
In this syllabus, the pivot must always be chosen as the middle item of the list, using the glossary definition of the middle item.
Procedure:
- Select the middle item as the pivot
- Rearrange the list so that all items less than the pivot are placed to the left, and all greater items to the right
- Apply the same process recursively to each sub-list
The algorithm finishes when all sub-lists contain only one item.
Binary Search
Binary search is an efficient searching algorithm used to find a specific item in a sorted list.
Procedure:
- Compare the target value with the middle item of the list
- If equal, the search is complete
- If smaller, repeat the search on the left half of the list
- If larger, repeat the search on the right half of the list
The process continues until the item is found or the list is empty.
Binary search is fast but only works on sorted lists.
Important Notes for Examinations
- Students must be able to follow and apply these algorithms step by step
- The pivot in quick sort must always be the middle item as defined in the glossary
- No analysis of algorithm efficiency is required
Example
Items of sizes
6, 4, 7, 3, 5
are to be packed into bins of capacity 10 using the first-fit algorithm.
▶️ Answer / Explanation
Bin 1:
Place 6 → remaining space 4
Place 4 → bin full
Bin 2:
Place 7 → remaining space 3
Place 3 → bin full
Bin 3:
Place 5 → remaining space 5
Conclusion: The algorithm uses 3 bins.
Example
Use bubble sort to arrange the list
7, 2, 5, 3
in ascending order.
▶️ Answer / Explanation
Pass 1:
7 and 2 → swap → 2, 7, 5, 3
7 and 5 → swap → 2, 5, 7, 3
7 and 3 → swap → 2, 5, 3, 7
Pass 2:
2 and 5 → no swap
5 and 3 → swap → 2, 3, 5, 7
Pass 3:
No swaps needed
Conclusion: The sorted list is 2, 3, 5, 7.
Example
Use quick sort to sort the list
9, 4, 7, 1, 6
The pivot must be chosen as the middle item.
▶️ Answer / Explanation
Number of items \( \mathrm{N = 5} \)
Middle position \( \mathrm{\dfrac{1}{2}(5+1) = 3} \)
Pivot: 7
Partition:
Left: 4, 1, 6
Right: 9
Apply quick sort to left sub-list:
Middle of (4,1,6) is 1 → pivot = 1
Left: —
Right: 4, 6
Sorted result:
1, 4, 6, 7, 9
Conclusion: The list is correctly sorted using the required pivot rule.
Example
Use binary search to find the value 18 in the sorted list
4, 7, 10, 13, 18, 21, 25
▶️ Answer / Explanation
Number of items \( \mathrm{N = 7} \)
Middle position \( \mathrm{\dfrac{1}{2}(7+1) = 4} \)
Middle item = 13
Since \( \mathrm{18 > 13} \), search the right half:
18, 21, 25
New middle position = 2
Middle item = 18
Conclusion: The item 18 is found successfully.