quick sort and O(nlgn) worst case bound
in [General Programming]
|
From: mohangupta13 on 28 Nov 2009 10:23 hello all , Using median of median or just median to choose the pivot in quick sort it can be deterministically proved that the worst case running time of quicksort is O(nlgn) and not O(n^2) . So why is that quick sort is still blamed to be having a worst case of O(n^2).?? Is there some problem with the above mentioned methods of choosing the pivot ? thanks Mohan
From: Willem on 28 Nov 2009 10:35 mohangupta13 wrote: ) hello all , ) Using median of median or just median to choose the pivot in quick ) sort it can be deterministically proved that the worst case running ) time of quicksort is O(nlgn) and not O(n^2) . ) ) So why is that quick sort is still blamed to be having a worst case of ) O(n^2).?? ) Is there some problem with the above mentioned methods of choosing the ) pivot ? Finding the median. SaSW, Willem -- Disclaimer: I am in no way responsible for any of the statements made in the above text. For all I know I might be drugged or something.. No I'm not paranoid. You all think I'm paranoid, don't you ! #EOT
From: mohangupta13 on 28 Nov 2009 10:58 On Nov 28, 8:35 pm, Willem <wil...(a)stack.nl> wrote: > mohangupta13 wrote: > > ) hello all , > ) Using median of median or just median to choose the pivot in quick > ) sort it can be deterministically proved that the worst case running > ) time of quicksort is O(nlgn) and not O(n^2) . > ) > ) So why is that quick sort is still blamed to be having a worst case of > ) O(n^2).?? > ) Is there some problem with the above mentioned methods of choosing the > ) pivot ? > > Finding the median. we have well defined algorithm that can find the median in linear time worst case and that linear time can be absorbed in the partition step of quicksort(which is also linear time) giving a overall worst case running time of O(nlgn) > > SaSW, Willem > -- > Disclaimer: I am in no way responsible for any of the statements > made in the above text. For all I know I might be > drugged or something.. > No I'm not paranoid. You all think I'm paranoid, don't you ! > #EOT
From: Willem on 28 Nov 2009 11:12 mohangupta13 wrote: ) On Nov 28, 8:35�pm, Willem <wil...(a)stack.nl> wrote: )> Finding the median. ) we have well defined algorithm that can find the median in linear time ) worst case and that linear time can be absorbed in the partition step ) of quicksort(which is also linear time) giving a overall worst case ) running time of O(nlgn) Yes, but practically speaking that well defined algorithm is quite slow. SaSW, Willem -- Disclaimer: I am in no way responsible for any of the statements made in the above text. For all I know I might be drugged or something.. No I'm not paranoid. You all think I'm paranoid, don't you ! #EOT
From: mohangupta13 on 28 Nov 2009 13:26
On Nov 28, 9:12 pm, Willem <wil...(a)stack.nl> wrote: > mohangupta13 wrote: > > ) On Nov 28, 8:35 pm, Willem <wil...(a)stack.nl> wrote: > )> Finding the median. > ) we have well defined algorithm that can find the median in linear time > ) worst case and that linear time can be absorbed in the partition step > ) of quicksort(which is also linear time) giving a overall worst case > ) running time of O(nlgn) > > Yes, but practically speaking that well defined algorithm is quite slow. But here I was referring theoretical consideration , if we see practically then quicksort despite of it O(n^2) worst case is better than O(dn) radix sort all other sorting algorithms out there like merge sort and heap sort . (the randomized quick sort of-course) Even in all theoretical books i have seen them calling worst case quick sort be O(n^2) . Mohan > > SaSW, Willem > -- > Disclaimer: I am in no way responsible for any of the statements > made in the above text. For all I know I might be > drugged or something.. > No I'm not paranoid. You all think I'm paranoid, don't you ! > #EOT |