simple question regarding sorting

Question

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

e.g. for input (1,4,5,2,3,6,7)

Output = (7,5,3,1,2,4,6)

Optimize for time complexity.

Answer 1

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;

}

Answer 2

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

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 4

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

Answer 5

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