Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
Solved

quick sort

Posted on 2007-03-26
Medium Priority
407 Views
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
Question by:btocakci
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• Learn & ask questions

LVL 86

Assisted Solution

jkr earned 400 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

efn earned 600 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

itsmeandnobodyelse earned 1000 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

Question has a verified solution.

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

Windows Script Host (WSH) has been part of Windows since Windows NT4. Windows Script Host provides architecture for building dynamic scripts that consist of a core object model, scripting hosts, and scripting engines. The key components of Window…
Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a …
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
Suggested Courses
Course of the Month11 days, 21 hours left to enroll

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

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