1.3: Searching & Sorting Algorithms
Exam Board:
OCR
Specification:
2020
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 many data items can be ignored.
However, the list of data must already be sorted in order before a binary search can take place.
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.
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.
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]
Watch on YouTube
Watch on YouTube
Watch on YouTube
Watch on YouTube