Quicksort Algo Change?

[ACollectionOfAtoms]

What's up?

Current quicksort implementation will not sort list with duplicate values:

quicksort([3,3,2,1,4]) // returns [1,2,3,4]

this along with the hidden random function may result in some confusion if someone were to try and implement the code with reference to the site.

Mkay, tell me more...

This can be alleviated with the following implementation:

function randomIndex(list) {
  return Math.round(Math.random() * (list.length - 1)); // changes here
}

export default function quicksort(list) {
  if (list.length < 2) {
    return list;
  }
  const pivot = list.splice(randomIndex(list), 1); // here
  const less = list.filter(i => i <= pivot); // here (<= rather than <)
  const greater = list.filter(i => i > pivot);

  return [
    ...quicksort(less),
    ...pivot, // and here
    ...quicksort(greater)
  ];
}

Which would result in: quicksort([3,3,2,1,4]) // returns [1,2,3,3,4]

Although I could see the current implementation being favored for a slight increase in brevity, I thought this was worth bringing up :)

(As an aside I initially wanted to make a PR... I attempted to (naively) drop the above code into algorithms/quicksort.js but this resulted in the pivot not displaying correctly :( )

[ovidiuch]

Current quicksort implementation will not sort list with duplicate values:

You're right. Thanks.

Although I could see the current implementation being favored for a slight increase in brevity, I thought this was worth bringing up :)

Indeed I am biased against keeping the featured code as short as possible.

I like your solution, with two mentions:

• Besides mutating the list (2nd bias: functional programming) const pivot = list.splice(randomIndex(list), 1) is a bit ugly and does 2 things at the same time
• It's a bit confusing that the pivot is a list (probably why the viz broke after you changed this)

Another route we could take, which might even rid us of the hidden random function, is to use [0] as pivot. It simplifies things but then we'd have to add .slice(1) for each side and gain 2 lines of code or do something like const remaining = list.slice(1); which would only add 1 line but require extra work on the animation side.

On the other hand I realize no variant is going to please every case, and definitely not the most visually attractive & short. Here's what I suggest: An info page for each algorithms where we:

• Outline the limitations of the featured version
• List a number of things you could do to improve (e.g. pivot strategies)
• Link external resources for more thorough documentation/examples

I feel this could help keep the mission of this project be about explaining the basic mechanics algorithms as elegantly as possible, while at the same time not bastardizing well-refined algorithms nor confusing users by omitting key elements. What do you think?

[ACollectionOfAtoms]

Right, I think info pages should prove worthy auxiliary in clearing up what may be lost in brevity. Closin' now!

[ovidiuch]

Integrated this in a new Footnotes section. Thanks!

[st0le]

Without loss of brevity, you can have one more filtered list that has i == pivot and have that returned in the middle of the final result.