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

### Key Steps

- Gist: Using a
**pivot**value, recursively split the array (or segments of array) and its resultant halves, where all the elements in left half is smaller than the pivot and all the elements in the right half is larger - 3 steps: stop condition, partition, recursion
- Stop condition
- Check if the given left index is strictly smaller than the given right index
- If they are equal, it means we are dealing with 1 element and there’s nothing to sort
- Left index should not and will not be more than the right index

- Partition
- The key here is to
**return a partition index** **Randomly**select element and use element value as pivot (**pivot index is ignored**)- Left and right index will traverse towards center
**Stop incrementing left**index when its value is**greater than or equal pivot**value**Stop decrementing right**index when its value is**smaller than or equal pivot**value- Swap the values and continue traversing
**Ensure left <= right**(this logic should be hoisted to the top)- Return the
**left index as the partition index** - This partition index will be the eventual midpoint of this subarray

- The key here is to
- Recursion
- Call itself twice
- One will use the given
**left**index and**partition index – 1** - The other will the given
**right**index the**partition index + 1**

- Stop condition

### Discussions

- Each iteration frees up 1 element
- For each element freed, quicksort is executed
`lg n`

times on average - Average time complexity is
`n lg n`

- Worst case is
`n^2`

, if the pivot is always the smallest/largest value, so need to be careful when choosing pivot - Randomize selection of pivot to effectively reduce probability of hitting worst case
**In place**sorting algorithm where no extra memory is needed and the operation can be carried out on the array itself

## Mergesort

### 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 3 parts in order: split, recursion, merge
- We will mutate the array, but it will not be an in place sorting. This is because it is difficult to do so.
- So first create an empty
of same size to`arrayCopy`

**temporarily hold the values of sections of the original array that are already sorted**to be overwritten into the corresponding section in the original array. - Split
- Given a subarray array, the
`arrayCopy`

, the**leftStart**and**rightEnd**of the subarray to be split - Continue splitting and duplicate a copy of the left half and the right half
**Stop condition**: Stop the current iteration if the given array is only 1 element and just return

- Given a subarray array, the
- Recursion
- Call itself on the left half
- Then call itself on the right half
- So the splitting will continue until we are dealing with 1 element to kick start the merge

- Merge
- Dealing with the
**same subarray from the split step**, provided with the`leftStart`

and`rightEnd`

of the subarray - The
`leftEnd`

and the`rightStart`

are at the**midpoint**of this subarray - These 4 key indices mirror the indices in the original array
- Traverse from
`leftStart`

to`leftEnd`

together from`rightStart`

to`rightEnd`

- Fill up the
`arrayCopy`

in ascending order - Ensure the indices do not overshoot its respective end
- Eventually, one half will have all its elements filled up in the
`arrayCopy`

, while the other half can simply append the remaining elements to the`arrayCopy`

from where it left off - The
`arrayCopy`

is sorted for that exact portion of the original array, so we will overwrite that portion of the original array with the same portion of the`arrayCopy`

*That portion of the original array may not be sorted in contemplation of its whole, but that will be addressed and its values overwritten in the subsequent merge steps.*

- Dealing with the

### Discussions

- Time complexity of
`n lg n`

even in worst case - Need extra
`n`

space for the array copy

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

### Key Steps

- Gist: keep
**swapping adjacent elements**if left is larger than right down the array, and repeat this iteration for as many time as there are elements in the array **End before the 2nd last index**so that we**do not go out of bound**when comparing the current element with the next for swapping- The largest elements starts forming at the end of the array
- Subsequent iterations can
**end before the already sorted section of the array at the end**as optimization - A flag reseted at each iteration can be used to end the function early if no swap is detected for the current iteration, which would mean the array is already sorted

### Discussions

- Time complexity is
`n^2`