10

I was wondering if we can somehow modify the Quick sort algorithm to produce the worst case time complexity of O(n logn). Although this can be done by permuting data and then assuming that we will get the average case complexity rather than worst case. But this is not a full proof solution as we can again land into worst case after permuting. Is there any other way around that you can suggest.

pseudocode
  • 341
  • 1
  • 6
  • 15
  • 2
    A trivial way is to add two lines to the top of the function: one which does a heap or merge sort, and the second of which returns. I understand that this probably isn't what you had in mind, but I hope this illustrates that you are going to need to be more specific about what kind of "modifications" are allowed to the standard quicksort algorithm... you are going to have to be pretty precise in your limitations to make something like I have suggested off-limits. – Patrick87 Mar 01 '12 at 16:28
  • I was thinking of if we can somehow tweak the quick sort itself. Like putting some restrictions on pivot. I can just use merge sort instead of quick sort, rather than using multiple sorts. I am looking for some tweak in Quick sort only. – pseudocode Mar 01 '12 at 16:33
  • See: http://stackoverflow.com/a/70631/44522 – MicSim Mar 01 '12 at 16:36
  • Right, but adding some code - or replacing all the Quicksort code with Mergesort code - is a "tweak", albeit a fairly significant one. You mention "putting some restrictions on pivot"; that's a good example of a restriction that we can work with. I suggest either limiting the scope of your question to this particular direction, or providing a list of all such directions which are fair-game. If part of the issue is that you don't understand Quicksort well enough to feel confident you've listed all potentially valid avenues, say so, and ask for other similar suggestions. Just ideas... – Patrick87 Mar 01 '12 at 16:40
  • @pseudocode Check out the link in MicSim's comment. It seems like this question has already received fairly good attention there. – Patrick87 Mar 01 '12 at 16:43
  • @Patrick87 I wasn't aware of the option of merging multiple sorting algorithms. You are right, should have explicitly limited the scope while asking question, but it didn't cross my mind then. I really like your answer and I would definitely use it for my future implementations. – pseudocode Mar 01 '12 at 16:55
  • @MicSim Thanks!!! couldn't find it before posting the question. – pseudocode Mar 01 '12 at 16:58

2 Answers2

16

Well, Yes we can bring it down to O(nlogn). All the algorithms I have seen that try to bring this down are based on choosing your pivot point. If you can "intelligently" choose your pivot point it can be brought down.

Options 1. Intro Sort . It is no longer a "pure" quick sort now. It uses merge sort later on. 2. Choosing the median as a pivot. Now finding the median might take a huge amount of time if done in the normal way BUT there is a mention in the Introduction to Algorithms.

Here is something straight from the horse's mouth Introduction to Algorithms

  1. Divide the array into [n/5] groups with each group having 5 elements
  2. Find median of each group using insertion sort and then pick the median from this list
  3. Then you will need to recursively try and find the median of [n/5] medians calculated from each group.
  4. Partition the array around this median

There are some more complex stuff in this algorithm that I have hidden. You can go through it in the same book if you want. Usually, I don't try to use this algorithm. I use a randomized selection operation to find the pivot and work on with that.

S.P.
  • 3,054
  • 1
  • 19
  • 17
  • Thanks S.P. I guess this is what I was looking for. – pseudocode Mar 01 '12 at 16:40
  • 1
    For option 1 it is not merge sort but heap sort that a run-away quicksort switches to. You want to preserve the in-place property of quicksort. For performance reason merge sort is rarely implemented in-place, although it could be. – user515430 Dec 19 '12 at 17:48
1

Well "modify" is a rather subjective word here. There are a number of ways you can augment quicksort to make it run in O(n log n). Whether or not you could still call it a quick sort is to be determined.

One of which is introsort. Introsort starts with quicksort but then switches to merge sort which has worst-case complexity O(n log n). One of the purposes of introsort is to combat median-of-3 killer lists.

tskuzzy
  • 35,812
  • 14
  • 73
  • 140