Author 
Topic: quick sort (Read 566 times) 

kirru
Newbie
Posts: 34


quick sort
« on: Aug 30^{th}, 2018, 8:57am » 
Quote Modify

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) ?

« Last Edit: Aug 30^{th}, 2018, 8:57am by kirru » 
IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: quick sort
« Reply #1 on: Aug 31^{st}, 2018, 12:35pm » 
Quote Modify

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).


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



kirru
Newbie
Posts: 34


Re: quick sort
« Reply #2 on: Sep 2^{nd}, 2018, 2:22am » 
Quote Modify

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 ) ?

« Last Edit: Sep 2^{nd}, 2018, 2:24am by kirru » 
IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: quick sort
« Reply #3 on: Sep 2^{nd}, 2018, 9:36am » 
Quote Modify

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 mediansort 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.

« Last Edit: Sep 2^{nd}, 2018, 9:37am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



