wu :: forums « wu :: forums - quick sort » Welcome, Guest. Please Login or Register. May 19th, 2024, 10:01am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    cs (Moderators: Icarus, william wu, Eigenray, towr, Grimbal, SMQ, ThudnBlunder)    quick sort « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: quick sort  (Read 552 times)
kirru
Newbie

Posts: 34
 quick sort   « on: Aug 30th, 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 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
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

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

Well, apparently wikipedia disagrees with me
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 Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft => cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »