Rearrange even and odd numbers

Question

If you have an array with random odd and even numbers, what is the most efficient way to put all even numbers on one side and all odd numbers on the other side of the array?

Answer 1

The solution is in-place quick sort type..

#include <iostream>
using namespace std;

int main()
{
    int a[] = {1,2,3,4,5,6,7,8,9,10};
    int n = 10;
    int i=0, j = n-1, tmp;
    while(i <= j)
    {
        while(a[i]%2 == 0)
        {
            i++;
            if(i == j) break;
        }
        if(i == j) break;
        while(a[j]%2 != 0)
        {
            j--;
            if(i == j) break;
        }
        if(i == j) break;
        tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
        i++;
        j--;
    }
    for(int i=0; i<n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}

Order : O(N)

Answer 2

Complexity o(n^2)

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