CODEWITHSUNDEEP
algorithmsortingquicksort
Nicola Pedretti
Nicola Pedretti

Reputation: 5166

Quicksort algorithm -- clarification

I have been looking at different videos and read different articles on the quicksort algorithm.

I understand how it works and if I didn't there is plenty of material online for me to look into. The problem I am having here is that some of the articles I found state the following (from wikipedia) :

Reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.

some other sources, (hackerrank video):

We swap elements around such that all elements smaller than the pivot come before elements that are bigger than the pivot

There is a substantial difference in these two algorithms. The first one splits the array using the pivot, and puts everything that is smaller on one side, and everything that is larger on the other.

The second one would not be concerned with the pivot itself, but it would make sure that all elements smaller than the pivot come before the ones that are bigger. Where the pivot ends up is not even mentioned.

So if this was the array to sort [3, 15, 4, 8, 12] and the pivot was 8

solution 1: [3, 4, 8, 15, 12]

solution 2: [3, 8, 4, 15, 12]

I found so many conflicting opinions that I wonder if this matters or not, but I would like to know if there is a right way of implementing it, or it can vary.

Upvotes: 0

Views: 275

Answers (1)

rcgldr
rcgldr

Reputation: 28931

The two main quicksort partition schemes are Lomuto and Hoare. Both are explained in pseudo code in the wiki article:

https://en.wikipedia.org/wiki/Quicksort#Lomuto_partition_scheme

https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme

For both of these schemes, each partition step puts the pivot in it's final sorted position. Elements equal to the pivot can end up in either the left or right partition after a partition step (but the pivot element ends in its proper position).

For Lomuto scheme, the pivot is either at the left or right end of the sub-array and there's a final swap to put the pivot in place. For Lomuto, the pivot element is not included in the recursive calls.

For Hoare scheme, the pivot ends up in place due to the way the algorithm works. However the pivot ends up as the last element of the left partition or the first element of the right partition. Extra code could be added to exclude the pivot element from recursion, but it ends up slightly slower. Hoare scheme is generally faster than Lomuto.

To avoid worst case O(n^2) time complexity on simple data patterns like already sorted data, reverse sorted data, a median of three can be used at the start, sorting the first, middle, and last elements in a sub-array, then using the middle element as the pivot. Another option is to choose a random pivot, but generating a random index usually involves a multiply, add, and divide (for modulo), adding to the overhead. Other schemes like median of medians guarantees O(n log(n)) time complexity, but the constant factor overhead is a multiple of the standard schemes.

https://en.wikipedia.org/wiki/Median_of_medians

Worst case stack complexity can be limited to O(log(n)) by only using recursion of the smaller of the two partitions during a partition step, then looping back to handle the larger partition. This doesn't avoid time complexity O(n^2).

An alternative is to use a hybrid sort like introsort, which switches to heap sort if the level of recursion exceeds some threshold.

https://en.wikipedia.org/wiki/Introsort

Upvotes: 2

Related Questions