Printable View
I want to find out how many comparisons it takes to sort N items using a quicksort.
I know on average it takes NlogN comparisons, but as this is bigOnotation im guessing the logarithmic base isnt exact.... so im going to assume that i cant just do:
Sort 1000 items
Average comparisons = 1000 * ln1000 = 6908 comparisons?
The problem with your assumption is that it is the "amortized" running time for the algorithm. There is no magic number of iterations that the algorithm will run at, it all depends on the data you get.
For example, if the array is already sorted, or the pivot choice makes the selection unbalanced, then the running time will be n^2 (approximately for unbalanced). It has nothing to do with the base of the log, it has to do with the collection of data, and the pivot choice.
If you're lucky and the pivot elements (picked at random) always happen to be the median (the array will split in half each time which is optimal) you get,Quote:
Originally Posted by scottyn
Comparisions = N * log2(N).
Exchanges = N/6 * log2(N).
If you aren't optimally lucky the average unluck still worsens the situation only by a factor of 2*ln(2), that is approximately 1.4.
(from Algorithms & Data Structures = Programs by N. Wirth)
With N=1000 (and log2(1000) = 10 approximately) you get
Comparisions = 10 * 10 * 1.4 = 140.
Exchanges = 10/6 * 10 * 1.4 = 23.
But note that this is on average only. If only a little more than average unlucky when picking pivot elements Quicksort quickly becomes Slowsort.