O(N*logM)
On Sat, Jun 16, 2012 at 5:15 PM, Amitesh Singh <[email protected]>wrote:
> Hi Guys,
>
> *Problem: *Rearrange a given array with n elements, so that m places
> contain the m smallest elements in ascending order.
>
> *Solution 2:* using QuickSort method approach.
> [image: n = r -p + 1]
>
> [image: \bold{PARTIAL-QUICKSORT(A,p,r,m)}: \newline if\; p<r \newline q
> \leftarrow RANDOMIZED-PARTITION(A,p,r) \newline
> PARTIAL-QUICKSORT(A,p,q-1,m) \newline if \; q<m-1 \newline
> PARTIAL-QUICKSORT(A,q+1,r,m)]
>
> http://amiteshsingh.wordpress.com/2012/06/16/partial-sorting/
>
> I know if m = n, then complexity of Partial sorting is same as QuickSort.
> but what would be the *average case analysis* in terms of n and m?
>
> Any suggestion would be highly appreciated.
>
> --
>
> Amitesh
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
