My objective is to execute quick sort ( i was told to convert the pseudocode from the Cormen book) using arrays of increasing sizes and find the average number of comparisons for each of those sizes over 100 iterations. This is a school project and the numbers I am getting are far larger than those of my friends, so I am clearly doing something wrong. I believe it must be in the way that I am collecting and averaging my number of comparisons. I will first give the method in which most of that calculating is done, then I will include the whole program.
I am incrementing the variable comparisonCount for each comparison done and adding that to an array of all the comparison numbers for that array size. I am then running through that array, averaging it, and placing that average into another array.
I suggest you get a common or garden quicksort running, and later add comparisons++ in one place.
You have some oddities: why are you zeroing comparisons in the loop? Are you using integer arithmetic for working out the average? Remember 99/100 is 0.
posted 4 years ago
Quicksort should run in nlogn time, so you are thinking about 100×log₂100 ≅ 664 comparisons.