# Sort Algorithms Cheatsheet

This is a summary of the key features that make up an algorithm.

## Motivation

While it is easy to understand the concept of each sort algorithm, I find it difficult for me to remember the key steps that define an algorithm or is characteristic of that algorithm. That key step may prove to be pivotal in solving the algorithm but may come in as insignificant from the macro view of its concept.

Hence, I decided that it will be better for me to jot the key pointers down.

## Quicksort

```
def quicksort array
recursion(array, 0, array.length - 1) #IMPT
array
end
def recursion array, start, finish
if start < finish # IMPT
pivot_index = partition(array, start, finish)
recursion(array, start, pivot_index - 1) # IMPT
recursion(array, pivot_index + 1, finish) # IMPT
end
end
def partition array, start, finish
pivot = array[finish]
pivot_index = start
(start...finish).each do |index| # IMPT
if array[index] <= pivot # NOTE
array[index], array[pivot_index] =
array[pivot_index], array[index]
pivot_index += 1
end
end
array[finish], array[pivot_index] =
array[pivot_index], array[finish]
pivot_index
end
```

### Key Steps

Gist: Using a pivot value, distribute the array into 2 halves that are not ordered, but are collectively smaller on the left side and collectively larger on the right side.

The array is mutated.

The pivot value of each iteration will find its rightful position in the array at every iteration, eventually leading to a sorted array.

### Discussions

Let’s start with the recursion function.

In the recursion function, note that the arguments are indices of the array, not the length. Keep this at the back of your mind so that you can understand when to end a loop.

Line 7 ensures we are iterating at least 2 elements.

In lines 9 and 10, the recursion occurs on either side of the pivot index in that iteration. Note that the pivot index does not participate in the next recursion, since it is already at where it belongs.

Now for the partition function.

In the partition function, the pivot does not participate in the reordering. Line 18 ensures the loop ends before reaching the last index, finish, which is the pivot, with the non-inclusive range constructor operator.

In the loop in line 18, we are are trying to push the values smaller than or equal to the pivot to the left here. It is also ok to use <.

We do so by swapping them with those that are bigger than the pivot, but exist on the left of those that are smaller.

The pivot_index increments at each swap and remembers the last position that was swapped. Hence, at the end of the loop, it holds the position of the first value that is bigger than the pivot. Everything on the left is either smaller than or equal to the pivot.

This is where the pivot belongs to in the array. We swap the pivot into that position. Ascend the throne!

The state of the array does not change in this last swap: all elements on the left of the pivot is still smaller or equal to the pivot, while all elements on the right of the pivot is still bigger than the pivot. They remain unsorted

The function returns the pivot’s position to the parent recursion function, which needs it to know where to split the array for the next iteration.

Lastly, let’s go back to the calling function where the initial recursion function is triggered. Make sure to pass in the last index of the array instead of its length.

## Mergesort

```
def merge_sort(list)
return list if list.length <= 1
mid = list.length / 2
left = merge_sort(list[0...mid])
right = merge_sort(list[mid...list.length])
merge(left, right)
end
def merge(left, right)
return right if left.empty?
return left if right.empty?
if left.first <= right.first
[left.first] + merge(left[1...left.length], right)
else
[right.first] + merge(left, right[1...right.length])
end
end
```

### Key Steps

Gist: first recursively halve array until we are dealing with 1 element, then recursively merge the elements back in a sorted order until we get back the array of the same size, and now it will be sorted

A recursive function that consist of 2 parts in order: recursively split and recursively merge

The array will be mutated

In lines 16 and 18, we are continuously appending the smaller of the first element on the right vs left array.

Lines 11 and 13 will take care of the comparison that is still ongoing, when 1 side has been fully appended while the other still have elements inside. Since these arrays are already sorted at whichever iteration, we can just append the whole array.

Remember the breaking function in line 2

Unfortunately, while this use of recursion is great, the number of recursions may become too excessive and cause a “stack level too deep” error.

We may need to to think prepare an alternative if the stack overflows.

```
def merge_sort(list)
return list if list.length <= 1
mid = list.length / 2
left = merge_sort(list[0...mid])
right = merge_sort(list[mid...list.length])
merge(list, left, right)
end
def merge(array, left, right)
left_index = 0
right_index = 0
index = 0
while left_index < left.length &&
right_index < right.length
if left[left_index] <= right[right_index]
array[index] = left[left_index]
left_index += 1
else
array[index] = right[right_index]
right_index += 1
end
index += 1
end
array[index...index + left.length - left_index] =
left[left_index...left.length]
array[index...index + right.length - right_index] =
right[right_index...right.length]
array
end
```

Line 15 till 36 basically carry out the operation with a while loop instead of recursion. It mutates the array along the way.

## Insertion sort

### Key Steps

Gist: insert elements one by one from unsorted part of array into sorted part of array

Divide the array into sorted portion and unsorted portion

Sorted partition always starts from the first element, as array of 1 element is always sorted

First element of unsorted array will shift forward until the start of the sorted portion of the array OR until it meets an element bigger than itself

Order of the sorted portion is maintained

The last element of the sorted array takes its place

The next iteration start on the next element of the unsorted portion, which is now the first element of the current unsorted portion

The loop mutates the array

### Discussions

Best case is an already sorted array, so no shifting of elements from the unsorted to the sorted portion of the array, resulting in a time complexity of n

The worst case is a reverse sorted array, which results in the whole sorted array having to shift for each iteration. The first element of the unsorted portion of array is always at the the smallest and need to go to the front of the sorted portion. Time complexity is n^2

## Selection sort

### Key Steps

Gist: scan array to find the smallest element and eliminate it for the next iterations

Swap smallest element with the front most element

Scan the array in the next iteration excluding the smallest element(s)

Last remaining single element will be of the largest value, so iterations take place until n - 2

### Discussions

Time complexity is n^2

## Bubble sort

```
def bubble_swap array
swap_took_place = true
while swap_took_place
swap_took_place = false
(0...array.length - 1).each do |index|
if array[index] > array[index + 1]
array[index + 1], array[index] =
array[index], array[index + 1]
# increment swaps here to record
# number of swaps that took place
swap_took_place = true
end
end
end
array
end
```

### Key Steps

Gist: keep swapping adjacent elements if left is larger than right down the array, and repeat this iteration for as many times as there are elements in the array. The last iteration will not have any swap occur to declare the array swapped.

### Discussions

Time complexity is n^2