Object-Oriented Sorting Algorithms

I would like a review of a library I've recently published. I realize this is a rather large request, but having looked on meta, it seems this is perfectly on-topic. I'll include a few choice samples from the library to demonstrate my approach, as well as a link to the full codebase for anyone interested in giving a full-breadth review.

So to summarize, this library, called sort-viz, is, as the title and tags suggest, an object-oriented approach at designing an educational tool for teaching sorting algorithms, which is why the sorting algorithms use generator functions to introduce interruptions in the control-flow in order to be visualized step-by-step.

Here's a few of the classes needed to implement an iterative (bottom-up) merge sort algorithm:

/**
* Abstract sort array module.
* @module sort/abstract
*
* @requires module:sort/scope.ScopeArray
*/
import { ScopeArray } from './scope'

/**
* @memberOf module:sort/virtual
*
* @class Entry
*
* @hideconstructor
*
* @extends Array
*
* @property {number} 0 - Index.
* @property {*} 1 - Value.
*/

/**
* Invoked during each interruptable step of AbstractSortArray methods.
* @memberOf module:sort/virtual
*
* @callback interruptCallback
*
* @param {Object} step - An object containing information about a generic step interruption.
* @param {string} step.type - The type of step, e.g. "compare", "swap", "put", "key".
* @param {module:sort/virtual.Entry[]} step.entries - An array of index / value pairs of elements involved in the step.
*/

/**
* Base abstract class for arrays that implement sorting algorithms. Do not invoke directly.
* @abstract
*
* @extends module:sort/scope.ScopeArray
*
* @param {module:sort/virtual.interruptCallback} [interrupt=() => {}]
*
* @throws {TypeError} Illegal constructor.
* @throws {TypeError} interrupt must be a function.
*/
export class AbstractSortArray extends ScopeArray {
constructor (interrupt = () => {}) {
super()

if (this.constructor === AbstractSortArray) {
throw new TypeError('Illegal constructor')
}

if (typeof interrupt === 'function') {
this.set('interrupt', interrupt)
} else {
throw new TypeError('interrupt must be a function')
}
}

/**
* Invoked for each index to generate an element of the array.
* @memberOf module:sort/virtual
*
* @callback fillCallback
*
* @return {*} element - A generated value with which to populate the array.
*/

/**
* A method to interruptably populate the array with elements generated from factory.
* @param {module:sort/virtual.fillCallback} factory
* @param {number} [length=this.length]
*
* @throws {TypeError} factory must be a function.
*/
* fill (factory, length = this.length) {
if (typeof factory !== 'function') {
throw new TypeError('factory must be a function')
}

this.length = 0

for (let i = 0; i < length; i++) {
yield * this.put(i, factory())
}
}

/**
* A method to interruptably randomize the order of elements in the array.
* Uses the {@link https://en.wikipedia.org/wiki/Fisher–Yates_shuffle|Knuth Fisher Yates} method.
*/
* shuffle () {
for (let i = this.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1))
yield * this.swap(i, j)
}
}

/**
* A method to interruptably swap two elements in the array.
* @param {number} i - Index of first element to swap.
* @param {number} j - Index of second element to swap.
*/
* swap (i, j) {
;[this[i], this[j]] = [this[j], this[i]]
yield this.get('interrupt')({ type: 'swap', entries: [[i, this[i]], [j, this[j]]] })
}

/**
* A method to interruptably put an element in the array.
* @param {number} index - Index to put element value.
* @param {*} value - Value to put in index.
*/
* put (index, value) {
this[index] = value
yield this.get('interrupt')({ type: 'put', entries: [[index, value]] })
}

/**
* Abstract method to interruptably sort array of elements.
* @abstract
* @throws {TypeError} Illegal invocation.
*/
* sort () {
throw new TypeError('Illegal invocation')
}
}

/**
* Comparative sort array module.
* @module sort/comparative
*
* @requires module:sort/abstract.AbstractSortArray
*/
import { AbstractSortArray } from './abstract'

/**
* Invoked during each compare step of the ComparativeSortArray sort method.
* @memberOf module:sort/virtual
*
* @callback compareCallback
*
* @param {*} a - An element to compare on the left-hand side.
* @param {*} b - An element to compare on the right-hand side.
*
* @return {number} result - See {@link https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort#Description|compareFunction}
*/

/**
* Base abstract class for arrays that implement comparative sorting algorithms.
* @abstract
*
* @extends module:sort/abstract.AbstractSortArray
*
* @param {module:sort/virtual.interruptCallback} [interrupt]
* @param {module:sort/virtual.compareCallback} [compare=(a, b) => 0]
*
* @throws {TypeError} compare must be a function of 2 arguments.
*/
export class ComparativeSortArray extends AbstractSortArray {
constructor (interrupt, compare = (a, b) => 0) {
super(interrupt)

if (typeof compare === 'function' && compare.length === 2) {
this.set('compare', compare)
} else {
throw new TypeError('compare must be a function of 2 arguments')
}
}

/**
* A method to interruptably compare two elements in the array.
* a and b are optional, since i and j can sometimes be
* used to represent indices that are virtual in the comparsion.
*
* @param {number} i - Index of left-hand element to compare.
* @param {number} j - Index of right-hand element to compare.
* @param {*} [a=this[i]] - Value of left-hand element to compare.
* @param {*} [b=this[j]] - Value of right-hand element to compare.
*
* @return {number} result - See {@link https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort#Description|compareFunction}
*/
* compare (i, j, a = this[i], b = this[j]) {
yield this.get('interrupt')({ type: 'compare', entries: [[i, a], [j, b]] })
return this.get('compare')(a, b)
}
}

