Quicksort implementation in JavaScript

Question

I implemented Quicksort in JavaScript. I'm trying to follow the best principles in JavaScript. In Ruby when you declare classes your able to use private for the methods that are private. I don't think there is anything like that in JavaScript.

class QuickSort {
  sort(a) {
    a = this.shuffle(a); //Shuffling is needed for perfomance guarantee.
    this.privateSort(a,0, a.length - 1)
    return a;
  }

  privateSort(a, lo, hi) {
    if(hi <= lo) { return }
    let j = this.partition(a, lo, hi);
    this.privateSort(a, lo, j - 1)
    this.privateSort(a, j + 1, hi)
  }

  partition(a, lo, hi) {
    let i = lo;
    let j = hi + 1;
    let v = a[lo];

    while (true) {
      while (a[++i] < v) {
        if (i >= hi) { break; };
      }
      while (v < a[--j]) {
        if (j <= lo) { break; };
      }
      if (i >= j) { break; }
      this.swap(a, i, j);
    }
    this.swap(a, lo, j);
    return j;
  }

  swap(a, firstEl, secondEl) {
    let temp = a[firstEl];
    a[firstEl] = a[secondEl];
    a[secondEl] = temp;
    return
  }

  // Knuth-Fisher-Yates shuffle algorithm
  shuffle(arr) {
    for (var i = arr.length - 1; i > 0; i--) {
      const swapIndex = Math.floor(Math.random() * (i + 1))
      const currentEl = arr[i]
      const elToSwap  = arr[swapIndex]

      arr[i] = elToSwap;
      arr[swapIndex] = currentEl;
    }
    return arr;
  }
}

I'm also thinking of adding a method to verify input, make sure input is array, not nil, etc. Ideas for how I can go about implementing such method are welcome.

Is there anything I can improve, are there principles being violated? Am I following best practices in class implementation in JavaScript.

here is a test:

var obj = new QuickSort();
sample = obj.sort(sample);
console.log(sample)

Answer 1

Private methods

You are correct- there currently is no way to set functions as private like other languages have, though there is a proposal for private class fields including private methods but that hasn't been adopted yet. See also this similar question about private functions on SO.

There isn't one de-facto convention about private method naming. For example, the Google JS Style guide states:

6.2.3 Method names

Method names are written in lowerCamelCase. Names for @private methods must end with a trailing underscore.¹

While the AirBnB style guide states:

• 23.4 Do not use trailing or leading underscores. eslint: no-underscore-dangle

Why? JavaScript does not have the concept of privacy in terms of properties or methods. Although a leading underscore is a common convention to mean “private”, in fact, these properties are fully public, and as such, are part of your public API contract. This convention might lead developers to wrongly think that a change won’t count as breaking, or that tests aren’t needed. tl;dr: if you want something to be “private”, it must not be observably present. ²

Bear in mind that "classes, introduced in ECMAScript 2015, are primarily syntactical sugar over JavaScript's existing prototype-based inheritance. The class syntax does not introduce a new object-oriented inheritance model to JavaScript."³. Another technique for private methods is to use the Revealing module pattern and only expose methods that are considered public.

var QuickSort = (function () {
  // We'll expose all these functions to the user
  function sort (a) {
    console.log('sort() called with argument: ', arguments);
  }
  function partition() {
  }
  // Let's hide this function
  function privateSort() {
    console.log('privateSort() called');
  }

  return { // expose public functions
    sort,
    partition
  }
})(); // our IIFE function (surrounded with parens) is invoked here
const sample = [3, 4];
QuickSort.sort(sample);
QuickSort.privateSort(); //Uncaught TypeError: QuickSort.privateSort is not a function

Suggestions

Use consistent line terminators

Many lines are terminated with a semi-colon but some are not. Unless you completely understand rules of Automatic semicolon insertion or are using a compiler/module bundler it is best to include line terminators.

Don't use var

Default to using const. If you determine re-assignment is necessary then use let. This helps avoid accidental re-assignment. There is little need for var anymore, except if you absolutely needed a global variable.

Swapping values

instead of this

let temp = a[firstEl];
a[firstEl] = a[secondEl];
a[secondEl] = temp;

One could use Destructuring assignment to swap variables but it seems that is slower than other techniques even though the V8 blog claims "Once we unblocked escape analysis to eliminate all temporary allocation, array destructuring with a temporary array is as fast as a sequence of assignments."1. There is a "hack" suggested in this SO answer by showdev that appears to be the fastest method to swap variables:

a[secondEl] = [a[firstEl], a[firstEl] = a[secondEl]][0];

Useless return in swap()

There is a return at the end of swap():

swap(a, firstEl, secondEl) {
  let temp = a[firstEl];
  a[firstEl] = a[secondEl];
  a[secondEl] = temp;
  return
}

That would return undefined so there is little use in that line.

Should the input array be mutated?

If I run this code sample will get mutated, but the caller might not want it to be

const sample = [1,0,3, -1];
var obj = new QuickSort();
sortedSample = obj.sort(sample);
//sample has been modified, even though sortedSample contains the sorted data

To preserve the original data, sort a copy of it (e.g. call slice()).

Answer 2

I'm pretty sure the js convention is still to prefix "private" stuff with an underscore.

class QuickSort {
  sort(a) {...}
  _sort(a, lo, hi) {...}
  ...}

The only other thing that sticks out to me is your use of ++ and -- in the while loops. While perfectly idiomatic, I think it would express the logic better to move both conditionals together in the while(condition), and the increment action into the while's body. Of course it's always nice if one can abstract away a loop altogether...

Other people can speak more specifically about javascript than I can.