Re: help with C algorythm (find unique value in an array) could you please make changes
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/
Reply to: