Here we will be diving into learning how different algorithms work, in particular Searching and Sorting Algorithms. Over the Computational thinking course, you will realise that the core fundamentals of every coursework requires some sort of sorting or searching algorithmic knowledge. If you understand the basics that we teach today you will have a good 'foundation' for starting next year.
We will be looking at 2 different searching algorithms: Linear Search and Binary Search. Each search has its own advantages and disadvantages and its own pre-requisite requiremtnts, Lets start with Linear Search!
Linear Search is one of the simplest searching algorithms. It works by checking each element in a list until it finds the target value or reaches the end of the list. Lets go through an example!
[5, 2, 8, 1, 9]
Target: 8
[5, 2, 8, 1, 9]
Is 5 = 8? No.
[5, 2, 8, 1, 9]
Is 2 = 8? No.
[5, 2, 8, 1, 9]
Is 8 = 8? Yes!
So we found our target value at index 2 after only 3 comparisons! not bad but lets look at a bigger list and see how it performs.
| [1, 2, 4, 8, 3, 83, 2, 3, 94, 9, 22, 84, 93, 3 |
| 89, 3, 2, 1, 38, 4, 30, 4, 2, 3, 5, 34, 23, 2 |
| 54, 4, 54, 2, 32, 5, 6, 34,..., 23, 3, 2, 1, 99, 3] |
Target: 99
In this example we can see that if you were to use linear search, you would have to check every single element in the list until you find the target value at the very end, proving why it is very inefficient for large lists. This is where Binary Search comes in!
Binary Search is a more efficient searching algorithm that works only on sorted lists. It repeatedly divides the search interval in half until it finds the target value or determines that it is not present. Lets go through an example!
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Target: 7
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
since there are 10 elements and 9 indexes, the middle element is at index 4 or element 5, which is 5.
Is the target value 7 less than, greater than, or equal to the middle element (5)?
7 is greater than 5.
[6, 7, 8, 9, 10]
Is the target value 7 less than, greater than, or equal to the middle element (8)?
7 is less than 8.
[6, 7]
Is the target value 7 less than, greater than, or equal to the middle element (7)? 7 is equal to 7 therefore we eliminate the left half of the list and found our target!.
So we found our target value at index 6 after only 3 comparisons! This is much more efficient than linear search for large sorted lists.
Bubble Sort is a simple sorting algorithm that repeatedly steps through a list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.
[3, 23, 9, 1, 8]
[3, 23, 9, 1, 8]
Is 3 > 23?
No. leave it as is.
[3, 23, 9, 1, 8]
Is 23 > 1?
Yes. Swap them.
[3, 9, 23, 1, 8]
[3, 9, 23, 1, 8]
Is 23 > 1?
Yes. Swap them.
[3, 9, 1, 23, 8]
[3, 9, 1, 23, 8]
Is 23 > 8?
Yes. Swap them.
[3, 9, 1, 8, 23]
Second Pass:
[3, 9, 1, 8, 23]
[3, 1, 9, 8, 23]
[3, 1, 8, 9, 23]
Third Pass:
[1, 3, 8, 9, 23]
Merge Sort is a divide-and-conquer algorithm that divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves.
[3, 23, 9, 10, 5, 1, 8, 12]
So we divide the list into [3, 23, 9, 10] and [5, 1, 8, 12]. We then divide those lists into [3], [23], [9], [10] and [5], [1], [8], [12].
[3, 23, 9, 10, 5, 1, 8, 12]
[3, 23, 9, 10] [5, 1, 8, 12]
{ [3], [23] } { [9], [10] } , { [5], [1] } { [8], [12] }
So we compare 3 and 23, add 3 to the merged list, then compare 23 and 9, add 9 to the merged list, then compare 23 and 10, add 10 to the merged list, then add 23 to the merged list. We do the same for the other half of the list and then merge those two sorted halves together.
{ [3], [23] } { [9], [10] } , { [1], [5] } { [8], [12] }
{ [3, 9, 10, 23] }, { [1, 5, 8, 12] }
[1, 3, 5, 8, 9, 10, 12, 23]