1.3: Searching & Sorting Algorithms
Exam Board:
OCR
Specification:
J277
Key features of a bubble sort:
-
Uses an outer while loop (condition controlled) to check no swaps have been made.
-
Uses an inner for loop (count controlled) to repeat through the length of the data set.
-
Uses a flag (a Boolean value) to track if a swap has been made and uses a temporary value to help correctly swap elements.
Linear Search
A linear search is the most simple search algorithm.
​
Each data item is searched in order from the first value to the last as if they were all laid out in a line.
The list does not have to be in any order before it is searched. This search is also known as a sequential search because the list is searched in a sequence from start to end.
For large lists, this search is not very efficient.
Binary Search
A binary search is a much more efficient searching algorithm as it generally searches through fewer data and is often much quicker - especially for large data sets.
In a binary search, the middle point of the data is selected with each iteration and compared to the value being searched for. When the midpoint matches the target value, it as been found and the search can stop.
! ! However there is a prerequisite of using a binary search - the list of data must already be sorted. A prerequisite is a condition that must be satisfied before an algorithm will work correctly.
Merge Sort
Merge sort is a sorting algorithm based on the idea of ‘divide and conquer’.
A merge sort divides a list into half, again and again until each data item is separate.
Then the items are combined in the same way as they were divided, but now in the correct order.
When the individual lists are all merged together as one list again, then the data is in order and the algorithm will end.
Bubble Sort
This algorithm is based on the comparison of adjacent data elements.
​
Data elements are swapped if they are not in the correct order.
The algorithm will only stop when a complete iteration through the data is completed with no swaps made.
​
A bubble sort is not suitable for large sets of data.
Insertion Sort
The list is logically split into sorted values (on the left) and unsorted values (on the right).
​
Starting from the left, values from the unsorted part are checked and inserted at the correct position in the sorted part.
​
This continues through all elements of the list until the last item is reached, and sorted.
Insertion sorts are efficient for small data sets but would be slow to sort large sets, compared to alternatives such as a merge sort.
Key features of a linear search:
-
A loop is used to check the first value in a list and increment by 1, checking each value for a match to the target.
-
Reaching the last element of the list without finding a match means the value is not included.
Key features of a binary search:
-
A midpoint, lowpoint and highpoint are calculated.
-
A while loop is used to repeatedly compare the midpoint to a target value.
-
The upper half or lower half of the data is ignored if the midpoint does not equal the target.
Key features of a merge sort:
-
This algorithm calls itself from within the subroutine (this is known as a recursive algorithm).
-
It continually splits sublists into a left side and a right side until each sublist has a length of 1.
Watch on YouTube
Watch on YouTube
Watch on YouTube
Watch on YouTube
Key features of a insertion sort:
-
Uses an outer for loop (count controlled) to iterate through each value in the list.
-
Uses an inner while loop (condition controlled) to find the current value’s correct position in the sorted part of the list.
-
An insertion sort moves ‘backwards’ to find the correct position of each value, by decreasing the index within the while loop.
Questo's Questions
1.3 - Searching & Sorting Algorithms:
​
Linear Search
Explain step-by-step how the number 8 would be found in the following list using a linear search:
12, 5, 3, 2, 8, 19, 14, 6 [4]
​
Binary Search
Explain step-by-step how the number 2 would be found in the following list using a binary search:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10 [6]
​
Merge Sort
Explain step-by-step how a merge sort would sort the following list of numbers:
4, 8, 5, 1, 3, 6, 7, 2 [6]
​
Bubble Sort
Explain step-by-step how a bubble sort would sort the following list of numbers:
3, 1, 6, 5, 2, 4 [6]
​
Insertion Sort
Explain step-by-step how an insertion sort would sort the following list of numbers:
5, 2, 6, 3, 1, 4 [6]