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 -~----------~----~----~----~------~----~------~--~---