c++ and quicksort

E

Exekute

Someone help! my quicksort isn't very quick. It's only like 25%
faster than selection sort (or insertion sort). This is also like 100
times slower than my merge sort. If it's supposed to be that slow
then someone tell me. Otherwise someone that's good at algorithm
analysis help me out. I know it's hard to trus people, but it's not a
noob mistake somewhere else in the program (teacher wrote everything
else). I'll give my quicksort and partition code. Pre condition:
array of ints, it's first element is given by l, and it's last is
given by r. Post condition: The array is sorted.

void quick_sort(int *A,int l,int r)
{
int middle;
if ( l < r )
{
middle = partition(A, l, r);
quick_sort(A, l, middle);
quick_sort(A, middle+1, r);
}
}
/-----------------------------------PARTITION
int partition(int *A, int l, int r)
{
int p = A[l];
int tmp;
int i = l;
int j = r + 1;
for (int x = 0; x == 0; x = 0)
{
do
{
i++;
} while ( p > A );

do
{
j--;
} while ( p < A[j] );

if (i < j)
{
tmp = A[j];
A[j] = A;
A = tmp;
}
else
{
return j;
}
}
}
 
C

Chris Dams

(e-mail address removed) (Exekute) writes:

Hello,
Someone help! my quicksort isn't very quick.

And it isn't quicksort either. It does not even sort, let alone quick.
void quick_sort(int *A,int l,int r)
{
int middle;
if ( l < r )
{
middle = partition(A, l, r);
quick_sort(A, l, middle);
quick_sort(A, middle+1, r);
}
}

So after partition is called, all elements with indices smaller (greater)
than middle are supposed to be smaller (greater) than A[middle], right?
That means that you can do

quick_sort(A,l,middle-1);
quick_sort(A,middle+1,r);

but this is not your main problem.
/-----------------------------------PARTITION
int partition(int *A, int l, int r)
{
int p = A[l];
int tmp;
int i = l;
int j = r + 1;
for (int x = 0; x == 0; x = 0)

This is a useless loop since it will only be executed once. Nothing is
done to x inside the loop.
{
do
{
i++;
} while ( p > A );

do
{
j--;
} while ( p < A[j] );
if (i < j)
{
tmp = A[j];
A[j] = A;
A = tmp;
}
else
{
return j;
}

}
}


You should fix you partition function, so that it will actually do what
you want and that is.
(1) pick some element, say p, from your array (the first for instance);
(2) change the order of your array, such that you get
{ all elements < p, p, all elements >= p };
(3) return the position of p.

After you have done that, and tested it on some non-trivial example
to make sure that it actually works, you can try your quick-sort.

Good luck,
Chris Dams
 
C

Chris Dams

Hello,

(e-mail address removed) (Exekute) writes:
This is a useless loop since it will only be executed once. Nothing is
done to x inside the loop.

Actually was not paying attention. Of course it is executed over and over
until the return is executed. Still it causes undefined behaviour. There
is no reason why the i variable could not get outside the A array.
do
{
i++;
} while ( p > A );


Bye,
Chris Dams
 
E

Exekute

ok, I fixed the pointer out of bounds problem, and I also made sure it
sorts this time. Now maybe my original performance question can be
adressed. Why is it going so slow? I'm not just talking small tweeks,
like chosing a better pivot point. I'm talking like grand scheme of
things I'm screwing up somewhere massive.
 
E

Exekute

ok, I fixed the pointer out of bounds problem, and I also made sure it
sorts this time. Now maybe my original performance question can be
adressed. Why is it going so slow? I'm not just talking small tweeks,
like chosing a better pivot point. I'm talking like grand scheme of
things I'm screwing up somewhere massive.
void quick_sort(int *A, int l, int r)
{
//int wait;
int middle;
if ( l < r )
{
middle = partition(A, l, r);
quick_sort(A, l, middle - 1 );
quick_sort(A, middle + 1, r);
}

}

int partition(int *A, int l, int r)
{
int p = A[l];
int tmp;
int i = l;
int j = r + 1;
for (int x = 0; x == 0; x = 0)
{
do
{
i++;
} while ( p > A && i < r);

do
{
j--;
} while ( p < A[j] );

if (i < j)
{
tmp = A[j];
A[j] = A;
A = tmp;
}
else
{
A[l] = A[j];
A[j] = p;
return j;
}
}
}
 
T

Tony Sokhon

Try this partition function. It could work better.

int partition(int* lines, int deb, int fin) {
int compt;
int pivot;
int i;

pivot = compt = deb;

for(i=deb+1;i<=fin;i++)
{
if (lines < lines[pivot])
{
compt++;
swap(lines, compt, i);
}
}

swap(lines, compt, deb);
return(compt);
}

void swap(int* lines, int i, int j) {
int t = lines; lines = lines[j]; lines[j] = t;
}

Now note that a quicksort algorithm that uses this function will be
slower than the qosrt function that comes with the C standard library,
and I don't know exactly why.
If you want to speed up your algorithm, here are some hints :
1 - When choosing the pivot in the partition function, make sure to
choose an element that splits the initial array into fairly equal
parts. Practically, you could achieve this by choosing the median
element between, say, the first, the middle element, and the last
element of the array.
2 - When you call partition, you should check the length of the
partitions you get. If one of these contains less than 10-20 elements,
sort it using standard selection (or insertion) sort, because
quicksort on such a small array is slower than the standard sorting
algorithms.

good luck.
 
J

Jerry Coffin

[ ... ]
2 - When you call partition, you should check the length of the
partitions you get. If one of these contains less than 10-20 elements,
sort it using standard selection (or insertion) sort, because
quicksort on such a small array is slower than the standard sorting
algorithms.

One of Sedgewick's (few) contributions to the world was noting that you
can delay this: instead of doing an insertion sort on each partition
separately, you can delay it and do one insertion sort after you're
finished doing the partial sorting on the entire array.

Note that in this case you definitely want to use an insertion sort
instead of a selection sort though -- the selection sort won't work well
under these circumstances. The insertion sort does, though, because its
speed is largely proportional to how far a given element is from its
final placement, and the partial sort with the quicksort ensures that's
never very far.

Exactly how much this gains will depend on the overhead of a function
call -- the lower it is, the less you save with this. It does a LOT of
good on older Intels, but virtually none on most SPARCs.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top