tag:blogger.com,1999:blog-6314876008291942531.post3223923694766308031..comments2024-01-14T00:36:43.430-08:00Comments on Antonio Gulli's coding playground: Quicksort is O(n log n) in average. How about worst case?Unknownnoreply@blogger.comBlogger8125tag:blogger.com,1999:blog-6314876008291942531.post-36170788570660032352010-07-01T01:03:30.617-07:002010-07-01T01:03:30.617-07:00i like the second one.i like the second one.codingplaygroundhttps://www.blogger.com/profile/08478993186814330588noreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-26770594344690178882010-06-30T16:23:20.278-07:002010-06-30T16:23:20.278-07:00OK. Randomized Quick Sort provides you an expected...OK. Randomized Quick Sort provides you an expected case runtime of O(nlgn). The reason why this is expected as against worst case is that there is always a possibility of picking up a bad pivot regardless of how random your selection is. <br /><br />Thinking is if I can guarantee that my pivot selection will never be the bad one, I can guarantee worst case run time of O(nlgn) for Quick Sort. How can I guarantee that my pivot selection will never be a bad one? Thinking is using something like the "Median of Medians algorithm" to pick the pivot. <br /><br />Would the above be a valid answer?Venkateshhttps://www.blogger.com/profile/15893132887136527161noreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-4097777734006539542010-06-30T05:29:24.815-07:002010-06-30T05:29:24.815-07:00no. seletion countsno. seletion countscodingplaygroundhttps://www.blogger.com/profile/08478993186814330588noreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-11862669667316494022010-06-29T22:36:56.482-07:002010-06-29T22:36:56.482-07:00Does parallelizing the operations count as making ...Does parallelizing the operations count as making it better ?Venkateshhttps://www.blogger.com/profile/15893132887136527161noreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-15507167342133429472010-06-29T00:45:48.723-07:002010-06-29T00:45:48.723-07:003-way partitioning?3-way partitioning?Faruk Akgulhttps://www.blogger.com/profile/02809305306639454060noreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-90241671309741808632010-06-28T23:45:50.860-07:002010-06-28T23:45:50.860-07:00and without going in that direction?and without going in that direction?codingplaygroundhttps://www.blogger.com/profile/08478993186814330588noreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-57672466848335820292010-06-28T21:18:36.110-07:002010-06-28T21:18:36.110-07:00Introsort - http://en.wikipedia.org/wiki/Introsort...Introsort - http://en.wikipedia.org/wiki/IntrosortAKhttps://www.blogger.com/profile/03552400896683903007noreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-34025438790978961912010-06-28T14:59:13.422-07:002010-06-28T14:59:13.422-07:00Use IntroSort (http://en.wikipedia.org/wiki/Intros...Use IntroSort (http://en.wikipedia.org/wiki/Introsort)Venkateshhttps://www.blogger.com/profile/15893132887136527161noreply@blogger.com