Skip to content

Latest commit

 

History

History
138 lines (105 loc) · 5.29 KB

README.md

File metadata and controls

138 lines (105 loc) · 5.29 KB
Raw

Sorting Algorithm Visualizer

Built with React and Redux.

Table of Contents

  1. LineCollection
  2. AlgoRunner
  3. Sorting Algorithms

How stuff works?

LineCollection

The LineCollection Class is an extension of the built-in Array Object. It adds methods that are vital to the functionality of the app.

See Source.

Methods:

shuffle()

Shuffles this (the instance of the LineCollection).

LineCollection.shuffle()

calcColor(i)

Generates rgb value based on i.

LineCollection.calcColor(i)

_generateCollection()

Generates collection of Line Objects.

LineCollection._generateCollection()
Invoked in constructor when integer is passed in.

_updateShuffleIdx()

Iterates over this and updates the shuffledIdx property of each Line.

LineCollection._updateShuffleIdx()
Invoked in constructor when Array or LineCollection is passed in.

Line

The Line Class represents a single line.

See source.

Methods:

recalculate(i)

Recalculates the height, width, x and y properties of this (instance of Line).

Line.recalculate(i)

mark()

Sets the Line.isComparing property to true. When Line.isComparing === true the line will render yellow. You must unmark the line to revert it to its original color.

Line.mark()

unmark()

Sets the Line.isComparing property to false. When Line.isComparing === false the line will render its original color.

Line.unmark()

AlgoRunner

The AlgoRunner Class is the mechanism that runs the sorting algorithm. It implements a "lazy sort" system (more on that later). It allows you to control the speed that the given sorting algorithm runs at.

See source.

Lazy Sort

First, let me explain a key piece of how the sorting algorithms are implemented*. Every sorting algorithm is implemented using Generator functions.

Before I explain why, I will explain what lead me to this implementation.

The original implementation would perform the sort and collect slices of the sorting proccess to later be rerendered. This, all before a single rerender occurred. The queued up slices would then be dequeued at an adjustable rate. This is where the rerendering would begin. This worked well for small collections but once the size increased it would appear to the user that the application was frozen. This was not acceptable.

Generator functions save the day! In short, a Generator is a function you can pause and come back to at anytime. This allowed me to implement a lazy sorting mechanism.

The process:

  1. Constructor:
    1. Get generator. **
    2. Initial next() call to retrieve first slice to be rerenderd.**
    3. Subscribe to redux store to listen for speed changes.**
  2. Run:
    1. Dispatch new slice to redux store. This kicks off the render.
    2. Subsequent next invokation to retrieve next slice of the sort. To be rerendered.
    3. Invoke _continueCycle() with delay of this.speed.
    4. Rinse and repeat.

Methods

run()

Kicks off sorting cycle.

AlgoRunner.run()

_startCycle()

Dispatches current slice, retrieves next slice and invokes this._continueCycle() with a delay.

AlgoRunner._startCycle()
Should always be invoked with delay.

_continueCyle()

Invokes this._startCycle().

AlgoRunner._continueCyle()

SortingAlgorithms

Requirements:

  • Every algorithm must be a Generator.
    • Every yield value must be a new LineCollection(). Will rerender using yielded value.
    • Recursive algorithms may use yield*.
    • Helper functions that perform swaps must also be Generators that yield new LineCollections().

F.A.Q

Q: Why did you make this?
A: I wanted to gain a deeper understanding of sorting algorithms. This project made it fun.

Q: How many algorithms are you going to implement?
A: I'm aiming for all of these.

** This step only occurs in the constructor