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

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?