Visualizing Sorting Algorithms (Part 2)

So this is expanding on some work on did for a prior blog found right here where I shuffled blocks of an image and reordered them using the bubble sort algorithm.

Now for this blog I wanted to expand out of the single algorithm I implemented and use selection sort (another bas iterative algorithm of O(n^2) like bubble sort), quick sort, and merge sort.

Insertion Sort

This was relatively simple to implement as for every element in the array, there is a corresponding search through the rest of the array to find the minimum element from there. This is really bad and really slow of an algorithm to implement but the code for me looked like:

export const selectionSort = (array, iterator, measure) => {
    let min = iterator;
    for (let i = iterator + 1; i < array.length; i++) {
        if (measure(array[i], array[min])) min = i
    }
    let t = array[min];
    array[min] = array[iterator];
    array[iterator] = t;
}

At this point my sketch file was growing wayyy too large so I decided to create a module for all the sorting algorithms I was using. Like last post, the draw function gets called over and over again in the sketch. That means the draw function will just act as the outer for loop and the correct element in the array will just be inserted as an argument. I tried to animate this as a loop but was having trouble using ccapture.js or other node gif encoders.

But I put the selection sort and bubble sort head to head right here so that you can see how they work against one another.

Quick Sort

So these were much more difficult to implement as they rely on recursion in some instances and the iterable solutions are pretty chunky compared to the recursive ones. Given that the draw function is our outer loop in these sorting algorithms a recursive approach is made much more complicated to implement.

However, I came across Daniel Shiffmans visualization algorithms on the coding train where his quick sort makes use of async and wait to have the draw function render the sorting while the recursion is happening in the background. This looked like:

export const quickSort = async (array, start = 0, end = array.length - 1) => {
    await sleep(10)
    if (start >= end) {
        return
    }
    let index = partition(array, start, end)
    await Promise.all([
        quickSort(array, start, index - 1),
        quickSort(array, index + 1, end)
    ])
}

const partition = (array, start, end) => {
    let pivotIndex = start;
    let pivotValue = array[end].index;
    for (let i = start; i < end; i++) {
        if (array[i].index < pivotValue) {
            swap(array, i, pivotIndex)
            pivotIndex++;
        }
    }
    swap(array, pivotIndex, end)
    return pivotIndex;
}
const swap = (array, i, j) => {
    let temp = array[i]
    array[i] = array[j]
    array[j] = temp
}
const sleep = (time) => new Promise(resolve => setTimeout(resolve, time))

This is a quicksort that uses the last element, for simplicity, as the pivot point and makes use of a sleep function to have the recursion wait rather than complete all at once. This is definitely some funky javascript and delays the sorting. It isn't all that helpful of a function to visualize as I think the async recursion doesn't demonstrate how the swapping is occurring.

The implementation that I did end up taking isn't exemplary of how quickly the algorithm sorts as the sleep asyncronously slows the process so it isn't insantaneous.

Merge Sort

Finally, I went with an iterable or bottom-up merge sort that increases by one left shift assignment so that we cover all integers in the log base 2 function.

const mergeSort = (array, m)  => {
    if (m < array.length) {
        var n = array.length, a1 = new Array(n);
          for (var i = 0; i < n; i += m << 1) {
            var left = i,
                right = Math.min(i + m, n),
                end = Math.min(i + (m << 1), n);
                merge(array, a1, left, right, end);
          }
        for (let i = 0; i < n; i++) {
            array[i] = a1[i]
        }
    }
  }

const merge = (a0, a1, left, right, end) => {
    for (var i0 = left, i1 = right; left < end; ++left) {
      if (i0 < right && (i1 >= end || a0[i0].index <= a0[i1].index)) {
        a1[left] = a0[i0++];
      } else {
        a1[left] = a0[i1++];
      }
    }
  }

I based my code on Mike Bostocks here. It starts by swapping individual elements, then merges adjacent arrays of 2 and then 4 and so on. Thereby proceeding bottom up until we merge the last two sorted arrays. This one, again, sorts wayyy faster than the bubble and selection sort algorithms.

In a case like this where there are 20x20 split blocks of the image being sorted which in the case of (n^2) meaning at worst 160,000 operations for the computer versus for quick and merge sort (O(nlogn)) giving at worst around 3,600 computations. This is a MASSIVE difference and very much reductive but illustrate how important it is to design algorithms that scale well.

Please check out the result at https://christianmkastner.com/algorithm-visualizer/ and the github repo