Algorithms cheatsheet

Here goes a list of useful and common algorithms explained in a way that is easy to understand and beside their names I have written their average case runtimes. Reading this article should give you insights about which algorithm to use and how to implement it.

 

Binary search (O(log2(n)), works in place)

1. Let n = size of the array.

2. Let min = 0 and max = n - 1.

3. If max < min then stop, the target is not present in the array, return -1.

4. Calculate guess as floor((max + min) / 2).

5. If array[guess] equals the target then stop, you found it, return guess.

6. If array[guess] < the target then set min = guess + 1 and jump to step 8.

7. if array[guess] > the target then set max = guess - 1.

8. Go back to step 3.

Uniform binary search (O(log2(n)), works in place)

1. Let sizeArray be the size of the array we will search, now calculate the size of the lookup table with the formula size = ceil(log2(sizeArray)) + 1.

2. Now let i = 1.

3. Add the element Delta(i) = floor(sizeArray + 2 ^ (i - 1)) / 2 ^ i to the lookup table called midpoints.

4. Let i += 1 and if i > size then go to step 6.

5. Go back to step 3.

6. Then let i = 0 and mid = midpoints[0] - 1, you decrement 1 to make up for the fact they were calculated starting at 1 and not at 0.

7. If mid < 0 or mid >= sizeArray then the element is not here, return -1.

8. If array[mid] is equal to the target then return mid, you've found it.

9. If i equals size - 1 then we've reached the end of the midpoints and therefore the element isn't here, return -1.

10. If array[mid] < the target then let mid += midpoints[i + 1], otherwise let mid -= midpoints[i + 1].

11. Increment i and go back to step 7.

XOR swap (O(1), works in place)

1. Remember the word BABA.

2. B ^= A; A ^= B; B ^= A;

3. This is it, the values of A and B have been swapped. This algorithm has no advantages whatsoever over the traditional swap methods.

Deterministic quick sort (theta(nlog2(n)), works in place)

1. Call the function with the array passed by reference, create a variable begin = the index of the first element of the array and a variable end = index of the last element of the array.

2. Take the element array[end] as the pivot.

3. Create a variable called boundary = begin and another one called u = begin.

4. If u = end then skip to step 7.

5. If array[u] <= array[end] then swap array[u] with array[boundary] and increment boundary.

6. increment u and go back to step 4.

7. Swap array[end] with array[boundary].

8. If boundary > begin + 1 then call this quick sort function recursively with parameters (array, begin, end = boundary - 1).

9. If boundary < end - 1 then call this quick sort function recursively with parameters (array, boundary + 1, end).

Randomized Quick sort (theta(nlog2(n)), works in place)

The same algorithm as the Deterministic quick sort but you must go to the step 2 of the Deterministic quick sort algorithm and choose 3 random elements between the indices begin and end, get the median of those 3 and swap it with the rightmost element, so it is the pivot. This will give you a higher chance at getting a good split and you can use less than 3 elements to make it simpler or more than 3 elements to make this chance even higher. My experiments have shown it is fastest when you use an if statement to do it randomized only when the array size is at least 30, furthermore, using only 1 random element is faster than using 2, which is faster than using 3.

