Solved

quick sort

Posted on 2007-03-26
4
401 Views
Last Modified: 2012-06-21
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?
0
Comment
Question by:btocakci
4 Comments
 
LVL 86

Assisted Solution

by:jkr
jkr earned 100 total points
ID: 18795545
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
 
LVL 15

Assisted Solution

by:efn
efn earned 150 total points
ID: 18796447
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
 
LVL 39

Accepted Solution

by:
itsmeandnobodyelse earned 250 total points
ID: 18798012
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

Featured Post

Announcing the Most Valuable Experts of 2016

MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Python 2.7 - French characters 6 101
SQL400 max size 5 99
I could not build boost code, 10 94
How do I get Window Title of all opened process? 4 11
This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
If you haven’t already, I encourage you to read the first article (http://www.experts-exchange.com/articles/18680/An-Introduction-to-R-Programming-and-R-Studio.html) in my series to gain a basic foundation of R and R Studio.  You will also find the …
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

789 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question