Quick sort with middle element as pivot

Question

My understanding of quick sort is

1. Choose a pivot element (in this case I am choosing middle element as pivot)
2. Initialize left and right pointers at extremes.
3. Find the first element to the left of the pivot which is greater than pivot.
4. Similarly find the first element to the right of the pivot which is smaller than pivot
5. Swap elements found in 3 and 4.
6. Repeat 3,4,5 unless left >= right.
7. Repeat the whole thing for left and right subarray as pivot is now placed at its place.

I am sure I am missing something here and being very stupid. But above does not seems to be working fot this array:

  8,7,1,2,6,9,10,2,11 pivot: 6  left pointer at 8, right pointer at 11
  2,7,1,2,6,9,10,8,11 swapped 2,8  left pointer at 7, right pointer at 10

Now what ? There is no element smaller than 6 on it's right side. How 7 is going to go to the right of 6 ?

Spiegelman

Answer 1

There is no upfront division between the left and the right side. In particular, 6 is not the division. Instead, the division is the result of moving the left and right pointer closer to each other until they meet. The result might be that one side is considerably smaller than the other.

Your description of the algorithm is fine. Nowhere does it say you have to stop at the middle element. Just continue to execute it as given.

BTW.: The pivot element might be moved during the sorting. Just continue to compare against 6, even if it has been moved.

Update:

There are indeed a few minor problems in your description of the algorithm. One is that either step 3 or step 4 need to include elements that are equal to the pivot. Let's rewrite it like this:

My understanding of quick sort is

1. Choose a pivot value (in this case, choose the value of the middle element)
2. Initialize left and right pointers at extremes.
3. Starting at the left pointer and moving to the right, find the first element which is greater than or equal to the pivot value.
4. Similarly, starting at the right pointer and moving to the left, find the first element, which is smaller than pivot value
5. Swap elements found in 3 and 4.
6. Repeat 3,4,5 until left pointer is greater or equal to right pointer.
7. Repeat the whole thing for the two subarrays to the left and the right of the left pointer.

pivot value: 6, left pointer at 8, right pointer at 11
8,7,1,2,6,9,10,2,11 left pointer stays at 8, right pointer moves to 2
2,7,1,2,6,9,10,8,11 swapped 2 and 8, left pointer moves to 7, right pointer moves to 2
2,2,1,7,6,9,10,8,11 swapped 2 and 7, left pointer moves to 7, right pointer moves to 1
pointers have now met / crossed, subdivide between 1 and 7 and continue with two subarrays

Frontogenesis

Thanks for the reply @Codo. So in this particular case what will my recursive calls will look like ? What I am trying to understand is the validity of the statement that I seem to came across everywhere - "All the elements on the left of the pivot are smaller and right of the pivot will be larger by the end of iteration" ... I understand that pivot can move .. but I do not see how it is moving in above case. – Spiegelman

waiting to hear back from you. :) – Spiegelman

My only concern (which is not really valid I think) is that we started with 6 as pivot but finally array got rearranged such that all the elements smaller than 7 are before 7 and larger than 7 are after 7. Ideally we should have achieved this for 6. – Spiegelman

According to your 4th point how did you gone past through 6 in your dry running code at left pointer moves to 7, right pointer moves to 2? According to the 4th rule, it should stop at 6 as 6 > 6 is false. How did you gone past the 6 and selected 2? Or am I missing something? – Totalitarian

Answer 2

Quick Sort Given an array of n elements (e.g., integers):
-If array only contains one element, return
-Else
  pick one element to use as pivot.
  Partition elements into two sub-arrays:
    Elements less than or equal to pivot
    Elements greater than pivot
  Quicksort two sub-arrays
  Return results

Let i and j are the left and right pivots, then code for one array will look like this:

1) While data[i] <= data[pivot]
    ++i
2) While data[j] > data[pivot]
    --j
3) If i < j
    swap data[i] and data[j]
4) While j > i, go to 1.
5) Swap data[j] and data[pivot_index]

Position of index j is where array is to-be partitioned in two half and then same steps are applied to them recursively.

At last you gets an sorted array.

Lucrece

Answer 3

Your confusion is because you think the partition should be the landmark separating the two. This is not true (for middle element pivot)!

• Lomuto's partition (pivot = most right partition). Left: (lo ... p-1) (note the pivot is not included) Right: (p+1 ... high)
• middle element as the pivot. The segment is partitioned: Left: (lo ... p) Right: (p+1 ... high) [https://en.wikipedia.org/wiki/Quicksort]

Federica

Answer 4

Why pivot doesn't comes at its right index after partitioning?

This is because the partition method you are using is Hoare's partition.
Actually there are two types of partitioning in quick sort Lomuto’s partition and Hoare’s QuickSort.
Hoare's partition is faster (it use two pointer at extremes so make three times less comparisons) ,
But the problem is that in Haore's partition there is no gaurantee that the pivot will be placed at the correct index after the partition.
It just gaurantees that there will be two partition one having the higher values and one having lower values.

If we want that the pivot always comes at the correct index after partitioning then we must use the Lomuto’s partition.

In lomuto partition we take pivot as the last element of the array:

    int partition(int low,int high,int *arr){

    int pivot = arr[high]; // pivot
    int i = (low - 1);     // Index of smaller element

    for (int j = low; j <= high - 1; j++)
    {
        if (arr[j] <= pivot)
        {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
       return i+1; //i+1 will be the index of pivot after partition 
       //which is also its correct index
    }

Lets workout on the following example:
1 7 3 14 2 13
pivot = 13
After partition : 1 7 3 2 13 14 --> 13 is at correct index

For further reading ,please refer the following article: https://www.geeksforgeeks.org/hoares-vs-lomuto-partition-scheme-quicksort/

Pillsbury