Sort Algorithm Visualizer

In general, sorting algorithms take an array of numbers, usually integers, and sort them in ascending(or descending) order.

This project is a web-app that visualizes 12+ common sorting algorithms using 1 dimensional data. It uses several interchangeable methods for linear data visualization.

Example of merge sort	Example of dual pivot quick sort	Example of tim sort	Example of radix sort

Table of contents

• Visualization Types
  • 2D
    • Scatter Plot
    • Swirl Dots
    • Disparity Dots
  • 3D
• Algorithms
  • Summary
  • Insertion Family
    • Insertion sort
    • Binary insertion sort
  • Merge family
    • Merge sort
  • Selection family
    • Selection sort
    • Heap sort
    • Ternary heap sort
  • Exchange family
    • Quick sort
    • Dual pivot quick sort
  • Non-comparison family
    • Counting sort
    • Radix sort(base 4)
  • Hybrid family
    • Tim sort
    • Intro sort
• References

Visualization-Types

2D

• Scatter plot
• Swirl dots
• Disparity dots

Scatter plot

Scatter plots use cartesian coordinates to plot data. The data's value is plotted to the y axis and the data's index is plotted to the x axis.

Random data (left)	Sorted data (right)

Swirl dots

Swirl dots use polar coordinates to plot data. The data's values is plotted as a function of the radius and the data's index is plotted as the angle.

Random data (left)	Sorted data (right)

Disparity dots

Disparity dots don't use a traditional coordinate system to plot data. The data's position, along the radius of the polar coordinate system, are plotted as the difference between their current position in the data array and the correct position in the sorted array. The data's position, along the angle of polar of the polar coordinate system is given by the data's index in the array.

Random data (left)	Sorted data (right)

3D

In progress.

Algorithms

Summary

Algorithms	Time Complexity	Space Complexity	Auxiliary Space Complexity	Stable	Approximate runtimes(2048)
Insertion sort	O(n^2)	O(n)	O(1)	Yes	139ms
Binary insertion sort	O(n^2)	O(n)	O(1)	Yes	293ms
Merge sort	O(nlog(n))	O(n)	O(1)	Yes	15ms
Selection sort	O(n^2)	O(n)	O(1)	No	226ms
Heap sort	O(nlog(n))	O(n)	O(1)	Yes	5ms
Ternary heap sort	O(nlog(n))	O(n)	O(1)	Yes	9ms
Quick sort	O(n^2)	O(n)	O(1)	No	7ms
Dual pivot quick sort	O(n^2)	O(n)	O(1)	No	6ms
Counting sort	O(n+ k), k = possible values in array	O(n)	O(n+k)	Yes	2ms
Radix sort	O(nk) k = radix base	O(n)	O(n+k)	Yes	11ms
Tim sort	O(nlog(n))	O(n)	O(1)	Yes	13ms
Intro sort	O(nlog(n))	O(n)	O(1)	Yes	6ms

Insertion Family

Insertion sort

Pseudocode:

insertionSort(A):
  for i = 1 to length(A):
    let key = A[i]
    let j = i
    
    while(j > 0 and A[j-1] > key):
      A[j] = A[j-1]
      j--
     
     A[j] = key
  

Binary insertion sort

Pseudocode:

binaryInsertionSort(A):
  for i = 1 to length(A):
    let key = A[i]
    let j = i
    
    let pivot = binarySearch(A[0:j], key)
    while(j > 0 and j >= pivot):
      A[j] = A[j-1]
      j--
    
    A[j] = key
    
binarySearch(A, value):
  let pivot = length(A)/2
  
  if(A[pivot] === value) return pivot
  if(A[pivot] < value) binarySearch(A[pivot+1:length(A)])
  if(A[pivot] > value) binarySearch(A[0:pivot])

Merge family

Merge sort

Pseudocode:

mergeSort(A):
  let pivot = length(A)/2
  mergeSort(A[0:pivot])
  mergeSort(A[pivot:-1])
  
  return mergeA[0:pivot], A[pivot:-1])
  

Selection family

Selection sort

Pseudocode:

selectionSort(A):
  for i = 1 to length(A):
    let min = i
    
    for j = i+1 to n:
      if(A[j] < A[min]):
        min = j
    
    if min != i :
      swap(A[min], A[i])
  

Heap sort

Pseudocode:

heapSort(A):
  buildMaxHeap(A)
  sort(A)

buildMaxHeap(A):
  for i = length(A)/2 -1 to 1:
    heapify(A, length(A), i)

sort(A):
  for i = length(A) - 1 to 1:
    swap(A[0], A[i])
    heapify(A, i, 0)
    
heapify(A, size, i):
  let largest = i
  let left = 2*i + 1
  let right = 2*i + 2
  if(left < size and A[left] > A[largest]):
    largest = left;
  if(right < size and A[right] > A[largest]):
    largest = right;
  if(largest != i):
    swap(A, i, largest)
    heapify(A, size, largest)

Ternary heap sort

Pseudocode:

ternaryHeapSort(A):
  buildMaxHeap(A)
  sort(A)

buildMaxHeap(A):
  for let i = n/3 to 0:
    ternaryHeapify(A, length(A), i-1)
    
sort(A):
  for i = length(A)-1 to 1:
    swap(A[0], A[i])
    ternaryHeapify(A, i, 0)

ternaryHeapify(A, size, i):
  let largest = i
  let left = 3*i + 1
  let middle = 3*i + 2
  let right =  3*i + 3
  
  if left < size and A[left] > A[largest]:
    largest = left
  if right < size and A[right] > A[largest]:
    largest = right
  if middle < size and A[middle] > A[largest]:
    largest = middle
  if(largest != i):
    swap(A[i], A[largest])
    ternaryHeapify(A, size, largest)
  

Exchange family

Quick sort

Pseudocode:

quickSort(A):
  if length(A) <= 1: return
  
  pivot = partition(A) 
  
  quickSort(A[0:pivot])
  quickSort(A[pivot:-1])

partition(A):
  let pivot = choosePivot(A)//  choose a pivot using some algorithm/heurisitic
  
  let i = 0
  for j = 1 to length(A)-1:
    if(A[j] < pivot):
      i++
      swap(A[j], A[i])
      
  swap(A[i+1], A[-1])

Dual pivot quick sort

dualQuickSort(A):
  pivot1, pivot2 = partition(A) //choose two pivots and swap as necessary 
  
  dualQuickSort(A[0:pivot1])
  dualQuickSort(A[pivot1:pivot2])
  dualQuickSort(A[pivot2:-1])


partition(A):
  

Non-comparison family

Counting sort

Radix sort(base 4)

Hybrid family

Tim sort

Intro sort

References

• Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2009.
• Eberly, David. 3D game engine design: a practical approach to real-time computer graphics. CRC Press, 2006.