Quick Sort in js

Question

I've found this article on medium and I'm trying to figured out what's the code actually do.

this is the code:

helper

const defaultComparator = (a, b) => {
  if (a < b) {
    return -1;
  }
  if (a > b) {
    return 1;
  }
  return 0;
};

sorting function

const quickSort = (
  unsortedArray,
  comparator = defaultComparator
) => {

  // Create a sortable array to return.
  const sortedArray = [ ...unsortedArray ];

  // Recursively sort sub-arrays.
  const recursiveSort = (start, end) => {

    // If this sub-array is empty, it's sorted.
    if (end - start < 1) {
      return;
    }

    const pivotValue = sortedArray[end];
    let splitIndex = start;
    for (let i = start; i < end; i++) {
      const sort = comparator(sortedArray[i], pivotValue);

      // This value is less than the pivot value.
      if (sort === -1) {

        // If the element just to the right of the split index,
        //   isn't this element, swap them.
        if (splitIndex !== i) {
          const temp = sortedArray[splitIndex];
          sortedArray[splitIndex] = sortedArray[i];
          sortedArray[i] = temp;
        }

        // Move the split index to the right by one,
        //   denoting an increase in the less-than sub-array size.
        splitIndex++;
      }

      // Leave values that are greater than or equal to
      //   the pivot value where they are.
    }

    // Move the pivot value to between the split.
    sortedArray[end] = sortedArray[splitIndex];
    sortedArray[splitIndex] = pivotValue;

    // Recursively sort the less-than and greater-than arrays.
    recursiveSort(start, splitIndex - 1);
    recursiveSort(splitIndex + 1, end);
  };

  // Sort the entire array.
  recursiveSort(0, unsortedArray.length - 1);
  return sortedArray;
};

So, I spent a while to figured out how the splitIndex works. It start at 0 and it get incremented by 1 only if the current element in the for loop is less than the pivot. When we encounter a number greater than the pivot value, the splitIndex remain at its value and the i gets incremented. In the next step if the number is also less than the pivot, we swap them

So for example with this array: [2,4,65,1,15] the splitIndex and i are equal, during the for loop, until we get the number 65. Here splitIndex is not incremented and when we arrive at number 1, we swap 1 and 65.

I'm not an english native speaker, so I not understand completely what the author means with:

 // If the element just to the right of the split index,
        //   isn't this element, swap them.

I have to fully understand yet how the code works, but, in your opinion, is correct what I've said?

Thanks

Have a look at this question: https://stackoverflow.com/questions/39665299/understanding-quicksort?rq=1 — David, Apr 09 '19 at 13:55
This is basically [Lomuto partition scheme](https://en.wikipedia.org/wiki/Quicksort#Lomuto_partition_scheme) . The check for splitIndex != i probably takes more time than avoiding needless swaps. — rcgldr, Apr 09 '19 at 14:16

Christoph Burschka · Accepted Answer · 2019-04-09T14:33:15.000

The splitIndex variable tracks (in the section of the array you are currently sorting) the divider between elements that are "smaller" and "equal or larger" than the pivot. Your description of how it works seems basically correct.

In general, if we encounter an element that is smaller than the pivot, we swap it with the one at splitIndex to put it in the "smaller than pivot" section, and then increment splitIndex to indicate the section has grown. If we encounter one that is equal or larger, we leave it where it is, and don't grow the section.

This makes sense assuming that the element at splitIndex is not smaller than the pivot. This is true if i is larger than splitIndex, because then we have already encountered at least one such element, and skipped over it.

The exception is if we are currently checking the element at splitIndex (which will be the case as long as all elements so far have been smaller than the pivot). In this case we'd be swapping the element with itself. That is redundant, so this is the reason for the splitIndex !== i check.

As for

    // If the element just to the right of the split index,
    //   isn't this element, swap them.

I suspect the author made an off-by-one error with the comment. It should say "the element at the split index", not "the element to the right of the split index".

score 1 · Answer 2 · answered Sep 27 '22 at 18:57

Try this, I think it looks very aesthetically.

function qsort(array) {
  if (array.length < 2) return array

  let pivot = array[0]
  let less = array.slice(1).filter(el => el <= pivot)
  let greater = array.slice(1).filter(el => el > pivot)

  return qsort(less).concat([pivot], qsort(greater))
}

console.log(qsort([10, 5, 2, 3, 7, 4])) // [ 2, 3, 4, 5, 7, 10 ]

Quick Sort in js

2 Answers2