Quick-sort Worst case time complexity?

Question

I am working on a Project that improves the Quick-sort algorithms worst case time complexity. I modified the algorithm by choosing the median pivot instead of the left most selection and introduced insertion sort after a certain number of iterations. The results are as follows:

For an input of unsorted data of length 5000 to 100000:

The number of Comparison made in my modified Quick-sort are very less than the number of comparisons made in regular Quick-sort.
Elapsed time for both is zero secs for all length if data.

For an input of already sorted data of length 5000 to 100000:

The number of Comparison made in my modified Quick-sort are still very less than the number of comparisons made in regular Quick-sort.
Elapsed time for my modified Quick-sort is very less than the elapsed time of the regular Quick-sort for all length of data.

How can I now prove that the time complexity O(n^2) for already sorted data has been improved? I have all the above data but dont know how to theoretically show it? No direct answers but hints will be fine.

A little secret. "your" improvement has already been discovered so many years ago. — Aurelio De Rosa
– Aurelio De Rosa, Commented Dec 3, 2011 at 3:00
I know. But I had to implement it on my own instead of just copying the concepts from somewhere. — user1031752
– user1031752, Commented Dec 3, 2011 at 3:04
@AurelioDeRosa I believe Robert Sedgewick's career got launched with these improvements. See "The Analysis of Quicksort Programs, " Acta Informatica 7, 1977. — Raymond Hettinger
– Raymond Hettinger, Commented Dec 3, 2011 at 3:07
You will have to use probability theory and do some math. There is no other way. Counting comparisons might suggest some trends, but its certainly not a proof. — malejpavouk
– malejpavouk, Commented Dec 3, 2011 at 16:19

Raymond Hettinger · Accepted Answer · 2011-12-03 03:15:15Z

2

The usual way to demonstrate algorithmic improvements in sorting algorithms is to instrument the code to count the number of comparisons and then run different algorithms over several different datasets, each with different characteristics (random, already sorted, reverse sorted, mostly sorted, etc).

A good model for this kind of analysis is Tim Peter's write-up for his Timsort algorithm: http://hg.python.org/cpython/file/2.7/Objects/listsort.txt

edited Dec 3, 2011 at 3:15

answered Dec 3, 2011 at 3:01

Raymond Hettinger

229k67 gold badges405 silver badges504 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Quick-sort Worst case time complexity?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related