Interview question on sorting

[arsenal_fan]

There is an array of odd and even numbers. Now, sort them in such a way that the top portion of the array contains odd numbers, bottom portion contains even numbers. The odd numbers are to be sorted in descending order and the even numbers in ascending order.

If the array is {1,4,5,2,3,6,7} the result would be {7,5,3,1,2,4,6} but I am getting {2,4,6,7,5,3,1}. Any pointers as to where I am going wrong?

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int lessthan(const void *a, const void *b)
{
  if(*(int *)a%2==1)
  {
     if(*(int *)b%2==0)
     {
        return 1;
     }
     else if(*(int *)b%2==1)   
     {
        if(*(int *)a < *(int *)b)
        {
           return 1;
        }
        else if(*(int *)a > *(int *)b)
        {
           return -1;
        }
     }           
  }
  else if(*(int *)a%2==0)
  {
     if(*(int *)b%2==1)
     {
        return -1;
     }
     else if(*(int *)b%2==0)
     {
        if(*(int *)a < *(int *)b)
        {
           return -1;
        }
        else if(*(int *)a > *(int *)b)
        {
           return 1;
        }   
     }
  }
}
 
int main(void)
{
  int n = 0;
  int values[] = {4,1,5,2,3,6,7};
  int len = 7;
  qsort(values, len, sizeof(int), lessthan);
  for(n=0;n<len;n++)
  {
    printf("%d ", values[n]);
  }
  return 0;
}

output:
2 4 6 7 5 3 1

[griswolf]

I don't have a compiler set up on this laptop, so I'm working by eye. Thus, I may have the comparisons reversed on lines 9 and 15 (?) ... and for that matter maybe one lines 7 and 13 (?). But here's approximately what I would do:

int lessthan(const void *a, const void *b)
{
  int lhs = *(int*)a;
  int rhs = *(int*)b;
  if(1 == lhs%2) { /* left odd */
    if( 0 == rhs%2) { /* right even */
     ret = 1; /* odd > even */
    } else { /* both odd */
       ret = rhs - lhs; /* want descending order */
    }
  } else { /* left even */
    if (1 == rhs %s) { /* right odd */
      ret = -1; /* even < odd */
    } else { /* both even */
      ret = lhs - rhs; /* want ascending order */
  }
  return ret;
}

This differs from your code in just two ways:

1. I did the conversion at the top, to avoid looking at all those *(int*) casts
2. I returned a calculated value when both arguments have the same evenness (the comparison function need not return 1,0,-1, it can be anything positive, 0, anything negative)

... and I also put in some comments to make things clearer while I thought about it.

Oh yeah, one other thing: As a matter of self-discipline, I try (not obsessively) to return only once from a function: Usually makes debugging easier; usually makes understanding easier, sometimes helps the compiler, and my first few programming teachers insisted... ;)

[arsenal_fan]

Hey thanks but I am still not getting the correct result. I am getting 6 4 2 1 3 5 7 as the output instead of 7 5 3 1 2 4 6. Also, how is lhs < rhs and rhs < lhs interpreted? I mean we want to return either 1 or -1 depending on whether lhs is greater or lesser than rhs but lhs < rhs will return 1 or 0 if I am understanding correctly.

Can you look at this link http://ideone.com/stWZV.

Ideone is an online compiler and editor. My code is at that URL. Thanks for suggestions on how to code well especially w.r.t. the return statement.

[arsenal_fan]

Also I had another question related to return statements.

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
int missingNumber(int* arr1, int* arr2, int size)          // int arr1[] is pass by value
{
   int *temp = (int *)malloc(size *sizeof(int));
   int i=0, j=0;
   assert(temp !=NULL);
   while(i<size)
   {
     temp[arr2[i]]=1;
     i++;
   }
   while(j<size)
   {
     if(!temp[arr1[j]])
     {
        return arr1[j];
     }
     j++;
   }
}
 
int main(void)
{
  int arr1[5]={1,2,3,4,5};
  int arr2[5]={2,3,0,4,5};
  int ret = missingNumber(arr1,arr2,5);
  printf("The number which is not present in the second array is %d\n", ret);
  return 0;
}

In this code I am trying to find the number from the first array which is not present in the second array.

Now,
From the code I get a warning that control reaches the end of a non-void function. What should I put in as a return statement just before the end of the function. If I return -1 it could be a problem if -1 was in the array. How could I write this code better?

One more question is where should I free the temp array? Will I have to include 2 free statements: one just before it returns the missing number and when just before the end of the function when there are no missing numbers?

Thanks.

[Adak]

You should return the index to the number, not the number. Then use the index, in main(), to print out the number.

Free the array whenever you no longer need it.

And you don't need to cast the return from malloc, in C.

[griswolf]

Hey thanks but I am still not getting the correct result. I am getting 6 4 2 1 3 5 7 as the output instead of 7 5 3 1 2 4 6. Also, how is lhs < rhs and rhs < lhs interpreted? I mean we want to return either 1 or -1 depending on whether lhs is greater or lesser than rhs but lhs < rhs will return 1 or 0 if I am understanding correctly.

Can you look at this link http://ideone.com/stWZV.

Ideone is an online compiler and editor. My code is at that URL. Thanks for suggestions on how to code well especially w.r.t. the return statement.

That's an interesting service. Hmm.

I did intend to return lhs - rhs or rhs - lhs This is an int which is what is required by qsort and the other sorts. Passing back the result of lhs < rhs or the reverse forces the compiler to cast the boolean to an int. Admittedly, that cast is cheap and almost surely right... unless your compiler uses 0xFFFF for "true" in which case the cast to an int would be a very negative number, not 1. Aside from that quibble, the result is the same. I have no idea whether subtraction or comparison is faster on any given machine.