CODEWITHSUNDEEP
arraysalgorithmsorting
Plrr
Plrr

Reputation: 53

Total Comparisons of Sorting Algorithms to Complete Sort

I want to find the total comparisons for sorting n elements in an array using different sorting algorithms. I don't want to do it manually (in case the number of elements in the array is considerably large). Is there a "formula" to calculate the comparisons for each of the sorting algorithms listed below if for example there is 8 elements in an array containing the following elements [3,24,66,34,8,-5,42,80]? How can I find the comparisons for each?

1) Merge Sort

For example, if I use Merge sort manually in order to find the total numbers of
comparisons for 8 elements, this is what I get:

       3, 24, 66, 34, 8, -5, 42, 80    

     3, 24, 66, 34      8, -5, 42, 80    

    3, 24    66, 34     8, -5    42, 80   

 3  24    66    34       8   -5   42    80    

    3, 24    34, 66     -5, 8    42, 80 

      3, 24, 34, 66      -5, 8, 42, 80  

       -5, 3, 8, 24, 34, 42, 66, 80

 Total number of comparisons  needed to sort this array = 15 
 I would like to be able to do this using a formula, if possible, not manually.


2) Insertion sort

Upvotes: 1

Views: 1231

Answers (3)

DanielTheRocketMan
DanielTheRocketMan

Reputation: 3249

Usually people do not make this kind of calculation. They are interested in evaluating the complexity of the algorithm, i.e., "asymptotically How the number of comparisons increases with the size of the input"

For instance, merge sort grows (in average) with O(n log n). This means that the number of comparisons of merge sort is not worse than n log n where n is the size of the input. There are some methods to arrive to this expression, namely master theorem or tree method.

Actually, one can prove that no algorithm based only on comparisons cannot make less comparisons than n log n. This is the so-called comparison model! comparison algorithms

However, sorting can be done in linear time, depending on the type of your set, for instance using counting sort - a kind of histogram.

Upvotes: 0

user1196549
user1196549

Reputation:

This is not an easy task, as it can depend on details of the algorithm implementation, and also is not a pure function of n.

Actually, what you get is a distribution of values of the number of comparisons, depending on the permutation of the input. Usually, one distinguishes the best case (least number of comparison), the worst case (largest number) and the average case (mathematical expectation when you assume the respective probabilities of the input permutations).

These numbers can be obtained by reasoning on the program, but this is usually a difficult task (even daunting for the average case), often solved with approximations.

Anyway, you can obtain it empirically by instrumenting your program: declare a counter variable, and increment it at the same time as a comparison is made.

I recommend you to do what follows as an exercise:

  • instrument the code as I said,
  • take the sequence of the n first integers;
  • generate all possible permutations of the input (there will be exactly n! possibilities - as long as n remains small, say n up to 10, this remains manageable, 10!=3628800) and run the algorithm on each;
  • (alternatively you can fill the array with random numbers and repeat many times);
  • accumulate the histogram of the number of comparisons (for every possible number of comparisons count how many permutations achieve it),
  • observe and compare the histograms of the different algorithms.

Even though n will remain modest, you will observe the best and worst cases, and with more care, the central trend and the spread. This should be instructive.

Using the same methodology, you can also observe the number of element displacements.

Upvotes: 1

luk32
luk32

Reputation: 16090

It is impossible, as the exact number depends on the input. This why you have optimistic complexity, pessimistic, and average sometimes also called expected. The prominent example is basic implementation of quick sort which has pessimistic complexity O(n^2). On the other hand optimistic case for bubble sort is O(n). More examples: http://en.wikipedia.org/wiki/Best,_worst_and_average_case#Sorting_algorithms.

The only thing you can do is to compute it per problem instance, for example by tapping into comparison function. Although, I am not sure if per-instance values are very meaningful.

Upvotes: 0

Related Questions