CODEWITHSUNDEEP
algorithmsortingdata-structuresquicksort
pranitb27
pranitb27

Reputation: 23

Quick sort where the first element in the array is smaller

Consider an array of elements {10,5,20,15,25,22,21}.

Here, I take the pivot element as 21 (last in array). According to the most of the Quick sort algorithms I saw on Internet, they explained starting the first element is compared with the pivot element. If it is smaller, it gets swapped with the index element. But the algorithm breaks on having first small element in the array making me difficult to write down the intermediate steps the quick sort will go through. All the guys on the Internet explained with example of array having the the first element greater than pivot, thus on comparing they didn't swap and moved to next element.

Please help.

Upvotes: 1

Views: 939

Answers (1)

ZhaoGang
ZhaoGang

Reputation: 4915

My suggestion on how to understand the quick sort:

The key to understand quick sort is the partition procedure, which is usually a for loop. Keep in mind that:

  1. our goal is to make the array finally become an array consisting of three parts at the end of the loop: the first part is smaller than the pivot, the second part is equal to or larger than the pivot, the last part is the unsorted part(which has no element).
  2. at the very beginning of the loop, we also have three parts: the first part(which has no element) is smaller than the pivot, the second part(which has no element) is equal to or larger than the pivot, the last part is the unsorted part(which has array.length-1 elements).
  3. During the loop, we compare and swap if needed, to ensure that in each loop, we always have those three parts, and the size of the first and second parts are increasing, and the size of the last parts is decreasing.

On your request in the comment:

Check this link: https://www.cs.rochester.edu/~gildea/csc282/slides/C07-quicksort.pdf

Read the three example figures VERY carefully and make sure you have understood them.

Upvotes: 2

Related Questions