Fast Sorting with Quicksort | kirupa.com

programming
1

by kirupa | 29 November 2014

When it comes to sorting stuff, one of the most popular algorithms you have is quicksort. It is popular because it is fast - really fast when compared to other algorithms for similar types of workloads. Key to its speed is that quicksort is a divide-and-conquer algorithm. It is called that because of how it breaks up its work. Instead of eating a giant chunk of data in one bite and chewing it over a long period of time (kinda like an anaconda), quicksort breaks up its data into smaller pieces and chews on each smaller piece quickly.

This is a companion discussion topic for the original entry at http://www.kirupa.com/sorts/quicksort.htm
2

Before swapping values you use the following code to check whether items should be swapped:

This checks whether the left index is smaller or equal to the right one.
But if both indexes are equal, the swap necessarily cannot have an effect.
Why not check with < instead of <=?

3

You totally can. There are different implementations for that part. I chose <= for it made my end conditions easier. If you remove the <= and replace it with just a <, you’ll need to go back and update not only the while loop but also the initial array you pass in to account for the last value not being checked. It gets a bit messy IMO.

4

Why is that? Since the indexes are the same the swap can’t do anything, right?
In what scenario does that make a difference?

5

You are totally right! Ignore what I said earlier. The important part is that we shift the values of i and j. You could simply write it as follows:

if (i < j) {
  var tempStore = arrayInput[i];

  arrayInput[i] = arrayInput[j];
  arrayInput[j] = tempStore;
}

i++;
j--;

Thanks for pointing that out :slight_smile: