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

Sorting algorithms

Selection sort

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

Bubble sort

Insertion sort

Merge sort

Quick sort