Win a copy of Kotlin in Action this week in the Kotlin forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Issue Determing Average Number of Comparsions for Quicksort  RSS feed

 
Gabrielle Evans
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.

 
Campbell Ritchie
Marshal
Posts: 55751
163
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Campbell Ritchie
Marshal
Posts: 55751
163
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Quicksort should run in nlogn time, so you are thinking about 100×log₂100 ≅ 664 comparisons.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!