Timeline for Can anyone give an example for worst case of quick sort if we employ median of three pivot selection?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 18, 2018 at 18:55 | answer | added | Bruce Lilly | timeline score: 9 | |
| Apr 24, 2016 at 3:30 | comment | added | user47605 | If first value or last value is selected as pivot, I know what would happen(and that's what tons of sites online talk about), but I specifically asked for median selected pivot's worst case. | |
| Apr 23, 2016 at 10:26 | comment | added | greybeard |
I have searched online for quicksort's worst case, but did you try to think? What is the worst case picking, e.g. the first value as pivot, and why? Are equal keys allowed? When does median of three do no better than first?
|
|
| Apr 23, 2016 at 5:25 | comment | added | D.W.♦ | Try creating a counterexample. It's not as hard as you might think. Play with some small examples of input arrays, to construct examples where quicksort will be very inefficient. It will be instructive and fun. You can do it -- give it a try! Then edit the question and show us what you've tried. You suggest making the pivot the largest element; that sounds promising. Can you do that? (possibly with a slight tweak) Can you arrange that that happens on every iteration? | |
| Apr 23, 2016 at 5:12 | comment | added | user47605 | I am a student yes, but this is absolutely not part of my exercise or anything. My professor said that to overcome the worst case of O(n^2), we choose the median pivot, which led me to thinking if there was an upper cap even for this algorithm. That's all. And I have no idea how to even analyze such algorithms, hence the question. I was thinking if the pivot happened to be the largest element in the array, then maybe it's the worst case, but I am not sure if this is indeed worst case and on top of that I don't know what complexity would be in this case, hence the question. | |
| Apr 23, 2016 at 4:09 | comment | added | D.W.♦ | What are your thoughts? What have you tried? Where did you get stuck? Have you tried constructing a counterexample? We want to help you understand concepts, not do your exercise for you. | |
| Apr 23, 2016 at 3:45 | review | First posts | |||
| Apr 24, 2016 at 1:01 | |||||
| Apr 23, 2016 at 3:44 | history | asked | user47605 | CC BY-SA 3.0 |