Table of contents

• Introduction
• Project Structure
• Algorithms
  • Bubble sort
  • Heap Sort
  • Insertion Sort
  • Merge Sort
  • Quick Sort
  • Radix Sort
  • Selection Sort
• Conclusion

Introduction

This project was designed to visualize some sorting algorithms in an intuitive and interactive way. It was built with React js, MUI for icons and controllers, and based in the work of Clement Mihailescu.

It implements all of the main sorting algorithms seen on a typical data structures and algorithms class:

• Bubble Sort
• Heap Sort
• Insertion Sort
• Merge Sort
• Quick Sort
• Radix Sort
• Selection Sort

Beyond the actual implementations of the algorithms (and related to the work done for the graph algorithm visualizer), the interesting aspect of the project came from drawing an isomorphism between the entities that the algorithms manage (an algebraic space with a total order relantionship) and what was to be visualized. Maybe I am going over a tangent here but this is what real world application of algorithm boils down to, drawing an isomorphism (or another mathematical relantionship, not necessarily it needs to be so restrictive) between the problem space, in this case the bars that need to be visualized as they are sorted, and the domain space of the algorithms.

Project Structure

The project is divided in two main parts, the front end and the backend. The front-end is the components folder, it includes all the different elements of the UI, and the backend is the model wherein all the algorithms are implemented as well as the logic to create the animations from the output of these.

.
├── App.js
├── MainApp.js
├── index.js
├── others
│   ├── index.css
│   ├── reportWebVitals.js
│   └── setupTests.js
└── visualiser
|
├── components
│   ├── Canvas.js
│   ├── InformationBox.js
│   ├── Welcome.js
│   ├── buttons
│   │   ├── FunctionsButtons.js
│   │   ├── ShuffleButton.js
│   │   └── SortButton.js
│   ├── radioBox
│   │   └── AlgorithmSelector.js
│   ├── sliders
│   │   ├── SliderAnimationSpeed.js
│   │   └── SliderNumberBars.js
│   └── tutorial
│       ├── AlgorithmSelectorExplanation.js
│       ├── FunctionButtonTutorial.js
│       ├── InformationBoxExplanation.js
│       ├── SlidersExplanation.js
│       └── Tutorial.js
|
└── model
├── algorithms
│   ├── SortingAlgorithm.js
│   ├── bubbleSort.js
│   ├── heapSort.js
│   ├── insertionSort.js
│   ├── mergeSort.js
│   ├── quickSort.js
│   ├── radixSort.js
│   └── selectionSort.js
├── animations
│   └── AnimationsEngine.js
└── utils.js

Algorithms

Bubble sort

Bubble sort works by traversing all the elements the amount of times being equal to the number of elements, and whenever two adjacent elements can be shifted in the correct order, they are shifted.

Its applications often involve places where memory is scarce and the amount of elements isn't extremely big. Although within cuadratic algorithms it's usually outperformed by insertion sort

In terms of time complexity its average, worst and best case are all O(n^2), while its space complexity is constant as its an in-place algorithm.

Heap Sort

Heap Sort works quite similarly to selection sort. It keeps an unsorted and a sorted region of the array, and inserts every element from the unsorted region into their correct position in the sorted region. It differs from selection sort in that it doesn't traverse all elements to know where it should be, but it pops it from a heap to quickly find the element. Because of this its time complexity comes to be the same as the lower bound for comparison-based sorts.

In terms of time complexity its best, average and worst case are all O(nlogn), while its space complexity is constant.

Insertion Sort

Insertion Sort works by traversing element in the array and putting it in the correct position, for every element in the array, it swaps it with every other previous element until it's in the correct position relative to the previous element.

It is worth mentioning that of the cuadratic sorting family its usually the fastest. In terms of time complexity its best, average and worst case are all O(n^2), while its space complexity is constant.

Merge Sort

Merge Sort works by recursively dividing the list of elements in half until it can't anymore. Then it merges all the subarrays, maintaining the correct order of the elements, until we dont have more subarrays to merge.

Like Quick Sort, merge sort is a divide and conquer algorithm. These algorithms work by dividing the input based on a heuristic (in this case by half, but can be in even and odd for example). Then solves each of the sub-problems, and finally merges all of them together. In terms of time complexity its best, worst and average cases are all O(nlogn), while space complexity is at worst linear.

Quick Sort

Quick Sort works by recursively partitioning the list of elements based upon a pivot element and then sorting each subarray recursively by putting the pivot in the correct order.

It works similarly to Merge Sort because both are divide and conquer algorithms.Their differences being how they divide into subproblems and how they merge.

In terms of time complexity its average case is O(nlogn), worst case is O(n^2), and best is O(nlogn), while space complexity is at worst linear.

Radix Sort

Radix Sort works by creating and distributing elements into buckets according to their radix. For elements with more than one significant digit, this bucketing process is repeated for each digit, while preserving the ordering of the prior step, until all digits have been considered.

In terms of time complexity its O(n) with the requirement that they are in the range 1 to n^c with c being a constant

This means that for most numbers we have linear complexity, the lower bound for any sorting algorithm! (we need to at least traverse every element to know how to order them) .

Selection Sort

Selection Sort works by traversing every element in the array, assuming its the smallest or biggest, and then for every element to the right updating it so that it is the smallest or biggest of all the elements to its right (in the unsorted array), then it swaps it into the index that it should have had and continues until no more elements in the unsorted part are left.

In terms of time complexity its best, average and worst case are all O(n^2), while its space complexity is constant.

Conclusion

It was an interesting project to build. It allowed me to really comprehend aspects of sorting that cannot be learned until you build them yourself, a kind of feel for how they work. It also was an opportunity to build a project with overall good design, in terms of encapsulation and reusability of logic.