I have this past year question based on the following scenario:
When the list of items to be sorted contains a lot of duplicate values, we can improve QuickSort by grouping all the values that are equal to the pivot to the middle and then we recursively QuickSort those values on the left and those values on the right. Make the necessary changes to the partition method to achieve that.
Here is the implementation of Quicksort, written in Java. I will not include the code in the main page because it seems that this site requests for description of pseudocode rather than actual code, even if the code is very “simple”.
In particular, this quicksort implementation is similar to the typical one, but choses its pivot on the left of the array.
I have some basic understanding of the quicksort algorithm based on the actual code, but a lot of times I have to break down the code myself to understand it. Whenever I am given pseudocode hints to understand the algorithm[and to be honest I don’t know sometimes whether a hint is a very obvious one or a rather implicit one], I somehow cannot appreciate the “magic” behind the pseudocode.
My understanding of this implementation of quicksort is that the array has to be iterated to make 2 regions of low and high values, while we dynamically decide on where to put the pivot, call it position X, which in this implementation is chosen to be the leftmost element of the input array. If this position X is dynamically decided, how exactly do you “group elements equal to pivot” to middle, and how exactly does it adhere to the principles behind the typical algorithm?
Do inform me if more information is required or the formatting of the question doesn't adhere to the standards here.