Sort an array in a specific way

Question

Write an efficient function in C language that receives an array A of natural numbers and their amoun as n. The function must rearrange the array A like this:

In the left part all the even numbers will be sorted in ascending order and in the right part all the odd numbers will be descending down.

The function must run on the order of n·log(n).

It is forbidden to use an auxiliary array but we can use functions like :

quicksort , binarysearch , partition , merge_sort..

For example:

A={6, 8, 8, 10, 20, 5,1}: the function A={ 1, 20, 5, 6, 8, 8, 10 } will rearrange the array

I tried to order the whole array using quick sort and then running all over the elements, putting the even numbers first and then counting how many even numbers there is. After that, using the evencounter starting one step after it tried to put the odd numbers and tried to sort them in descending order.

The complexity should be n·log(n) so I don't know whether running all over the elements is the right thing to do.

Answer 1

I think it is enough to use standard C function qsort.

Here is a demonstration program.

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

int cmp_numbers( const void *a, const void *b )
{
    unsigned int x = *( const unsigned int * )a;
    unsigned int y = *( const unsigned int * )b;

    int result = ( int )( x % 2 ) - ( int )( y % 2 );

    if (result == 0)
    {
        enum { Even = 0, Odd = 1 };

        switch (x % 2)
        {
        case Even:
            return ( y < x ) - ( x < y );
        case Odd:
            return ( x < y ) - ( y < x );
        }
    }
    else
    {
        return result;
    }
}

int main( void )
{
    unsigned int a[] = { 8, 1, 6, 3,  4, 5, 2, 7, 0,  9 };
    const size_t N = sizeof( a ) / sizeof( *a );

    for (size_t i = 0; i < N; i++)
    {
        printf( "%u ", a[i] );
    }
    putchar( '\n' );

    qsort( a, N, sizeof( *a ), cmp_numbers );

    for (size_t i = 0; i < N; i++)
    {
        printf( "%u ", a[i] );
    }
    putchar( '\n' );
}

The program output is

8 1 6 3 4 5 2 7 0 9
0 2 4 6 8 9 7 5 3 1

Otherwise you could for example write a function that split an array in two partitions and sort the partitions separately.

Pay attention to this lone

int result = ( int )( x % 2 ) - ( int )( y % 2 );

without casting to int the result of expression will be unsigned int (the type of x and y) and never can be negative.

If you want to have an array of signed integers then apart from other changes from unsigned int to int in this statement use standard C function abs

int result = abs( x % 2 ) - abs( y % 2 );