Algorithm Efficiency question

Damien Allen

I am completing an assignment and I'm stuck on the final part. I have to write a program in C that will generate a list of random numbers (Floats) and then sort them using the following sorts, Bubble sort, Quick sort, Heap Sort and Bucket Sort whilst keeping track of swaps and comparisons.

I have completed this section sucessfully·but I now need to derive the expected number of swaps and compares for the above sorts, which I haven't a clue where to start.

Can anybody point me in the right direction? I have managed to find information on Bubble sort but nothing else.

phil kenny

Google is your friend. Some of your questions may be answered here:

en.wikipedia.org/wiki/Random_permutation_statistics

phil

Damien Allen

I'm not sure that is what I need. I need to derive two equations from each sort that will approximate the number of swaps and the number of compares

Gadgetman

Well...

You may want to check up something called 'Big O' notation...
http://en.wikipedia.org/wiki/Big_O_notation
(The most sloppy and inaccurate math, even more inaccurate than a restaurant tab... )

The formula for calculating the number of calculations of a bubblesort algorithm is O(n²) I think.
(A while since I had to do this kind of math)
This means that the number of Operations increases rather fast as the number of entries increases.
(In this case, a 10-item list will give approx 100 comparisons, 100 items will give 10.000 comparisons... Yes, bubblesort is rather inefficient)




▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Don't visit my new website...

Damien Allen

Unfortunately I cannot use big O notation, for example the number of comparisons for bubble sort is = n(n-1)/2. I must generate similar equations for quick sort and heap sort and also bucket sort