CODEWITHSUNDEEP
arrayssortingquicksort
Yousuf Khan
Yousuf Khan

Reputation: 334

How to choose pivot value in QuickSort?

I have been studying quick sort for a few hours and am confused about choosing a pivot value. Does the pivot value need to exist in the array?

For example if the array is 1,2,5,6 , can we use the value 3 or 4 as a pivot?

We use the position of pivot for dividing the array into sub-arrays but I am a little confused about what will be the pivot position after we move values < 5 to left of the array and values > 5 to right?

7,1,5,3,3,5,8,9,2,1

I dry runned the algo with the pivot 5 and came with the following result:

1,1,5,3,3,5,8,9,2,7
1,1,5,3,3,5,8,9,2,7
1,1,5,3,3,5,8,2,9,7

We can see that the value 2 is still not in the correct position. What am i doing wrong? Sorry if it's a silly question.

I came up with the following code but it's only working when pivot = left, I can't use a random pivot.

template <class T>
void quickSort(vector <T> & arr, int p, int r, bool piv_flag) {
    if (p < r) {
        int q, piv(p); counter++;

        //piv = ((p + r) / 2); doesn't work

        q = partition(arr, p, r, piv);
        quickSort(arr, p, q - 1, piv_flag); //Sort left half
        quickSort(arr, q + 1, r, piv_flag); //Sort right half
    }

    return;
}

int partition(vector <T> & arr, int left, int right, int piv) {
    int i{ left - 0 }, j{ right + 0 }, pivot{ arr[piv] };

    while (i < j) {
        while (arr[i] <= pivot) { i++; }
        while (arr[j] > pivot) { j--; }
        if (i < j) (swap(arr[i], arr[j]));
        else {
            swap(arr[j], arr[piv]);
            return j;
        }
    } 
}

Thank you.

Upvotes: 1

Views: 5267

Answers (1)

ilim
ilim

Reputation: 4547

In many applications the pivot is chosen as some element in the array, but it can also be any value you may use to separate the numbers in the array into two. If pivot value you choose is a specific element in the array you need to place it between those two groups after you partition the array into two. If not, you can just proceed with the recursive sorting process by calling the indices properly. (i.e. keeping in mind that there is no pivot element in the array, but just the two groups of values)

See this response to a similar question for a concise explanation of some widely-used alternatives for selecting a pivot.

The most important function of the pivot as to serve as a boundary between the groups we are trying to create during the partitioning phase of quicksort. The goal/challenge here is to create those groups in such a way that they are equal or almost equal in size so that quicksort can work efficiently. That challenge is the reason so many pivot selection methods are conceived. (i.e. so that at least in most cases the numbers will be separated into groups of similar size)

As to the second part of your question regarding how the position of the pivot will change once the partitioning is done, see below for a sample partitioning phase.

Say we have an array A with elements [4,1,5,3,3,5,8,9,2,1] and we chose pivot to be the first element, namely 4. The letter E used below indicates the end of the elements that are smaller than the pivot. (i.e. the last element that is smaller than the pivot)

   E
[4,1,5,3,3,5,8,9,2,1]

     E
[4,1,3,5,3,5,8,9,2,1]

       E
[4,1,3,3,5,5,8,9,2,1]

         E
[4,1,3,3,2,5,8,9,5,1]

           E
[4,1,3,3,2,1,8,9,5,5]

[1,1,3,3,2,4,8,9,5,5] // swap pivot with the rightmost element that is smaller than its value

After this partitioning, the elements are still not sorted, obviously. But all the elements that is to the left of 4 are smaller than 4, and all the ones to its right are larger than 4. To sort them, we recursively use Quicksort on those groups.

Based on your code, below is a sample partitioning code based on the procedure I described above. You may also observe its execution here.

template <class T>
int partition(vector<T>& arr, int left, int right, int piv) {
    int leftmostSmallerThanPivot = left;

    if(piv != left)
        swap(arr[piv], arr[left]);
    for(int i=left+1; i <= right; ++i) {
        if(arr[i] < arr[left])
            swap(arr[++leftmostSmallerThanPivot], arr[i]);
    }
    swap(arr[left], arr[leftmostSmallerThanPivot]);
    return leftmostSmallerThanPivot;
}

template <class T>
void quickSort(vector<T>& arr, int p, int r) {
    if (p < r) {
        int q, piv(p);

        piv = ((p + r) / 2); // works

        q = partition(arr, p, r, piv);
        quickSort(arr, p, q - 1); //Sort left half
        quickSort(arr, q + 1, r); //Sort right half
    }
}

Upvotes: 1

Related Questions