On Monday 05 February 2007 16:51, you wrote: > Kamaraju Kusumanchi wrote: > > [snip] > > > 2. In the worst case, your algorithm scales as O(N^2). If I am not wrong, > > you can do this in O(N log(N)) steps. If your N is large (say > 1000) > > this has a huge benefit. The algorithm would be > > One can do that using, for example, heapsort. But there > are sort algorithms which run in O(N) time, if sufficient > memory be present. > > > a. use a quicksort technique to sort the input array > > In worst case, quicksort runs in O(N^2) time. Not the best choice, IMO.
Thanks for correcting me. I went back and looked into numerical recipes in Fortran77, Fortran 90. You are absolutely right! Quicksort's worst case (a presorted array) runs at O(N^2). He should use heapsort as it requires no auxiliary storage and even the worst case scales as O(N logN). raju -- Kamaraju S Kusumanchi http://www.people.cornell.edu/pages/kk288/ http://malayamaarutham.blogspot.com/ ---------------------------------------------------------------------- Click to consolidate debt and lower month expenses: http://tags.bluebottle.com/fc/CAaCMPJklgwHwcSyYn1ZRFvO6pT3HNh6/ -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
