wu :: forums
wu :: forums - quick sort

Welcome, Guest. Please Login or Register.
May 19th, 2024, 10:01am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs
(Moderators: Icarus, william wu, Eigenray, towr, Grimbal, SMQ, ThudnBlunder)
   quick sort
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: quick sort  (Read 552 times)
kirru
Newbie
*





   


Posts: 34
quick sort  
« on: Aug 30th, 2018, 8:57am »
Quote Quote Modify 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 30th, 2018, 8:57am by kirru » IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: quick sort  
« Reply #1 on: Aug 31st, 2018, 12:35pm »
Quote Quote Modify 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 Quote Modify 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: male
Posts: 13730
Re: quick sort  
« Reply #3 on: Sep 2nd, 2018, 9:36am »
Quote Quote Modify 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
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: quick sort  
« Reply #4 on: Sep 2nd, 2018, 9:42am »
Quote Quote Modify Modify

Well, apparently wikipedia disagrees with me Tongue  
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)
« Last Edit: Sep 2nd, 2018, 9:53am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board