Thomas.Chang wrote:
> Following is a qsort() program, I checked it carefully severally times
> and tested with a lot of cases without finding any error. But when I
> submit the program using it to online judge, it always "wrong answer",
> if I substitute it with the standard qsort() of c library, it will
> pass.
> I post it here wishing someone can point out my mistakes. It's really
> frustrating having problem with such basic, simple algorithms.
>
> -----------------------------------------------------------------------------------
> int sticks[100];
> void sort(int left,int right){
> int pivot, i, j;
> int temp;
> if(left<right){
> i=left; j=right+1;
> pivot = sticks[left];
> do{
> do i++;
> while (i<=right && sticks[i] < pivot );
> do j--;
> while (j>=left && sticks[j] > pivot);
> if(i<j && i<=right && j>=left) {
> temp = sticks[i];
> sticks[i] = sticks[j];
> sticks[j] = temp;
> }
> }while(i<j);
> if(j>left){
> temp = sticks[left];
> sticks[left] = sticks[j];
> sticks[j] = temp;
> }
> if(left<j) sort(left,j-1);
> if(j<right && left<=j) sort(j+1, right);
> }
> }
Quicksort is anything BUT a simple or basic algorithm. It took the best
minds in CS years to come up with it's elegance and speed. (The
discoverer was knighted for this, and several other contributions to
the field of CS).
Quicksort is a "fragile" algorithm, easily broken by any little
addition or subtraction. In comparing a good version, with yours above,
my version did not have the following unneeded line:
do i++; //<<< this is unnecessary, you haven't DONE anything yet,
why would you want to increment a variable, here?
while (i<=right && sticks[i] < pivot ); //<< it can go here.
same with the j logic which follows. Also, it did not have the "j-1" in
the recursive call at the end to sort, is just "if(left<j) sort(left,
j);
Unless you have the time to really test and the skill to alter
Quicksort, why not just use a known good version? Either the standard
library for your language, or a known good one (like the one in K&R
"The C Programming Langauge", or one of Sedgewick's versions).
Even Microsoft has released Quicksort code which was about 15% slower
than it should have been, simply because they mis-placed a single line
of code.
There are many good version of Quicksort out there. Find one you like,
and use it. Using an extra do loop, or an earlier incrementing may not
seem like much, but with Quicksort, it IS a big deal. It's a remarkable
algorithm, and it's remarkably fragile and easy to knock it into a
cocked hat.
Adak
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
