Visualizing Sorting Algorithms

This post contains initial experimental visualizations of the bubble , insertion , and quick sort algorithms.

I'm interesting in showing all the mechanics inherent to each implementation, such as the movement of indices, and the recursive open/close of function calls.

This project is still in development!

Bubble Sort

The bubble sort:

    def bubblesort(A):
        last_i = len(A)-1;
        while last_i > 0:
            for i in range(0,last_i+1):
                if A[i] > A[i+1]:
                    swap(A,i,i+1)
            last_i -= 1

Above i is the green dot , and last_i is the purple dot . The inverted gray "v" is the compartor of the if A[i] > A[i+1] line.

Bubble sort is very simple to understand, but also very inefficient as it makes every comparison, and time to execute is always O(n ² ). Next we look at a slight improvement, the insertion sort.

Insertion Sort

The insertion sort:

    def sort(A):
        n = len(A)
        for pos in range(1,n-1):
            insert(A,pos,A[pos])

    def insert(A, pos, value):
        i = pos - 1
        while i >=0 and A[i] > value:
            A[i+1] = A[i]
            i = i - 1
        A[i+1] = value

This visualization is definitely not quite finished yet! I need to add a comparator visualization and explain better what is going on.

Quick Sort

The quick sort using the Lomuto Partition :

And the reference source in python:

    # The main methods
    def quicksort(A, l, r):
        if l < r:
            pivot = partition(A,l,r)
            quicksort(A,l,pivot-1)
            quicksort(A,pivot+1,r)

    def partition(A, l, r):
        pivot_val = A[r]
        i = l
        for j in range(l,r):
            if A[j] < pivot_val:
                if i != j:
                    swap(A,i,j)
                i += 1
        if i != r:
            swap(A,i,r)
        return i

    # Running it
    arr = [ 7, 13, 4, 5, 8, 2 ]
    quicksort(arr, 0, len(arr)-1)

Conclusion

These sorting algorithms are a first step towards visualizing more complex algorithms from other areas of computer science.

I'm hoping to visualize some graph and spatial tree structures soon!

Appendix

Quicksort in javascript:

    // The main methods
    function quicksort(A, l, r){
        if(l < r){
            let pivot = partition(A,l,r);
            quicksort(A,l,pivot-1);
            quicksort(A,pivot+1,r);
        }
    }

    function partition(A, l, r){
        let pivot_val = A[r],
            i = l;
        for(let j = l; j < r; j++){
            if(A[j] < pivot_val){
                if(i!=j){
                    swap(A,i,j);
                }
                i += 1;
            }
        }
        if(i != r){
            swap(A,i,r);
        }
        return i;
    }

    // Running it
    let arr = [ 7, 13, 4, 5, 8, 2 ];
    quicksort(arr, 0, arr.length-1);