Partitioning and sorting even and odd numbers within an array

Question

I solved a problem where it was told to sort an array of numbers such that the even numbers are kept first and the odd numbers should follow. Moreover, the even numbers must be sorted in ascending order among them and the odd numbers as well. Only arrays can be used. My code is as follows , which works fine but it seems bit long to me. I wanted to know if there is anything I can do to shorten it and make it more readable.

#include <stdio.h>

int main(void)
{
    int n,i,k,p,j,temp;

    scanf("%d",&n);

    int arr[n],arr_even[n],arr_odd[n];

    k=0,p=0;
    for(i=0;i<n;i++){
        scanf("%d",&arr[i]);
        if(arr[i]%2==0) arr_even[k++]=arr[i];
        else arr_odd[p++]=arr[i];
    }

    for(i=0;i<k;i++){
        for(j=0;j<=i;j++){
            if(arr_even[j]>arr_even[i]){
                temp=arr_even[i],arr_even[i]=arr_even[j],arr_even[j]=temp;
            }
        }
    }

    for(i=0;i<p;i++){
        for(j=0;j<=i;j++){
            if(arr_odd[j]>arr_odd[i]){
                temp=arr_odd[i],arr_odd[i]=arr_odd[j],arr_odd[j]=temp;
            }
        }
    }

    p=0;
    for(i=0;i<n;i++)
    {
        if(k) arr[i]=arr_even[i],k--;
        else arr[i]=arr_odd[p++];
        }

    for(i=0;i<n;i++)
    {
        printf("%d ",arr[i]);
    }

    return 0;
}

Input:

10    
0 5 1 2 3 4 6 12 10 9

Output:

0 2 4 6 10 12 1 3 5 9

Answer 1

Your code is quite complicated. The C standard library provides all the ingredients you need to sort an array. You just need to define a comparison function. All the rest is done by the qsort function from stdlib.h.

The comparison function should look like:

static int even_first(const void *a, const void *b) {
    int left = *(const int *)a;
    int right = *(const int *)b;

    int res = (left % 2 != 0) - (right % 2 != 0);
    if (res == 0)
        res = (left > right) - (left < right);
    return res;
}

The expressions of the form cond1 - cond2 may look strange at first, but they are commonly used in C code in comparison functions like this one.

The benefit over a naïve left - right is that no integer overflow can happen. Integer overflow is a common source of undefined behavior.

To make the code more readable, it's also possible to extract the basic integer comparison into a separate function:

static int compare(int a, int b) {
    return a < b ? -1 : a > b ? +1 : 0;
    // alternatively: return (a > b) - (a < b);
    // alternatively: return a < b ? -1 : a > b;
}

Then, the comparison function becomes:

static int even_first(const void *a, const void *b) {
    int left = *(const int *)a;
    int right = *(const int *)b;

    int res = compare(left % 2 != 0, right % 2 != 0);
    if (res == 0)
        res = compare(left, right);
    return res;
}

This form is much less of a brain twister than the above variant.

Answer 2

Firstly, we should separate the sorting from the reading of inputs and writing of outputs. We can create a function sort_evens_first() - that's the foundation of writing re-usable code. An advantage (even in this small program) is that a separable function can more easily be tested - no need for an external script to run many instances of the program with different inputs, making tests run much faster; also it makes it easier to distinguish bugs in the I/O from bugs in the algorithm

Secondly, the Standard Library provides us with qsort() to save us having to re-implement sort every time (and it's usually more efficient than the bubble sort implemented here). We need to give it a comparator function as follows:

• if one element is even and the other is odd, the even number sorts before the odd one,
• else, the numerically smaller one is lower.

That looks like:

int compare_evens_first(const void *va, const void *vb)
{
    const int *a = va;
    const int *b = vb;

    if (*a % 2 != *b % 2)
        return (*a % 2) - (*b % 2);

    // else both odd, or both even
    // return *a - *b might overflow, so avoid that
    return (*a > *b) - (*a < *b);
}

Then we can simply use it:

#include <stdlib.h>

void sort_evens_first(int *array, size_t count)
{
    qsort(array, count, sizeof *array, compare_evens_first);
}

N.B. I've not had time to test this code; bugs may be lurking.

---

Additional problems with the supporting code

When reading input with scanf() and family, it is essential to confirm the return value before using any of the results.

It's less important to check the result of printf() as failure there is less likely to lead to bad outcomes, but it's still worth considering so that we can return EXIT_FAILURE if the output wasn't successfully written (it might not be obvious to the user if directed to a file or pipeline, for example).