DEV Community

loading...

Discussion on: [HELP]Why every explanation about quicksort is somehow different?

Collapse
jennrmillerdev profile image
Jen Miller • Edited

hmm, I think I may not be understanding the issue you see. I'll take a shot. Lets call the left pointer "i" and right pointer "j"

There are different ways to select the pivot. Some will select a random element, others index 0 or last or the middle. Regardless, i will keep moving right and j will keep moving left...until they meet.

In the end, you want elements divided into two groups. The dividing point of the two arrays is where index when i and j meet. Algorithms treat the meeting differently. Some will stop the i and j progression when i==j. Others will stop before. But this is just a implementation detail.

Some algorithms will put the pivot in the middle as a final swap, then recursively quick sort the two halves (not including the pivot in the middle -as this element is in the correct final position).

They key is to understand regardless of the partitioning specifics, the two arrays will be partitioned into two groups. The left group will be less than the pivot and the right side will be larger. Again, it's an implementation detail if the pivot is included in the group, in the right side or left side.

I can understand why it's complicated though. In particular this video is pretty helpful (and is how I think of quicksort).

Another method is explained in the hackerrank video below, however, the explanation misses the key point of how the meeting of i and j is dealt with...so I can see how it's confusing to follow. Though it is talked about in the code writeup. A lot of people in the comments are also frustrated too.