mergesort for array of pointers to structs-CodePudding

I'm trying to write a generic mergesort for arrays holding pointers to different structs. I'm at a point that the compiler doesn't give any errors, but the sort function doesn't give the right output yet. The two structures and the two compare functions are defined as follows:

typedef struct Query {int day, rank;} Query;  

typedef struct Event {int day, frame; char action;} Event;

int compEvents (const void *a, const void *b) {
  return (*(Event**)a)->day - (*(Event**)b)->day;
}

int compQueries (const void *a, const void *b) {
  return (*(Query**)a)->day - (*(Query**)b)->day;
}

If I use qsort, everything works fine and the output is correct:

qsort (queries, size, sizeof(Query*), compQueries);

If I use a different mergesort for each type, and don't use the compare functions, everything works fine too:

void queryMerge(Query **arr, int left, int mid, int right) {
  Query **temp = newQueryArray(right-left 1);
  int i = left, j = mid   1, t = 0;   
  while (i <= mid && j <= right) {
    if (arr[i]->day < arr[j]->day) temp[t  ] = arr[i  ];
    else temp[t  ] = arr[j  ];
  }
  while (i <= mid) temp[t  ] = arr[i  ];
  while (j <= right) temp[t  ] = arr[j  ];
  for (int i = left; i <= right; i  ) arr[i] = temp[i-left];
  free(temp);
}

void querySort(Query **arr, int left, int right) { 
  if (left < right) {
    int mid = left   (right - left)/2;
    querySort(arr, left, mid);
    querySort(arr, mid 1, right);
    queryMerge(arr, left, mid, right);
  }
}

void eventMerge(Event **arr, int left, int mid, int right) {
  Event **temp = newEventArray(right-left 1);
  int i = left, j = mid   1, t = 0;   
  while (i <= mid && j <= right) {
    if (arr[i]->day < arr[j]->day) temp[t  ] = arr[i  ];
    else temp[t  ] = arr[j  ];
  }
  while (i <= mid) temp[t  ] = arr[i  ];
  while (j <= right) temp[t  ] = arr[j  ];
  for (int i = left; i <= right; i  ) arr[i] = temp[i-left];
  free(temp);
}

void eventSort(Event **arr, int left, int right) { 
  if (left < right) {
    int mid = left   (right - left)/2;
    eventSort(arr, left, mid);
    eventSort(arr, mid 1, right);
    eventMerge(arr, left, mid, right);
  }
}

However, if I try to use a generic mergesort that would work for both types just like qsort, it isn't working correctly, even though the compiler and valgrind have no complaints:

void merge(void *arr, int left, int mid, int right, int width, int (*comp)(const void*, const void*)) {
  void *temp = malloc((right - left   1) * width);
  int i = left, j = mid   1, t = 0;   
  while (i <= mid && j <= right) {
    if (comp((char*)arr   i*width, (char*)arr   j*width)) {
      memcpy((char*)temp   t*width, (char*)arr   i*width, width);
      i  ; t  ;
    } else {
      memcpy((char*)temp   t*width, (char*)arr   j*width, width);
      j  ; t  ;
    }
  }
  while (i <= mid) {
    memcpy((char*)temp   t*width, (char*)arr   i*width, width);
    i  ; t  ;
  }
  while (j <= right) {
    memcpy((char*)temp   t*width, (char*)arr   j*width, width);
    j  ; t  ;
  }
  for (int i = left; i <= right; i  ) {
    memcpy((char*)arr   i*width, (char*)temp   (i - left)*width, width);
  }
  free(temp);
}

void mergeSort(void *arr, int left, int right, int width, int (*comp)(const void*, const void*)) { 
  if (left < right) {
    int mid = left   (right - left)/2;
    mergeSort(arr, left, mid, width, comp);
    mergeSort(arr, mid 1, right, width, comp);
    merge(arr, left, mid, right, width, comp);
  }
}

This is the way it is called:

mergeSort(queries, 0, size-1, sizeof(Query*), compQueries);

I tried different things to get the void pointers right, but I'm still not sure. Any ideas?

CodePudding user response：

Your usage of comparison function is broken:

if (comp((char*)arr   i*width, (char*)arr   j*width)))

is the same as

if (comp((char*)arr   i*width, (char*)arr   j*width)) != 0)

while you need

if (comp((char*)arr   i*width, (char*)arr   j*width)) < 0)

With your code you will ignore which was larger but only if they are same. As a result you do not sort at all.

Adding the <0 fixes the sorting.

Note: Your specific function uses correct comparison result:

if (arr[i]->day < arr[j]->day)

CodePudding user response：

This is my final version:

void merge(void *arr, int left, int mid, int right, int width, int (*comp)(const void*, const void*)) {
  void *temp = safeMalloc((right - left   1) * width);
  int i = left, j = mid   1, t = 0;   
  while (i <= mid && j <= right) {
    if (comp((char*)arr   i*width, (char*)arr   j*width) < 0) 
      memcpy((char*)temp   (t  )*width, (char*)arr   (i  )*width, width);
    else memcpy((char*)temp   (t  )*width, (char*)arr   (j  )*width, width);
  }
  memcpy((char*)temp   t*width, (char*)arr   i*width, (mid - i   1)*width);
  memcpy((char*)temp   t*width, (char*)arr   j*width, (right - j   1)*width);
  memcpy((char*)arr   left*width, temp, (right - left   1)*width);
  free(temp);
}

void mergeSort(void *arr, int left, int right, int width, int (*comp)(const void*, const void*)) { 
  if (left < right) {
    int mid = left   (right - left)/2;
    mergeSort(arr, left, mid, width, comp);
    mergeSort(arr, mid 1, right, width, comp);
    merge(arr, left, mid, right, width, comp);
  }
}