wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> quick sort
        
(Message started by: kirru on Aug 30^th, 2018, 8:57am)

Title: quick sort
Post by kirru on Aug 30^th, 2018, 8:57am

If median is used as pivot then quicksort in the worst case takes O(nlogn) time. Then why still worst case of quick sort is considered O(n^2) ?

Title: Re: quick sort
Post by towr on Aug 31^st, 2018, 12:35pm

I don't think it's quicksort anymore if for each partition you first need to find the median.
I also don't think you can find the actual median in O(1). (And even if you could, it sounds like something that would make the constant on the average runtime a lot higher).

Title: Re: quick sort
Post by kirru on Sep 2^nd, 2018, 2:22am

Median of median algorithm can find median in O(n) time. But it has significant overhead. But I was considering the asymptotic complexity, wouldn't it be O(n logn ) ?

Title: Re: quick sort
Post by towr on Sep 2^nd, 2018, 9:36am

Yes, you can make an algorithm that uses median of medians to sort in O(n log n). But I don't think anyone would call it quicksort.
Maybe they'd call it median-sort (https://www.safaribooksonline.com/library/view/algorithms-in-a/9780596516246/ch04s03.html)

It's probably an open discussion point what exactly makes quicksort quicksort and how much you can adjust it before it should be called something else. But once it start to become significantly less quick, I'd stop calling it quicksort.

Title: Re: quick sort
Post by towr on Sep 2^nd, 2018, 9:42am

Well, apparently wikipedia disagrees with me :P
https://en.wikipedia.org/wiki/Median_of_medians mentions it can be used as a pivot strategy for quicksort (and also that it's typically outperformed by using a random pivot)