CODEWITHSUNDEEP
data-structuresquicksort
Rajeshwar
Rajeshwar

Reputation: 11651

Quick Sort Understanding in this case

I am revising the quick sort algorithm however it is prooving to be a bit more complex that I thought.

Suppose My Array has the following A = {7,1,5,8,2,0}

Now I select my pivot as the index 2 of the array and it has the value 5. (Eventually all elements less than 5 would be on LHS and elements greater would be on RHS)

Now I start moving from left (index 0) towards right(index 2) till I reach a value that is greater than 5. If a value on the left side is greater than the pivot value 5 then it needs to move to the right side. For it to move to the right side it requires an empty slot so that both the value can be interchanged. So the first interchange gives me the array

A = {0,1,5,8,2,7}

Now two elements still remain on the left side the 2 and 7 (The right side also moves towards the pivot - leftwards and if it is less than th epivot it is suppose to move to the other side). Now here is the question what would happen if there is no slot in the right side and an element on the left side needs to be moved to the right side of the pivot ? Am I missing something ?

Upvotes: 1

Views: 314

Answers (2)

Ankur Anandapu
Ankur Anandapu

Reputation: 81

the basic idea of quick sort is ,

you choose a pivot element, and try to place all the elements less than pivot left to pivot element , and greater than or equal to to the right. this process happens recursively.

As yo have chosen 5 , a point from left and other from right moves on towards each other comparing each element with pivot, and if these two pointers cross over you swap left pointer with pivot.

In the first case , you have swapped 0 and 7 , which is fine ,but now the index advances from one point , now the left pointer points to element 1, and right pointer to 2 . Right pointer stops at 2 as it is less than pivot 5., left pointer comes till 8 and swaps 8 and 2. the pointer advance one more time, the left pointer cross over the right pointer , hence it swaps with 2.

now if you see, 5 is in its correct place. it would look like 0,1,2,5,8,7

link useful: https://www.youtube.com/watch?v=8hHWpuAPBHo

Algorithm:

// left is the index of the leftmost element of the subarray

// right is the index of the rightmost element of the subarray (inclusive)

// number of elements in subarray = right-left+1

partition(array, left, right)

 pivotIndex := choosePivot(array, left, right)

 pivotValue := array[pivotIndex]

 swap array[pivotIndex] and array[right]

 storeIndex := left

 for i from left to right - 1

     if array[i] < pivotValue

         swap array[i] and array[storeIndex]

         storeIndex := storeIndex + 1

 swap array[storeIndex] and array[right]  // Move pivot to its final place

 return storeIndex

Upvotes: 0

Erti-Chris Eelmaa
Erti-Chris Eelmaa

Reputation: 26268

Well, the "partition" step you're tazlking about, can be implemented in various ways.

The easiest way to implement is imo this way:

1) Pick a pivot element

2) Move the pivot element as the most rightmost element

3) Do a left scan and stack all the elements that are smaller than pivot sequentially.

4) Finally you know how many elements are smaller -> do the final swap to make sure pivot element ends up in the correct place.

I've taken this from the wiki, and added number steps to the code, just to make it clear.

// left is the index of the leftmost element of the subarray // right is the index of the rightmost element of the subarray (inclusive) // number of elements in subarray = right-left+1 partition(array, left, right) pivotIndex := choosePivot(array, left, right) // step 1 pivotValue := array[pivotIndex] swap array[pivotIndex] and array[right] // step 2 storeIndex := left for i from left to right - 1 // step 3 if array[i] < pivotValue swap array[i] and array[storeIndex] storeIndex := storeIndex + 1 swap array[storeIndex] and array[right] // step 4 return storeIndex

Upvotes: 1

Related Questions