The original poster wants complexity < O(n log n). But quicksort is
not guaranteed to be even O(n log n). It can degenerate to as bad as
O(n^2), depending on the input order.
It is easy to do in O(n) if you use extra storage equal in size to the
input array. But I don't know of any algorithm requiring only O(1)
extra space or even O(log n) extra space that has complexity less than
O(n log n).
Dave
On Oct 30, 9:32 am, "ajay mall" <[EMAIL PROTECTED]> wrote:
> Use quick sort..........if u don't want to use any extra memory...
> On Tue, Oct 14, 2008 at 7:53 AM, Geoffrey Summerhayes <[EMAIL
> PROTECTED]>wrote:
>
>
>
>
>
>
>
> > On Oct 13, 10:52 am, "sharad kumar" <[EMAIL PROTECTED]> wrote:
> > > its possible
> > > take gn array.
> > > find median
> > > then split arraay in two halves
> > > split it till it becomes smallest no.
> > > then exchange each even no with odd and merge them.= till u get original
> > array.
> > > almost the reverse form of merge sort
>
> > Why get so complex?
> > You have essentially two sorted arrays waiting for a final merge.
>
> > max <- size(input)
> > even <- 0
> > odd <- 1
> > i <- 0
> > result <- makearray(max)
> > while i < max
> > ;; four cases
> > if(even >= max) ;; even is done
> > {
> > result[i] <- input[odd]
> > odd <- odd+ 2
> > }
> > else if(odd >= max) ;; odd is done
> > {
> > result[i] <- input[even]
> > even <- even + 2
> > }
> > else if(input[odd]>input[even]) ;; even is smaller
> > {
> > result[i] <- input[even]
> > even <- even + 2
> > }
> > else ;; take the odd
> > {
> > result[i] <- input[odd]
> > odd <- odd + 2
> > }
> > i <- i+1
> > end while
>
> > ---
> > Geoff
>
> --
> Thanks.
>
> Ajay Mall
> 2524,Tidewater Drive,Pelican Pointe Apt.
> Slidell, LA 70458
> Contact me @ 1-985-643-7762- Hide quoted text -
>
> - Show quoted text -
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
