Sort Algorithms Cheatsheet

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

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

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 arrayCopy of same size to 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
  • 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.

Discussions

  •  Time complexity of n lg neven 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

Leave a Reply

Your email address will not be published. Required fields are marked *