2.1 Searching and Sorting Algorithms

Linear search
Binary search
Bubble sort
Insertion sort
Merge sort

Linear search

In linear search, the algorithm starts by comparing the item at the first index with the item to be found. If equal, it will return the index. Otherwise, it will move onto the next index and compare that. This will continue in order until either the item is found or the end of the list is reached.

Used to search a list or array for a certain item and returns the index.
Can be used on unsorted lists.
Checks each item in turn one-by-one until the item is found.
If the item isn’t found a value of –1 is returned.
Not efficient for large lists although you might get lucky and the item could be in the first few you check.

Binary search

Binary search takes a sorted array and removes half of it over and over again until the search item is found.

The array must be sorted.
Uses three pointers — low, mid and high.
A mid point is found and a logical test is made to decide whether the item is less than, greater than or equal to the mid point.
If less than or greater than, half the array is discounted by moving either the low or high pointer. This repeats until the mid point = the item found.
Much faster for large lists than linear search but array must be sorted first.

Bubble sort

A bubble sort involves looping through every item in an array.
Each item is compared to the one to its right. If they are in the wrong order they swap.
A variable needs to be used to store whether or not there were any swaps in a pass. When there are no swaps the algorithm ends.
Each pass the largest value will “bubble” to the right. This means it is not necessary to check this number again.
Bubble sort is a very slow sort and there is no reason to use it other than for academic purposes. The only advantage is that some may find it slightly easier to implement than some other sorts.

Insertion sort

In an insertion sort we loop through the array from left to right.
For each index, we loop back to the left comparing each value as we go.
If the value is greater than the index we shift it right. This continues until we find the correct insertion point and the index in placed in the correct spot.
One iteration from left to right is enough to fully sort the array.
Insertion sort is generally much faster than bubble sort.

Merge sort

The array is divided in half over and over until each subset is 1 big.
A merge algorithm is performed on each pair of subsets until there is one, combined, sorted subset left.
Merge sort is significantly faster for large arrays than insertion or bubble sort.