Author |
Topic: quick sort (Read 566 times) |
|
kirru
Newbie
Posts: 34
|
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 30th, 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 31st, 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 2nd, 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 2nd, 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 2nd, 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 median-sort
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 2nd, 2018, 9:37am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print