Given an array consisting of even and odd numbers. Sort the array with even first and then odds. The order of numbers can't be changed

Question

If the input array is - 1,4,3,8,6,5,7 the output should be - 4 8 6 1 3 5 7

I have one solution with insertion sort kind of thing.

void sortarrayinorder(int arr[],int size)
{
     int i,j,tem,k;
     for(i=1;i<size;i++)
     {
       for(j=0;j<i;j++)
       {
       if((arr[j]%2)!=0 && (arr[i]%2)==0)
       {
         tem=arr[j];
         arr[j]=arr[i];
         for(k =i;k>j;k--)
           arr[k]=arr[k-1];

           arr[k+1]=tem;
           }
         }
     }     
}

Can this problem be solved in a better way? The complexity of my solution is o(n2). Please provide a solution with lesser time complexity. No extra space is allowed.

Answer 1

You can do this in O(n) with a two-pass approach, so long as you're allowed to allocate a separate output buffer. On the first pass, detect and copy all even numbers. On the second pass, detect and copy all odd numbers.

Answer 2

class Program 
    {
        static void Main()
        {
          int[] numbers = { 1, 2, 3, 4, 5,6,7,8,9,10,11,12,13,14 };

         //using delegate
          Array.Sort (numbers, (x, y) => x % 2 == y % 2 ? 0 : x % 2 == 1 ? -1 : 1);

          Array.ForEach(numbers, x => Console.Write(x));
          Console.WriteLine("");

         //using custom comparer
          CustomComparer comparer = new CustomComparer();
          Array.Sort(numbers, comparer);
          Array.ForEach(numbers, x => Console.Write(x));
          Console.WriteLine("");

          //using lambda
          int[] items = numbers.OrderBy(x => x % 2 == 0).ThenBy(x => x % 2).ToArray();

          Console.WriteLine("");
          Array.ForEach(items, x => Console.Write(x));
        }

        public int Compare(int x, int y)
        {
            return x % 2 == y % 2 ? 0 : x % 2 == 1 ? -1 : 1;
        }
    }

    public class CustomComparer : IComparer<int>
    {
        int IComparer<int>.Compare(int x, int y)
        {
            return x % 2 == y % 2 ? 0 : x % 2 == 1 ? -1 : 1;
        }
    }

Answer 3

This can be done in O(n log n) time if not extra space is to be used. The strategy would be to sort the array first in O(n log n) time and then partition the array into even and odd groups by two successive linear scans, each taking O(n).

The total complexity would be O(n log n) + 2 * O(n) = O(n log n).

If we have more information on the distribution of the numbers in the array, it could be possible to improve on the O(n log n) time required to sort the array there by reducing the overall complexity.

The code for this can be seen at http://www.codeblocks.info/2010/10/sorting-array-with-all-even-numbers.html

Answer 4

You can certainly do it in O(n) time using O(n) extra memory. You need a stable sort, and in effect you need to do the first step of an MSD radix sort (normally the sign bit is the "most significant" bit, whereas you're interested in even/oddness, but it's same basic deal). A radix sort can be made stable by using a separate buffer to contain either the 1 or 0 values, then combine them.

C++ has the algorithm stable_partition, which does exactly what you want. It has O(n) complexity if it uses a buffer and O(n log n) if it doesn't. I don't know the technique for the latter off-hand. I realise the question is about C, but you could copy and modify the code from any C++ standard library implementation, or maybe use a C++ compiler to build yourself an "extern C" function that calls stable_partition.