Thanks for you reply.
Yes, I can use the qsort() in standard c library to finish my work. But
what I want to know is why I was wrong. Qsort is a great, because it
shortens the sorting time from O(n^2) to O(nlogn). But I want to know
if I am thinking the wrong way against the discoverer's.
The "i++" "j--" expressions are just to skip the sticks[left] and find
the right position for it, so I don't think that's a weak point.
Also, all cases have passed under my program. Everything proves ok
logically and practically. That's what is anonying me.
adak wrote:
> 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
-~----------~----~----~----~------~----~------~--~---
