1

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
Improve this question
7
  • I think merge sort it takes 17 comparisons doesn't it? Commented Dec 17, 2014 at 0:16
  • @MooingDuck How did you get 17? Commented Dec 17, 2014 at 0:20
  • 1
    step 1: 3<24, 34<66, -5<8, 42<80, step 2: 3<34, 24<34, *, -5<42, 8<42, *, step 3: -5<3, 3<8, 8<24, 24<42, 34<42, 42<66, 66<80. In step two, two comparisons that would "theoretically" be there are skipped because of your particular data. So you're right, 15 for this input. Worst case would be 17. Random data is going to often be 15-17, with some using a few less comparisons. Commented Dec 17, 2014 at 0:22
  • 1
    The only sort that uses a fixed number of comparisons for a given N is the selection sort. That, or a poorly written bubble sort. Commented Dec 17, 2014 at 0:25
  • 1
    It's all correct and well said after the edit though =). I am not sure why people vote to close as too broad... The answer is simple, and can be concise. Commented Dec 17, 2014 at 0:35

3 Answers 3

Reset to default
1

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

I'm not sure, I think for a merge sort, the number of comparisons is going to be pretty darn close to a specific calculable value, which is also an upper bound. The only place I can think where permutation kicks in is if when merging two lists and one list is fully merged in and the rest doesn't. The rest can then be concatenated with no additional comparisons.
This is exactly why I recommend to work with histograms: they will show the spread of the distribution. This important aspect is very rarely addressed in courses, as it is pretty difficult to compute.
0

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.

Improve this answer

1 Comment

I honestly don't think it changes much. Formula that gives exact number of comparisons based just on the size of the input does not exists. That being said, my answer just gives the answer, and a basic proof, Yves' one is probably more educational and fun =)
0

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.