Merge sort (theta(nlog2(n)), doesn't work in place)

1. If the size of the array is <= 1 then skip to step 12.

2. Calculate the midpoint as the floor of the size of the array divided by 2.

3. Create a new array called lowerHalf which is equal to the return of the merge sort function on array[0 .. midpoint].

4. Create a new array called upperHalf which is equal to the return of the merge sort function on array[midpoint .. end].

5. Append a sentinel with a value equivalent to infinity to both the lowerHalf and the upperHalf arrays, this will prevent violating the array's bounds.

6. Create 3 integers, originalI, lowerI and upperI to keep track of the indices of the original array, the lowerHalf array and the upperHalf array, respectively, they all start with the value 0.

7. If originalI >= length of array then skip to step 12.

8. If lowerHalf[lowerI] <= upperHalf[upperI] then make array[originalI] = lowerHalf[lowerI], otherwise skip to step 10.

9. Increment both originalI and lowerI, then go back to step 7.

10. Make array[originalI] = upperHalf[upperI].

11. Increment both originalI and upperI, then go back to step 7.

12. Return the array.

Insertion sort (theta(n^2), works in place)

1. Let i = 1.

2. If i is >= the length of the array then stop because you have reached the end, meaning it is now sorted.

3. Let key = array[i]. The variable i will mark the unsorted part boundary and key will be the first element of the unsorted part.

4. Let j = i - 1. j will be used to check all the elements in the already sorted part, we descend the list until we find where to put key.

5. If array[j] > key then make array[j + 1] = array[j]. We push the elements up to make room for key in front of them.

6. If array[j] <= key then make array[j + 1] = key, i++ and go back to step 2. Here you have found where to put key and then we move up the boundary that separates the sorted part from the unsorted part.

7. Decrement j, we will now check the next element down the list.

8. If j is equal to -1 then make array[0] = key, increment i and then go back to step 2. In this case key had to go in the very beginning.

9. Go back to step 5.

Selection sort (theta(n^2), works in place)

1. Let i = 0.

2. If i is equal to the length of the array - 1 then stop, you're done.

3. Let minIndex = i and j = i + 1.

4. If array[j] < array[minIndex] then minIndex = j.

5. Let j += 1.

6. If j is equal to the length of the array then swap the values of array[i] and array[minIndex], then increment i and go back to step 2.

7. Go back to step 4.

Bubble sort (theta(n^2), works in place)

1. Let i = 1.

2. If i >= length of the array then stop, you're done.

3. Let j = 0.

4. If array[j] > array[j + 1] then swap their values.

5. Increment j, if j is equal to the length of the array - i then increment i and go back to step 2.

6. Go back to step 4.

Counting sort (theta(R + N), doesn't work in place)

1. R is the limit of the range of numbers (if the biggest number is 6, then R is 7) and N is the size of the array.

2. Create an array called equals with a length equal to R and set all values to 0.

3. Let key = the next number in the array.

4. Increment equals[key], that way you will store how many times each element appears in the array.

5. If you haven't reached the end of the array then go back to step 3.

6. Create an array called smallers with a length equal to R and set the first value to 0.

7. Create i = 1.

8. Do smallers[i] = equals[i - 1] + smallers[i - 1], that way you will be counting how many numbers come before each key in the array.

9. If i < R then increment i and go back to step 8.

10. Now create a new array result with the length equal to N.

11. Now make i = 0.

12. Make key = array[i] and then make index = smallers[key].

13. Then make result[index] = key and increment smallers[key].

14. If i < N then increment i and go back to step 12.

15. Return result, which is now sorted in a stable way.

16. This algorithm only works when the array only contains integers.

Radix sort (theta(R + N), doesn't work in place)

1. This algorithm is useful when you are sorting an array of equal size strings, such as ["K1E", "R3T", "Y7U"], R is the range of values for each character and N is the size of the array. In this case R would be 36 because we have 10 digits + 26 characters.

2. Make i = size of a string, in this case i = 3.

3. Create a new array result with length N.

4. Apply the counting sort algorithm above to the array, but only take into consideration the character in the index i - 1, meaning the rightmost character, insert the elements in result.

5. If i = 0 then the array result is now sorted in a stable way, return it.

6. Decrement i, make the original array = result and go back to step 4.

Breadth-first search (O(|V| + |E|))

1. Start with all vertices having their distance = infinity. Choose the origin vertex and set its distance to 0, its predecessor to null and make it the current vertex.

2. Create a queue with only the current vertex in it.

3. Visit all adjacent vertices of the current.

4. If the adjacent vertex's distance <= current vertex's distance + edge's weight, then skip to step 8.

5. Set the adjacent vertex's distance to be the current vertex's distance + the edge's weight.

6. Set the adjacent vertex's predecessor to be the current vertex.

7. Enqueue the adjacent vertex.

8. Once you are done with all adjacent vertices you should dequeue the current vertex.

9. If the queue is empty, then you are done, skip to step 11.

10. Choose the first element of the queue as the current vertex and go back to step 3.

11. Make the current vertex be the destination vertex and create a result list.

12. Add the current vertex to the result list.

13. If the current vertex is the origin then just return the result list and skip the next step.

14. Make the current vertex be its predecessor and go back to step 12.

Sierpinski gasket (theta(3^(log2(window's width))))

1. Define a function called sierpinski(int left, int top, int right, int bottom, Window window).

2. In the main() function you create a square window, for example a 1000x1000 window.

3. Call the sierpinski() function by passing the window along with its dimensions as arguments, as in sierpinski(0, 0, 1000, 1000, window).

4. From now on we are inside the sierpinski() function and we will use the arguments left, top, right and bottom to draw the lines and rectangles.

5. If right - left <= 5 or bottom - top <= 5 then we have reached the base case, draw a square (left, top, right, bottom), fill it with a color and skip the next steps.

6. Create the variables widthMiddle = (right - left) / 2 and heightMiddle = (bottom - top) / 2.

7. Draw a line from point (left, top + heightMiddle) to point (right, top + heightMiddle).

8. Draw a line from point (left + widthMiddle, top) to point (left + widthMiddle, bottom).

9. Recursively call the sierpinski() function with the arguments (left, top, left + widthMiddle, top + heightMiddle, window).

10. Recursively call the sierpinski() function with the arguments (left + widthMiddle, top, right, top + heightMiddle, window).

11. Recursively call the sierpinski() function with the arguments (left + widthMiddle, top + heightMiddle, right, bottom, window).

Middle squares method (theta(n))

1. Create an empty list of numbers and choose a random number to be the seed.

2. Create a variable seedLength = the number of digits in the seed.

3. Add the seed to the list of numbers.

4. Let squared = the seed ^ 2.

5. If the length of squared is <= seedLength (it happens if the middle number was very small), then make the seed = squared and skip to step 7.

6. Pick the digits in the middle of squared, the number of digits must be equal to the length of the seed, for example, if the seed was 704, then squared = 495616, therefore you will pick 561 (49[561]6) to be the next seed. Notice you find the middle point to the right, not to the left.

7. If the seed is neither 0 nor a number which is already in the list, then you haven't reached the period yet, go back to step 3.

8. Return the list of numbers.

Notes

1. In order of fastest to slowest sorting algorithm we have: Quick Sort > Merge Sort > Insertion Sort > Selection Sort > Bubble Sort.

2. There are some variations of Quick Sort, the randomized version is faster than the deterministic version in worst case scenarios, but slower in the average scenarios. You can make it much faster by creating a hybrid which uses Insertion Sort on the array pieces that have few elements.

3. The existential lower bound for comparison sorting algorithms is omega(nlog2(n)) and the universal lower bound for all sorting algorithms is omega(n).

4. If the recursive algorithm is taking too long then use memoization, it should make it faster.

5. Bottom-up approach is when you start with the smallest value and iteratively use it to calculate up until the target value.

6. You can use Dynamic Programming every time you have optimal substructure and overlapping subproblems.

7. Divide and conquer can be summed up as 3 steps: divide (split it in subproblems), conquer (solve the subproblems) and combine (join the subresults to solve the original problem).

8. When using a pseudorandom number generator you should use a seed of at least 10 digits so it will look truly random.

9. The Middle Squares Method is very limited, the period is usually very small even if you use a very big seed.