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
``````