The guide I wish I had starting out; this is very much a work in progress
Algorithms are a set of instructions for accomplishing a task. For those of you with a math background, they are essentially functions that are usually optimized to be as efficient as possible, and often do useful things.
There are always trade-offs to be made, but this will be more clear with time.
Bhargava, in Grokking Algorithms, gives a fantastic example of why Binary Search is useful. Let’s say two friends were playing a guessing game.
Alice tells Bob she is thinking of a number between 1 and 100, inclusive, and wants Bob to guess her number. She is only allowed to tell Bob if his guess is too low, too high, or correct. What would be a quick way for Bob to guess?
The simple way would be for him to guess randomly. A smarter approach would be binary search. Bob is smart, so he uses binary search.
Bob starts at 50. Alice says he’s too high. He therefore eliminates 50% of his range.
Then he guesses 25. Bob now eliminates a further 50% of his range. Alice says he’s too low.
Bob now guesses 38. Alice says he’s too high.
I hope this make sense. Binary search is an efficient way of approaching this.
It has a worst case runtime of $log n$. But it only works when the list is sorted.
Here’s Python code that does just this:
def binary_search(arr, key): least_index = 0 highest_index = len(arr) - 1 while least_index <= highest_index: // that would be a terminating condition mid = (least_index + highest_index)/2 if arr[mid] == key: return mid elif arr[mid] > key: // we're too high, let's lower our highest index highest_index = mid - 1; else: // we're too low, let's increase our lowest index lowest_index = mid + 1; return None
This should be self-explanatory.
( O(n^2) ) running time
Pseudo code: def selection_sort(arr): for each element in the array. Find the lowest element in the array starting from index i + 1 if that element is lower than this element, swap them. Else move on.
Code: def selection_sort(arr): for i in range(len(arr)): index_of_lowest_ahead = findLowest(i, arr) if arr[index_of_lowest_ahead] < arr[i]: swap(i, index_of_lowest_ahead)
def findLowest(i, arr): min = arr[i] index = i for j in range(i, len(arr)): if arr[j] < min: min = arr[j] index = j return index def swap(i, j): temp = arr[j] arr[j] = arr[i] arr[i] = temp