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.

So what are you asking? How to optimize it? People usually appreciate some kind of an attempt before they're willing to help you. (i.e. post some code and people will be happy to help you optimize it) — Adam, May 23 '10 at 02:44
A "Microsoft interview question" http://geeksforgeeks.org/forum/topic/microsoft-interview-question-for-software-engineerdeveloper-about-arrays — WhirlWind, May 23 '10 at 02:46
What have you tried? Why don't you like your first solution? What are you considering as an optimization, and what's your specific question about that consideration? — Kate Gregory, May 23 '10 at 02:54
It's O(n) Do a radix sort and you get the even/odd splitting for free. — Nils Pipenbrinck, May 23 '10 at 10:48

score 2 · Accepted Answer · answered May 23 '10 at 02:51

2

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;

}

answered May 23 '10 at 02:51

Cubbi

46,567
13
103
169

I'm always suspicious when I see signed integers combined with the modulus operator. Does your solution work with negative numbers? – fredoverflow May 23 '10 at 10:29
1

On the compilers I could test it does, but you're right, of course, it's implementation defined in C++ per `5.6/4 [expr.mul]` with a footnote that rounding to zero is preferred.. – Cubbi May 23 '10 at 19:14
Wonder if a similar approach existing for Python implementation? – Daniel Hao Oct 02 '22 at 12:21

score 1 · Answer 2 · answered May 23 '10 at 03:10

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.

score 1 · Answer 3 · answered May 23 '10 at 05:16

1

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

answered May 23 '10 at 05:16

Michael Dorgan

12,453
3
31
61

A count sort?!? Yes, O(n)... if you don't mind an implied constant of 2^32 or so. – Charles May 23 '10 at 06:00
Ok, let me change that to bytes instead of ints - I read his range and assumed bytes. My bad. BTW, 4n if you do it in 4 passes... – Michael Dorgan May 23 '10 at 19:03
Question: I was looking at a version of the OP (yes, an interview question relayed to me secondhand), in which the required data structure is a linked list. Does a count sort seem applicable in that case? I'm also reading this related answer (https://stackoverflow.com/questions/14368392/radix-sort-vs-counting-sort-vs-bucket-sort-whats-the-difference). – learning2learn Jun 11 '21 at 17:52
As long as you are placing the values into array buckets as they are read in via the linked list, it should still be possible. "Read all values from linked list, do sorts, rebuild linked list with new values." Not efficient as this is not what a linked list is meant to do, but possible. – Michael Dorgan Jun 11 '21 at 18:08

fredoverflow · Answer 4 · 2010-05-23T19:38:01.927

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 ;-)

Jonathan Leffler · Answer 5 · 2018-03-16T06:15:14.890

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:

Odd ascending before even descending
Odd descending before even ascending
Even ascending before odd descending
Even descending before odd ascending
Odd ascending before even ascending
Odd descending before even descending
Even ascending before odd ascending
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.

score 0 · Answer 6 · edited May 23 '10 at 03:16

// 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
    }
  }
}

Sorting odd in descending and even in ascending order

6 Answers6

Linked

Related