user2737948 user2737948 - 1 month ago 15
C Question

Using qsort with a define struct

I'm learning C and I'm solving this challenge, I'm not planning to submit it to the uva platform and the reason I'm coding this exercise is for leaning, maybe is not the best approach to the problem but I'm trying.

The input I print in my terminal is the following:

4
3
20 30 40 50 30 40
Res: 2
4
20 30 10 10 30 20 40 50
Res: 4
3
10 30 20 20 30 10
Res: 2
4
10 10 20 30 40 50 39 51
Res: 3


The answers from each input test are incorrect and I believe the reason is the qsort function. I'm confuse about how to use the qsort function using a structure, I'm calling my structure that is called array, followed by the size of my input, then using sizeof(int) but do I need to use int or sizeof my structure, lastly I'm calling my compare function. My code is:

#include <stdio.h>
#include <string.h>

struct Dolls{
int w;
int h;
}array[20005];

int cmp(struct Dolls a, struct Dolls b){
if(a.w==b.w){
return a.h < b.h;
}else{
return a.w > b.w;
}
}

int arr[20005];
int dp[20005];
int n;

int bSearch(int num, int k){
int low=1;
int high = k;
int mid;
while(low<= high){
mid = (low+high)/2;
if(num>=dp[mid]){
low=mid+1;
}else{
high=mid-1;
}
}
return low;
}

int res_dolls(){
int k=1;
int i,pos;
dp[i]=arr[1];
for(i=2;i<=n;i++){
if(arr[i]>=dp[k]){
dp[++k] = arr[i];
}else{
pos = bSearch(arr[i],k);
dp[pos] = arr[i];
}
}
return k;
}

int main(){
int t,j;
scanf("%d",&t);
while(t--){
memset(array,0,sizeof(array));
scanf("%d",&n);
for(j=1;j<=n;j++){
scanf("%d %d",&array[j].w, &array[j].h);
}
qsort(array,n,sizeof(int),cmp);
for(j=1;j<=n;j++){
arr[j] = array[j].h;
}
printf("%d\n",res_dolls());
}
return 0;
}

Answer

Your cmp function needs to be defined as int (*)(const void *, const void *) for it to work for qsort:

int cmp(const void *va, const void *vb){
  const struct Dolls *a = va;
  const struct Dolls *b = vb;

  if(a->w > b->w) {
      return 1;
  } else if(a->w < b->w){
      return -1;
  } else if(a->h > b->h) {
      return 1;
  } else if(a->h < b->h){
      return -1;
  } else {
    return 0;
  }
}

As for the call to qsort, you need to give it the size of an array element:

qsort(array,n,sizeof(struct Dolls),cmp);

EDIT:

Fixed the error with the parameter names. Also changed how the sort is performed to conform to how the comparison function must behave.