2
\$\begingroup\$

This is an implementation of Quick Sort in JS. Can this implantation of Quick Sort be more concise and efficient while still remaining expressive?

function quickSort(list){   
   if( list.length < 2 ) {
    return list;     
}
var leftList = [];
var rightList = [];
for( var i = 1; i < list.length; i++ ){
    if(list[i] >= list[0]){
       rightList.push(list[i]) ;
    }else{
       leftList.push(list[i]);
    }
}

var sortedLeft = quickSort(leftList);
var sortedRight = quickSort(rightList);
var combined = sortedLeft.concat(list[0]).concat(sortedRight);
console.log(combined.join(' '));
return combined;
}

var array=[9,8,7,6,5,4,3,2,1];
quickSort(array);

Example 2 works with randomly selected pivots, filters, and recursion. This example is more efficient than the first while still remaining as just as expressive. Unfortunately, both perform horribly compared to in place and nonrecursive approaches.

function quicksort(arr,len=arr.length) {
    if (len <= 1) return arr;
        else
        var randomIndex = Math.floor(Math.random() * len),
        pivot = arr.splice(randomIndex, 1),
        lesserHalf = arr.filter(el =>el <= pivot)
        biggerHalf = arr.filter((el)=> el > pivot)
        return ((lesserHalf, pivot, biggerHalf) => 
        [].concat(quicksort(lesserHalf), pivot, quicksort(biggerHalf)))
        (lesserHalf, pivot, biggerHalf)
}

var arr =[9,8,7,6,5,4,3,2,1];
console.log(quicksort(arr));

Example 3 is the shortest I've seen using spread and inspired by Haskel

const quickSort = ([x = [], ...xs]) => {
  if (x.length === 0) return [];
  return [
    ...quickSort(xs.filter(y => y <= x)),
    x,
    ...quickSort(xs.filter(y => y > x))
  ];
}

var arr= [9,8,7,6,5,4,3,2,1];

console.log(quickSort(arr))

\$\endgroup\$

locked by Jamal May 29 '17 at 16:59

This post has been locked while disputes about its content are being resolved. You may discuss this on meta if you have concerns.

Read more about locked posts here.

  • \$\begingroup\$ Most of the sample code I find online when I search for "quicksort JS" involves making two functions swap() and partition()... I did see one implementation that is very similar to yours on a gist here... slightly shorter but mostly because it combines the arrays in the call to concat() and has fewer blocks (i.e. with curly-braces: {}) \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ May 26 '17 at 16:17
  • \$\begingroup\$ @Sam Onela The use of splice in pivot obfuscates and makes the code less efficient. Also, the lack of blocks is ornamental at best. The foreach is definitely shorter. However, that is not enough of a change for it to be considered an improvement. Maybe if the whole thing was done in reduce, or a shorter combination of the higher order functions, a case can be made for that \$\endgroup\$ – Rick May 26 '17 at 16:39
  • 1
    \$\begingroup\$ @Arrow Your quicksort creates a lot of new arrays and concatenates them. An in-place solution would be the fastest. Alternatively, cloning the input array and sorting in-place on the clone would be fast, too. A non-recursive solution is probably faster than a recursive one. \$\endgroup\$ – le_m May 26 '17 at 17:14
  • \$\begingroup\$ @le_m can you do it without adding excessively more code? maybe by using a generator, Map, or Set data structures? \$\endgroup\$ – Rick May 26 '17 at 17:17
2
\$\begingroup\$

Before even thinking about performance, concision, etc., run JSLint or similar over these methods and fix the indentation, other whitespace, and bugs. As it is the lack of consistency and poor indentation makes it hard to read and hides things like a missing comma which is leading to implicit semicolon insertion:

        var randomIndex = Math.floor(Math.random() * len),
        pivot = arr.splice(randomIndex, 1),
        lesserHalf = arr.filter(el =>el <= pivot)
        biggerHalf = arr.filter((el)=> el > pivot)

These four lines also look buggy because pivot is an array and yet it's being compared to an element with <= and >.

        var randomIndex = Math.floor(Math.random() * len),
            pivot = arr.splice(randomIndex, 1)[0],
            lesserHalf = arr.filter(el => el <= pivot),
            biggerHalf = arr.filter(el => el > pivot);

is more consistent, more obviously correct, and fixes at least one bug.


Example 3 also looks buggy.

const quickSort = ([x = [], ...xs]) => {
  if (x.length === 0) return [];

How will this sort ["", "a", "b"]? Answer: it will return [].

\$\endgroup\$
1
\$\begingroup\$

You keep allocating memory in all recursive calls of your implementation, yet you need not to: quicksort as an algorithm does not require more memory than the stack space (due to recurssion). Also, it would make sense to sort the input array itself instead of producing a new sorted array. Finally, its a bad idea to do console output in an algorithm.

Taking the pseudocode from Wikipedia article for quick sort, we can arrive at this implementation:

function swap(arr, i, j) {
    var tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

function partition(arr, lo, hi) {
    var pivot = arr[hi];
    var i = lo - 1;

    for (var j = lo; j < hi; ++j) {
        if (arr[j] <= pivot) {
            ++i;
            if (i !== j) {
                swap(arr, i, j);
            }
        }
    }
    swap(arr, i + 1, hi);
    return i + 1;
}

function quick_sort2(arr, lo, hi) {
    if (lo < hi) {
        var p = partition(arr, lo, hi);
        quick_sort2(arr, lo, p - 1);
        quick_sort2(arr, p + 1, hi);
    }
}

function quick_sort_entire(arr) {
    quick_sort2(arr, 0, arr.length - 1);
}
\$\endgroup\$
  • \$\begingroup\$ I like the current implementation because of it's concise and expressive nature. Do you think an equally expressive yet concise implementation is possible why still addressing all of the valid performance concerns you just mentioned? If possible can you provide an example? \$\endgroup\$ – Rick May 26 '17 at 19:58

Not the answer you're looking for? Browse other questions tagged or ask your own question.