Counting the number of comparisons for merge sort

Question

So this is my code for a merge sort. But I need to find out how many times the comparisons were made during the merge function. For my code, the count output would be 0. How should I change the code to make the counter working?

#include<stdio.h>
#include<stdlib.h>

void merge(int *array,int low, int mid, int high,int count)
{
  int i=low, j=mid+1, n=low, f[high+1];

  while((i<=mid)&&(j<=high)) {
    if(array[i]>array[j]){
          f[n]=array[j];
          j++;
      }else{
          f[n]=array[i];
          i++;
      }
    n++;
    count++;
  }

  if(i>mid)
  while(n<=high) {
    f[n]=array[j];
    n++;
    j++;
    }

  if(j>mid)
  while(n<=high) {
    f[n]=array[i];
    n++;
    i++;
    }
  for(n=low;n<=high;n++)
      array[n]=f[n];
}


void mergesort(int *array, int low, int high,int count)
{
  int mid;
  if(low<high){
      mid=(high+low)/2;
      mergesort(array,low,mid,count);
      mergesort(array,mid+1,high,count);
      merge(array, low, mid, high,count);
     }
} 

int main()
{
  int size,i, count=0, *f;
  scanf("%d", &size);
  f=(int *)malloc(sizeof(int)*size);
  for(i=0;i<size;i++)
    scanf("%d", &f[i]);
  mergesort(f, 0, size-1,count);
  for(i=0;i<size;i++) {
      printf("%d",f[i]);
      if(i==size-1)
        printf("\n");
      else
        printf(" ");
    }
  printf("%d\n", count);
  return 0;
}

Instead of using `<` or `<=` etc, make a named function `lessThan` and increment the count inside this function. — Mohit Jain, Jun 02 '16 at 10:53
Function parameters in C are passed by value. That means, changing the value of a parameter inside a function does not change the original variable that the caller passed in. So the `count` needs to be returned from your function or be passed in as a pointer. — kaylum, Jun 02 '16 at 10:54
keep a static variable `counter` and increment it in `mergesort` function — piyushj, Jun 02 '16 at 10:55
You could also make `merge()` return its count (counting from 0), and do the additions in `mergesort()`. — unwind, Jun 02 '16 at 11:34
To pass the count as a pointer, write the argument as int* count, and increment it with *count++. In the main function, call mergesort with &count (i.e. pass the address of the int count variable). — Miguel Muñoz, Jun 02 '16 at 11:47

score 2 · Answer 1 · edited May 23 '17 at 10:34

2

Easiest way to accomplish this is to have one global variable count and you increment that variable each time you have comparison in Mergesort code. Either that or using pointers.

In C when you pass argument to function, that argument gets copied so original will remain unchanged. That's the problem with your code.

Please, read more here: Why would I pass function parameters by value in C?

edited May 23 '17 at 10:34

Community

1
1

answered Jun 02 '16 at 11:46

Aleksandar Makragić

1,957
17
32

Counting the number of comparisons for merge sort

1 Answers1