Thanks Hassan. But I was more interested in knowing the mathematic proof of Partial Quick Sort.
-- Amitesh On Sun, Jun 17, 2012 at 7:54 PM, Hassan Monfared <[email protected]>wrote: > 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. > -- 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.
