Sorting odd in descending and even in ascending order

Question

Given a array of random integers, sort the odd elements in descending order and even numbers in ascending order.

Example input: (1,4,5,2,3,6,7)
Output: (7,5,3,1,2,4,6)

Optimize for time complexity.

Answer 1

Once upon a time, this code was going to be added to the SO documentation project. Then there wasn't a documentation project, so now it can go here. This is unrepentant C code.

There are quite a number of variations on the theme of sorting odd and even numbers separately:

1. Odd ascending before even descending
2. Odd descending before even ascending
3. Even ascending before odd descending
4. Even descending before odd ascending
5. Odd ascending before even ascending
6. Odd descending before even descending
7. Even ascending before odd ascending
8. Even descending before odd descending

The code below shows options 1-4 — options 5-8 are easily created from these (don't do the final test for odd vs even; choose the correct ascending or descending comparison):

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

/* odd numbers in ascending order before even numbers in descending order */
static int oddasc_evendesc(const void *vp1, const void *vp2)
{
    int v1 = *(int *)vp1;
    int v2 = *(int *)vp2;
    if ((v1 & 1) != (v2 & 1))
    {
        /* One odd, one even */
        if (v1 & 1)
            return -1;      /* Odd is smaller */
        return +1;
    }
    /* Both odd or both even */
    if ((v1 & 1) == 1)
        return (v1 < v2) ? -1 : (v1 > v2) ? +1 : 0;     /* Ascending */
    return (v1 < v2) ? +1 : (v1 > v2) ? -1 : 0;         /* Descending */
}

/* even numbers descending before odd numbers ascending */
static int evendesc_oddasc(const void *vp1, const void *vp2)
{
    int v1 = *(int *)vp1;
    int v2 = *(int *)vp2;
    if ((v1 & 1) != (v2 & 1))
    {
        /* One odd, one even */
        if (v1 & 1)
            return +1;      /* Odd is larger */
        return -1;
    }
    /* Both odd or both even */
    if ((v1 & 1) == 1)
        return (v1 > v2) - (v1 < v2);     /* Ascending */
    return (v1 < v2) - (v1 > v2);         /* Descending */
}

/* odd numbers in descending order before even numbers in ascending order */
static int odddesc_evenasc(const void *vp1, const void *vp2)
{
    int v1 = *(int *)vp1;
    int v2 = *(int *)vp2;
    if ((v1 & 1) != (v2 & 1))
    {
        /* One odd, one even */
        if (v1 & 1)
            return -1;      /* Odd is smaller */
        return +1;
    }
    /* Both odd or both even */
    if ((v1 & 1) == 1)
        return (v1 < v2) ? +1 : (v1 > v2) ? -1 : 0;     /* Descending */
    return (v1 < v2) ? -1 : (v1 > v2) ? +1 : 0;         /* Ascending */
}

/* even numbers ascending before odd numbers descending */
static int evenasc_odddesc(const void *vp1, const void *vp2)
{
    int v1 = *(int *)vp1;
    int v2 = *(int *)vp2;
    if ((v1 & 1) != (v2 & 1))
    {
        /* One odd, one even */
        if (v1 & 1)
            return +1;      /* Odd is larger */
        return -1;
    }
    /* Both odd or both even */
    if ((v1 & 1) == 1)
        return (v1 < v2) - (v1 > v2);     /* Descending */
    return (v1 > v2) - (v1 < v2);         /* Ascending */
}

static void dump_array(const char *tag, int num, int *data)
{
    printf("%s:\n", tag);
    int i;
    const char *pad = "";
    for (i = 0; i < num; i++)
    {
        printf("%s%+3d", pad, data[i]);
        pad = " ";
        if (i % 10 == 9)
        {
            putchar('\n');
            pad = "";
        }
    }
    if (i % 10 != 0)
        putchar('\n');      /* End partial line */
    putchar('\n');          /* Blank line */
}

int main(void)
{
    int data1[] =
    {
        /* random -n 80 -- -99 99 | commalist -b '        ' -n 10 */
        +39, +36, +78, -92, +63, -21, -51, +49,   0, -77,
        -10, -49, -98, -17, +60, +83, +30, -97, -68, +86,
        +70, +84, -56,  +3, +33, -34, +14, -40, -72, -86,
        -95, -87, -73, -20, -72, -86,  -3, -71, -55, -80,
        -60,  -4, -26, -64, -31, -84, -79, +25, +41, +80,
        -54, -51, +24, -48, +13, +61, -99, +60,  -2, +16,
        -66, -30, +24, +88,  +5, -77, +13,  +3, +16, -69,
        -60, +26, +51, +16, -13, +71,  -9,  -2, +51, +72,
    };
    enum { NUM_DATA = sizeof(data1) / sizeof(data1[0]) };
    int data2[NUM_DATA];
    int data3[NUM_DATA];
    int data4[NUM_DATA];

    memmove(data2, data1, sizeof(data1));
    memmove(data3, data1, sizeof(data1));
    memmove(data4, data1, sizeof(data1));

    printf("Sort odd numbers ascending before even numbers descending\n");
    dump_array("Before", NUM_DATA, data1);
    qsort(data1, NUM_DATA, sizeof(data1[0]), oddasc_evendesc);
    dump_array("After", NUM_DATA, data1);

    printf("Sort even numbers descending before odd numbers ascending\n");
    dump_array("Before", NUM_DATA, data2);
    qsort(data2, NUM_DATA, sizeof(data2[0]), evendesc_oddasc);
    dump_array("After", NUM_DATA, data2);

    printf("Sort odd numbers descending before even numbers ascending\n");
    dump_array("Before", NUM_DATA, data3);
    qsort(data3, NUM_DATA, sizeof(data3[0]), odddesc_evenasc);
    dump_array("After", NUM_DATA, data3);

    printf("Sort even numbers ascending before odd numbers descending\n");
    dump_array("Before", NUM_DATA, data4);
    qsort(data4, NUM_DATA, sizeof(data4[0]), evenasc_odddesc);
    dump_array("After", NUM_DATA, data4);

    return 0;
}

Output:

Sort odd numbers ascending before even numbers descending
Before:
+39 +36 +78 -92 +63 -21 -51 +49  +0 -77
-10 -49 -98 -17 +60 +83 +30 -97 -68 +86
+70 +84 -56  +3 +33 -34 +14 -40 -72 -86
-95 -87 -73 -20 -72 -86  -3 -71 -55 -80
-60  -4 -26 -64 -31 -84 -79 +25 +41 +80
-54 -51 +24 -48 +13 +61 -99 +60  -2 +16
-66 -30 +24 +88  +5 -77 +13  +3 +16 -69
-60 +26 +51 +16 -13 +71  -9  -2 +51 +72

After:
-99 -97 -95 -87 -79 -77 -77 -73 -71 -69
-55 -51 -51 -49 -31 -21 -17 -13  -9  -3
 +3  +3  +5 +13 +13 +25 +33 +39 +41 +49
+51 +51 +61 +63 +71 +83 +88 +86 +84 +80
+78 +72 +70 +60 +60 +36 +30 +26 +24 +24
+16 +16 +16 +14  +0  -2  -2  -4 -10 -20
-26 -30 -34 -40 -48 -54 -56 -60 -60 -64
-66 -68 -72 -72 -80 -84 -86 -86 -92 -98

Sort even numbers descending before odd numbers ascending
Before:
+39 +36 +78 -92 +63 -21 -51 +49  +0 -77
-10 -49 -98 -17 +60 +83 +30 -97 -68 +86
+70 +84 -56  +3 +33 -34 +14 -40 -72 -86
-95 -87 -73 -20 -72 -86  -3 -71 -55 -80
-60  -4 -26 -64 -31 -84 -79 +25 +41 +80
-54 -51 +24 -48 +13 +61 -99 +60  -2 +16
-66 -30 +24 +88  +5 -77 +13  +3 +16 -69
-60 +26 +51 +16 -13 +71  -9  -2 +51 +72

After:
+88 +86 +84 +80 +78 +72 +70 +60 +60 +36
+30 +26 +24 +24 +16 +16 +16 +14  +0  -2
 -2  -4 -10 -20 -26 -30 -34 -40 -48 -54
-56 -60 -60 -64 -66 -68 -72 -72 -80 -84
-86 -86 -92 -98 -99 -97 -95 -87 -79 -77
-77 -73 -71 -69 -55 -51 -51 -49 -31 -21
-17 -13  -9  -3  +3  +3  +5 +13 +13 +25
+33 +39 +41 +49 +51 +51 +61 +63 +71 +83

Sort odd numbers descending before even numbers ascending
Before:
+39 +36 +78 -92 +63 -21 -51 +49  +0 -77
-10 -49 -98 -17 +60 +83 +30 -97 -68 +86
+70 +84 -56  +3 +33 -34 +14 -40 -72 -86
-95 -87 -73 -20 -72 -86  -3 -71 -55 -80
-60  -4 -26 -64 -31 -84 -79 +25 +41 +80
-54 -51 +24 -48 +13 +61 -99 +60  -2 +16
-66 -30 +24 +88  +5 -77 +13  +3 +16 -69
-60 +26 +51 +16 -13 +71  -9  -2 +51 +72

After:
+83 +71 +63 +61 +51 +51 +49 +41 +39 +33
+25 +13 +13  +5  +3  +3  -3  -9 -13 -17
-21 -31 -49 -51 -51 -55 -69 -71 -73 -77
-77 -79 -87 -95 -97 -99 -98 -92 -86 -86
-84 -80 -72 -72 -68 -66 -64 -60 -60 -56
-54 -48 -40 -34 -30 -26 -20 -10  -4  -2
 -2  +0 +14 +16 +16 +16 +24 +24 +26 +30
+36 +60 +60 +70 +72 +78 +80 +84 +86 +88

Sort even numbers ascending before odd numbers descending
Before:
+39 +36 +78 -92 +63 -21 -51 +49  +0 -77
-10 -49 -98 -17 +60 +83 +30 -97 -68 +86
+70 +84 -56  +3 +33 -34 +14 -40 -72 -86
-95 -87 -73 -20 -72 -86  -3 -71 -55 -80
-60  -4 -26 -64 -31 -84 -79 +25 +41 +80
-54 -51 +24 -48 +13 +61 -99 +60  -2 +16
-66 -30 +24 +88  +5 -77 +13  +3 +16 -69
-60 +26 +51 +16 -13 +71  -9  -2 +51 +72

After:
-98 -92 -86 -86 -84 -80 -72 -72 -68 -66
-64 -60 -60 -56 -54 -48 -40 -34 -30 -26
-20 -10  -4  -2  -2  +0 +14 +16 +16 +16
+24 +24 +26 +30 +36 +60 +60 +70 +72 +78
+80 +84 +86 +88 +83 +71 +63 +61 +51 +51
+49 +41 +39 +33 +25 +13 +13  +5  +3  +3
 -3  -9 -13 -17 -21 -31 -49 -51 -51 -55
-69 -71 -73 -77 -77 -79 -87 -95 -97 -99

This code is available on GitHub in my SOQ (Stack Overflow Questions) repository as file oddascevendesc.c (now a misnomer) in the doc/qsort sub-directory.

Answer 2

Just to give an alternative solution:

#include <algorithm>
#include <functional>

bool is_odd(int x)
{
    return x & 1;
}

int* rushakoff(int* begin, int* end)
{
    int* middle = std::partition(begin, end, is_odd);
    std::sort(begin, middle, std::greater<int>());
    std::sort(middle, end, std::less<int>());
    return middle;
}

int main()
{
    int array[] = {1,4,5,2,3,6,7};
    rushakoff(array, array + 7);
}

Maybe not so optimal, but quite readable. That's important, too ;-)

Answer 3

With integers as the sort target, you can get this to an O(n) sort using a count sort and a little care.

Answer 4

// Sort with a custom comparison function
// returns -1 if a before b, 0 if a==b, 1 if a after b
int _cmp(a,b) {
  if (a % 2) == 0 {
    if (b % 2) == 0 {
      return (a>b) ? 1 : (a==b) 0 : -1; # Even(a) vs Even(b)
    } else {
      return 1; # Even(a) vs Odd(b) all evens are after all odds
    }
  } else {
    if (b % 2) == 0 {
      return -1; # Odd(a) vs Even(b) all odds are before all evens
    } else {
      return (b>a) ? 1 : (a==b) 0 : -1; # Odd(a) vs Odd(b) has reverse order
    }
  }
}

Answer 5

Here's a c# one-liner:

int[] x = { 1,4,5,2,3,6,7 };
Array.Sort(x, (a, b) => a % 2 == 0 ? b % 2 == 0 ? a.CompareTo(b) : 1 : b % 2 == 0 ? -1 : -1 * a.CompareTo(b));

Don't turn it in to your teacher. Your teacher wants to see you implement the sorting algorithm yourself, so he knows you can do it and knows you understand what's involved.

In practice, you'll (almost) never do that on the job. Your platform will already have highly-optimized sort methods, and you want to take advantage of those, be it C#'s Array.Sort() or .OrderBy() or a C++ stl algorithm. This code was to show you how you might solve this problem in the real world, albeit if I wanted this to pass a code review I might not squeeze it all on one line.

Answer 6

Which language is it, C or C++ (I see both tags)

In C++, you can use std::sort() with appropriate ordering function. In C, qsort() works similarly:

#include <iostream>
#include <algorithm>
bool Order(int a, int b)
{
        if (a%2 != b%2) return a%2;
        else return a%2 ? b<a : a<b;
}
int main()
{
        int a[] = {1,4,5,2,3,6,7};
        size_t N = sizeof(a) / sizeof(a[0]);

        std::sort(a, a+N, Order);

        for(size_t i=0; i<N; ++i)
                std::cout << a[i] << ' ';
        std::cout << std::endl;

}