Algorithms

Front 1

Insertion Sort

Back 1

for i = 1 to end

x = a[i]

j = i - 1

while a[j] > x and j >= 0

a[j+1] = a[j]

j--

end while

a[j] = x

end for

Best: O(n) (array in order)

Worst: O(n^2) (array in reverse)

Average: O(n^2)

Very bad for large arrays because average time is O(n^2)

Very good for small arrays

and when array is nearly sorted (because algorithm is adaptive)

Front 2

Merge Sort

Back 2

Break array up into single element lists

Combine them into 2s, then 4s, etc

smallest elements first of which ever two are being combined

Worst/Best/Average Case: O(nlogn)

Good for linked lists because the algorithm operates sequentially, plus it is easy to break apart/combine nodes

Front 3

Bucket Sort

Back 3

Create n number of buckets

Add each element to appropriate bucket

Sort the elements in each bucket

Combine the buckets

Best: O(n + k) (k is number of buckets)

Worst: O(n^2)

Average: O(n + k)

Implemented with insertion sort because of the small lists

Good when array is distributed into buckets evenly

Bad when all elements are in the same bucket

Front 4

Quick Sort

Back 4

Best: O(nlogn)

Worst: O(n^2)

Average: O(nlogn)

Good for when data is very unsorted

Good for when you care about average performance

Front 5

Heap Sort

Back 5

Build Max Heap

Swap first element with last

MaxHeapify

HeapSort(0, n- 1)

BuildMaxHeap

for i = floor(n/2) to 0

MaxHeapify

Best: O(nlogn)

Worst: O(nlogn)

Average: O(nlogn)

Good for when you care about worst-case performance

Front 6

Dynamic Programming

Back 6

Used to find optimal solution

Represents time vs. memory tradeoff

Front 7

Local Alignment

Back 7

Strings differ in length, short patches of similarity

Front 8

Global Sequence

Back 8

Good for same length strings which are similar throughout

Front 9

Needleman Wunsch = LCS if..

Back 9

g = 0

s(xi, yj) = 1 if xi = yj

s(xi, yj) = -∞ if xi ≠ yj

Front 10

Radix Sort

Back 10

Sort by LSD or MSD

if there is a tie, whichever comes first in array wins

Performance: O(kN)

Good for integers and fixed size strings

Front 11

Counting Sort

Back 11

Find min and max value

Create array of length max - min

Create array that holds count of each number

Create sumcount array which is runsum of count

Put each number in array associated with occurence in sumcount

For example if 12 has sum count of 5, 12 goes in position 5