How to make pivot element generic inside Quicksort?

I am trying to sort 100k elements present in a file using quicksort.My algorithm works only if I use first element as pivot.How can I make pivot element generic to the program?What is the best way to choose a pivot element using quicksort?Is pivot element dependent on the data or do we use any specific algorithms in real time?

void quicksort(int *temp,int p,int r)
{
    if(r > p + 1)
    {
        int piv = temp[p];
        int left = p + 1;
        int right = r;
        while(left < right)
        {
            if(temp[left] <= piv)
                left++;
            else
                swap(&temp[left], &temp[--right]);
        }
        swap(&temp[--left], &temp[p]);
        quicksort(temp, p, left);
        quicksort(temp, right, r);
    }
}

Answers


The constraint on your pivot selection is that it needs to be fairly fast. Common approaches are choosing the first element, choosing the middle element, or choosing a random element.

Using a random element is probably best, because it will still tend to have fast sorts even for lists that are already ordered (using the first element will perform very poorly on sorted lists because all of the following elements will fall on one side of the pivot).

Using the middle element is also fairly bulletproof, unless your list is in some strange nonstandard order such like you would find by concatenating two lists sorted in opposite orders.

I recommend a random selection.

My algorithm works only if I use first element as pivot

When you say this, do you mean it produces a mis-sorted list if your pivot is not the first element? Can you go into greater detail?


Need Your Help

Is this a valid pattern for raising events in C#?

c# multithreading events locking thread-safety

Update: For the benefit of anyone reading this, since .NET 4, the lock is unnecessary due to changes in synchronization of auto-generated events, so I just use this now:

jQuery check hover status before start trigger

jquery triggers slider

i create a small slider plugin with jquery. the images would slide 5% in from left or right when the mouse is over the left or right controll div. On click the image slides in to 100%