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

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

Leave a Reply

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