Let’s sort by hand

Assume we have an array of random numbers and we need to sort it using QuickSort algorithm:

[5, 2, 7, 9, 6, 1, 4, 5, 0]

We need to create function qsort that will get an array as an argument and will return sorted array.

That’s how the call to the function will look like:

qsort([5, 2, 7, 9, 6, 1, 4, 5, 0]);

Let’s go inside the function and inspect how it will sort the array.

  • At the first call we need to select pivot element from the array. There are multiple approaches how to select pivot, it can be chosen randomly, it can picked form the middle of an array or it can be just first element of an array. For simplicity we’ll just take first element and assign it to pivot variable and it will be equal to five in our case.
  • Then we will create two empty arrays, named left and right. First one will have all elements with values that are less than pivot. And second will receive all other elements - greater or equal to pivot.
  • Now we will go through the source array and place elements to the respective arrays by hand. Five is the pivot, we already took it from the source array, two goes to left, seven goes to right, nine goes to right, six goes to right, one goes to left, four goes to left, five goes to right and zero goes to left.
  • Now we have pivot and two arrays that have elements that are less or greater than pivot. Result of our function call will be concatenation of sorted left array, pivot and sorted right array;
// call 1:
qsort([5, 2, 7, 9, 6, 1, 4, 5, 0]);
const pivot = 5;
const left = [2, 1, 4, 0];
const right = [7, 9, 6, 5];
return qsort([2, 1, 4, 0]).concat(5).concat(qsort([[7, 9, 6, 5]]));

On the next step we call qsort recursively for the left array that holds [2, 1, 4, 0]. We repeat all the actions we did before:

  • Choose pivot, it will be equal to two
  • Create empty left and right arrays and fill them with values comparing each element of source array to pivot: one goes to left, four goes to right, zero goes to left.
  • Now result of this function call will be sorted left array, concatenated with pivot and sorted right array.
// call 2
qsort([2, 1, 4, 0]);
const pivot = 2;
const left = [1, 0];
const right = [4];
return qsort([1, 0]).concat(2).concat(qsort[4]); // [0, 1, 2, 4]

On the next step we will call qsort to sort array of two elements [1, 0]. We repeat all the steps:

  • Choose pivot, it will be equal to one.
  • Create left and right arrays and fill them with values. In our case left will hold just one element, zero. And right will be empty.
  • And result of this call will be sorted left array, pivot and right array.
// call 3
qsort([1, 0]);
const pivot = 1;
const left = [0];
const right = [];
return qsort([0]).concat(1).concat(qsort([])); // [0, 1]

No we call qsort on array that just holds one element and obviously it doesn’t need to be sorted, we just return an array as it is.

// call 4
qsort([0]);
return [0];

We return in recursive calls one level up, concatenate pivot and make another recursive call to sort empty array. Similar to the previous call with one element, we don’t need to do anything with empty array, just return it back.

// call 5
qsort([]);
return [];

Now we go up to call three, return value that holds sorted array of two elements - [0, 1], go up to call two, concatenate this value with pivot that is equals to two and concatenate to call for sorting of array from one element [4]. We already know that this call will just return that array back:

// call 6
qsort([4]);
return [4];

And now from call two we return sorted array that holds four elements: [0, 1, 2, 4]. Now we go up to the very first call of our recursive function, we already have left array sorted, pivot concatenated and we need to sort right array. Everything will work exactly as we seen before. We get an array, choose pivot, create left and right arrays, fill them with values and return concatenation of sorted left array, pivot and sorted right array.

// call 7
qsort([7, 9, 6, 5]);
const pivot = 7;
const left = [6, 5];
const right = [9];
return qsort([6, 5]).concat(7).qsort([9]);

We won’t go deeper in recursive calls because they work the same way as we already seen before.

Implementing recursive function in JavaScript

Now we will implement our function in JavaScript.

  • We start function body by checking length of an array and if it is empty or has only one element, we return as it is.
  • Next we use destructuring assignment and spread operator to get first element as pivot and place rest of the array to rest constant.
  • Also we use const keyword to create two empty arrays left and right. Using const here may be confusing because we will change contents of the arrays, it simply means that identifiers left and right won’t be reassigned but it doesn’t tell that contents of arrays can’t be changed.
  • Next we call .forEach() on rest array and compare each element with pivot, elements with lower values are put to the left and all others - to the right.
  • At the last step we call qsort recursively on left array, concatenate pivot and result of qsort on right array.

That’s how our implementation will look like:

function qsort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    const [pivot, ...rest] = arr;
    const left = [], right = [];
    rest.forEach( el => el < pivot ? left.push(el) : right.push(el) );
    return qsort(left).concat(pivot).concat(qsort(right));
}