/**
* Merge sort array module.
* @module sort/comparative/merge
*
* @requires module:sort/comparative.ComparativeSortArray
*/
import { ComparativeSortArray } from '../comparative'

/**
* Base abstract merge sort array.
*
* @abstract
*
* @extends module:sort/comparative.ComparativeSortArray
*/
export class MergeSortArray extends ComparativeSortArray {
/**
* @param {number} begin
* @param {number} middle
* @param {number} end
*/
* merge (begin, middle, end) {
const first = this.slice(begin, middle)
const last = this.slice(middle, end)
let index = begin
let i = 0
let j = 0

while (index < end) {
if (j === last.length) {
yield * this.put(index, first[i++])
} else if (i === first.length) {
yield * this.put(index, last[j++])
} else if ((yield * this.compare(begin + i, middle + j, first[i], last[j])) <= 0) {
yield * this.put(index, first[i++])
} else {
yield * this.put(index, last[j++])
}

index++
}
}
}

/**
* Iterative merge sort array module.
* @module sort/comparative/merge/iterative
*
* @requires module:sort/comparative/merge.MergeSortArray
*/
import { MergeSortArray } from '../merge'

/**
* @see {@link https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation|Bottom-up Merge Sort}
*
* @extends module:sort/comparative/merge.MergeSortArray
*/
export class IterativeMergeSortArray extends MergeSortArray {
/** @override */
* sort () {
for (let increment = 1; increment < this.length; increment *= 2) {
for (let begin = 0; begin < this.length; begin += increment * 2) {
const middle = begin + increment
const end = Math.min(begin + increment * 2, this.length)

yield * this.merge(begin, middle, end)
}
}
}
}


And as promised, here is the link to the repository, which also contains formatted documentation on the respective github pages, and a full demo on Heroku.

Please be responsible and only make HTTP requests to the Heroku link sparingly, as I have it hosted on a hobbyist plan, which only allows so many hours of uptime a month. I have plans to implement a service worker for it in the future to mitigate this issue.

• I just have to say, this looks incredible. Amazing work! Aug 13 '17 at 0:34
• @Gerrit0 thank you, I really appreciate the compliment. I know that having a deep prototypal inheritance and using generator functions isn't exactly performant, but then again, that was never the point to begin with. I was working more towards clean, readable, and maintainable code that tried to avoid "looking asynchronous" as much as possible. Aug 13 '17 at 0:39
• I would take another approach to this, the main class you need to have is a list, and this is already defined in javascript as an array. I would instead define methods to sort the array it instead of defining every operation as a class. Ideally a class should abstract some kind of data and the operations over these data in the form of methods. Aug 18 '17 at 7:32
• @DavidLemon if you actually look at the repository, the base class of all these algorithms is in fact Array. So, I don't really understand how that isn't already done here. And the operations aren't represented by classes, it's just the hierarchy of inheritance is based on what algorithms use what operations. Of course everything can use swap and put, so that goes in the abstract class. compare is only used by comparative algorithms, so that goes in the next class. merge is used by merge sorts, and then finally the polymorphic sort function overriden for each implementation. Aug 18 '17 at 7:52

Note- the review below only pertains to the code in the post. "Code that's not included can not be reviewed."1

Overall I would say this code is well-written. Variables are declared with const and let appropriately. It has good documentation - especially for each method- although example usage is tough to find. One possible change you could consider is using async functions.

I haven't used generators much but do believe they can be quite useful. I am intrigued by the application in certain functions - e.g. the shuffle method. Does it make sense to use an iterator to handle things like shuffling?

The shuffle method is already somewhat optimized by looping from the end of the array to the front:

for (let i = this.length - 1; i > 0; i--) {


The same can be achieved by moving the decrement operator to the while condition, and starting i at this.length:

for (let i = this.length; i--; ) {


I noticed sometimes j can be equal to i - especially as i approaches zero. Does it still make sense to call the swap method when those are equal?

The constructor for AbstractSortArray throws an error if the base constructor is called, and then if interrupt is not a function throws an error.

constructor (interrupt = () => {}) {
super()

if (this.constructor === AbstractSortArray) {
throw new TypeError('Illegal constructor')
}

if (typeof interrupt === 'function') {
this.set('interrupt', interrupt)
} else {
throw new TypeError('interrupt must be a function')
}


The else keyword can be avoided by checking if the typeof interrupt isn't a function first:

if (typeof interrupt !== 'function') {
throw new TypeError('interrupt must be a function')
}
this.set('interrupt', interrupt)


• Just to clarify, the reason that generators are used for the sort and shuffle methods is because each put() and swap() call suspends the generator function and waits for the DOM to repaint based on the changes made to the array. That's also why swap() is called in shuffle() even if the indices are equal, to allow the DOM to indicate that an item was swapped with itself. I also appreciate the feedback regarding the AbstractSortArray constructor, I realize now that the absense of abrupt returns should be outside of conditional statements in the constructor, but did not at the time. Jul 19 '20 at 8:43