# quick sort

i attempt to alter the quick sort code to choose the pivot as median of first, middle and last element,but i couldnot achieve my aim. my code is:
template<class type>
void quick_sort(type* darr,int size, int lb, int ub)
{
int a;              // key holder //
int up, down;
int temp;           // temporary variable, used in swapping //

if (lb >= ub)
return;

a = darr[(lb+ub)/2];
up = ub;
down = lb;

while (down < up)
{
while (darr[down] <= a)         // scan the keys from left to right //
down++;
while (darr[up] > a)             // scan the keys from right to left //
up--;
if (down < up)
{
temp = darr[down];          /* interchange records */
darr[down] = darr[up];
darr[up] = temp;
}
}

darr[lb] = darr[up];                /* interchange records */
darr[up] = a;

quick_sort(darr,size, lb, up-1);         /* recursive call - sort first subtable */
quick_sort(darr, size,up+1, ub);         /* recursive call - sort second subtable */

}

how to choose pivot in the way i desire?
###### Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
Try

a = darr[lb+(lb+ub)/2];

instead. Others even set it to "a = darr[lb];", see e.g. the examples at http://en.wikipedia.org/wiki/Quicksort
0
Commented:
You need to write some code to find the median value.  You don't have any now.  You could write a big nested if statement to find it, or you could put the three values in an array, sort them, and take the second, whichever you find easiest.

Although your current code takes the pivot from the middle element, the post-loop code is written for the pivot being the first element.  You will have to fix this too.  After you find the median, you could save where it came from and use that after the loop to do the right exchange, but it will be simpler to swap the median with the first element before the loop and keep the code you have.
0
Commented:
Finding the median costs extra time that will slow down sorting in most cases. You may consider to take a random index between lb and ub instead:

pivot = lb + rand()%(ub-lb);

To avoid the rand() overhead as well you may use a static array of random numbers instead:

static int randarr = { 1234, 623, 7621, 9, 2800, ... };
...

pivot = lb + (randarr[(ub l lb)%(sizeof(randarr)/sizeof(int))] % (ub - lb));
0

Experts Exchange Solution brought to you by