quick sort is worst case O(n^2) On 12 April 2011 18:17, Akash Agrawal <[email protected]> wrote:
> since we are bubbling up, it's again is a O(n^2). > > Is there anything possible like O(n) in constant space. I tried on swapping > values but mees it somewhere... here are intermediate steps in my approach. > > > 1, 5, 7, 9, 11, 2, 3, 8, 9, 21 > > 1, 2, 7, 9, 11, *5*, 3, 8, 9, 21 > > 1, 2, 3, 9, 11, *5, 7*, 8, 9, 21 > > 1, 2, 3, 5, 11, 9, 7, 8, 9, 21 > > 1, 2, 3, 5, 7, 9, 11, 8, 9, 21 > > 1, 2, 3, 5, 7, 8, 11, 9, 9, 21 > > 1, 2, 3, 5, 7, 8, 9, 11, 9, 21 > > 1, 2, 3, 5, 7, 8, 9, 9, 11, 21 > > Regards, > Akash Agrawal > http://tech-queries.blogspot.com/ > > > On Tue, Apr 12, 2011 at 10:23 PM, powerideas <[email protected] > > wrote: > >> say we hav array {101,102,103,104(ptr1),1,2,3,4(ptr2)} >> >> >> 1.take end of 1 st array in ptr1 & end of 2nd array in ptr2 >> 2.IF (ptr1>ptr2) >> >> bubble up ptr1 to ptr2; >> ptr2-- >> ptr1-- >> >> ELSE >> ptr2--; >> >> >> 1.compare last element of both arrays ie 104 & 4 since 104>4 >> bubble up 104 to end since it will be greater than whole 2 nd array >> so {101,102,103(ptr1),1,2,3,4(ptr2),104} >> moving on............ >> >> ex 2 : {1,3,5,7(ptr1),2,4,6,8(ptr2)} >> 7<8 so ptr2-- {1,3,5,7(pr1),2,4,6(ptr2), >> 8}----------------> {1,3,5(ptr1),2,4,6(ptr2),7,8} moving on.......... >> >> -- >> 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.
