Why is it a good idea to choose a random pivot when using quicksort?

I've been looking at different implementations of quicksort with different ways of optimizing it. One of the optimizations that is really confusing is the idea of choosing the pivot randomly. It just seems counter intuitive to me that randomly choosing a pivot would lower the probably of achieving the worst case scenario(if you already have a sorted array as a simple case). The idea of choosing the best pivot is to divide the array into equally balanced sub arrays so that you dont run into the scenario where there is nothing to the left or right side of the pivot(this is the case when you a sorted array or a reverse sorted array and cause quicksort to run in big-oh n^2). If that is the case, why not just make the middle of the array the pivot? If someone can explains this better to me that would be great.

Quote:

---

If that is the case, why not just make the middle of the array the pivot?

---

It depends on what you mean by the middle of the array. If you mean position-wise, then there is little guarantee that the pivot is a good one. You can craft an array that puts one of the extreme elements in the middle and end up with poor performance.

Choosing a random value separates the pivot value from the order of the array's contents, meaning that chances are high for getting a good pivot by doing the same thing: calling a PRNG. The perfect pivot does not necessarily have to be in the array, either.

Ok, I think I understand.

So I can do this to ensure that each position in the array has equal possibility of getting picked as the pivot.

Code:

---

int pivot = start + rand() % (end - start + 1)

---

Note, I know that rand() is sometimes a bit bias with how it chooses its random numbers, but I think it is fine for my purposes.

Yeah. I can't say I like random pivot values; you just asked me how it was good. I don't see much of a point in selecting a random value from the array, either. My personal favorite way is to average some of the array's values to make a pivot.

Well I'll implement it for practice and see how well it does. Once I'm done I guess I will post it here.

Well I finished implementing it with a random pivot and insertion sort and this is what I got.

Code:

---

void quickSort(struct Card *hand, int start, int end)
{
    if(start < end)
    {
        if((end - start) < MINIMUMNUMBER) // If it is less than 10 cards, do insertion sort.
        {
            insertionSort(hand, start, end + 1);
        }
        else
        {
            int partitionIndex = randomPartition(hand, start, end);
            quickSort(hand, start, partitionIndex - 1);
            quickSort(hand, partitionIndex + 1, end);
        }
    }
}


int randomPartition(struct Card *hand, int start, int end)
{
    int pivotIndex = start + rand() % (end - start + 1);
    const int *pivotPtr = hand[pivotIndex].faceValue;


    int partitionIndex, index;
    swapCards(&hand[pivotIndex], &hand[end]);
    partitionIndex = start;


    for(index = start; index < end; index++)
    {
        const int *temp = hand[index].faceValue;


        if((*temp) <= (*pivotPtr))
        {
            swapCards(&hand[index], &hand[partitionIndex]);
            partitionIndex++;
        }
    }


    swapCards(&hand[end], &hand[partitionIndex]);


    return partitionIndex;
}


void insertionSort(struct Card *hand, int start, int end)
{
    int index1;


    for(index1 = start + 1; index1 < end; index1++)
    {
        struct Card temp = hand[index1];
        int index2;


        for(index2 = index1 - 1; index2 >= 0 && *(temp.faceValue) < *(hand[index2].faceValue); index2--)
        {
            hand[index2 + 1] = hand[index2];
            hand[index2] = temp;
        }
    }
}

---

It works and sorts a deck of cards pretty nicely. Now what I want to do is to make this generic and my swap also generic because as it stands, it can only swap cards

Here is how the swap looks if you want to see

Code:

---

void swapCards(struct Card *card, struct Card *cardToSwap)
{
    /*Create a struct to temporarily hold data*/
    struct Card temp;
    temp = *card;
    *card = *cardToSwap;
    *cardToSwap = temp;
}

---

What would be a seemingly good way to do this in C?

Look at how qsort allows for a comparator to be provided.

Incidentally, instead of naming your function randomPartition, perhaps you should remove the "random" part of the name to a function like randomPivot that returns the index of a randomly selected pivot. This way, you can more easily implement other pivot selection strategies to compare.