Split and sort array

Here was another interesting interview question on arrays

How do you sort the array so that all the odd elements are before all the even elements.

And both these subarrays must be sorted.

We can first split the array so that all odd elements are in first subarray and all even elements come afterwards. Next we can use some sorting method to sort these two sub-arrays separately.

Next comes the question. How do we split the array?

• For ith element in array, if it is even 
• remove the element from ith position
• move it to end of array
• Repeat this process for all elements from last to 0th

Here is the code to split array into odd and even.

int splitOddEven(int *arr,int n)
{
    int i;
    int evencount=0;
    for(i=n-1;i>=0;i--)
    {
       if(arr[i]%2==0)
           {
           move_extreme_right(arr,n,i);
    evencount++;
           }
    }
    return evencount;
}

The function test whether arr[i] is even. If yes, to moves the element to extreme right and packs the hole. It also maintains the total number of even values in the array.

Here is the function to move ith element to end of array.

void move_extreme_right(int *arr,int n,int position)
{
   int i;
   int temp = arr[position];
   for(i=position+1;i<n;i++)
      arr[i-1]=arr[i];
   arr[n-1]=temp;
}

Now we get all odd elements in first part and even elements in second half. We will sort them using insertion sort. But sorting of second part needs an offset because it starts from n-evencount.

evencount = splitOddEven(arr,n);    
insertion_sort(arr,n-evencount,0);
insertion_sort(arr,evencount,n-evencount);//write these in a separate function 

void insertion_sort(int *arr,int sz,int offset)
{
   int i,j,k;
   for(i = 1;i<sz;i++)
   {
       int temp = arr[i+offset];
       int j = i-1;
       while(j>=0  && arr[j+offset]>temp)
       {          
          arr[j+1+offset] = arr[j+offset];          
          j--;
       }
       arr[j+1+offset] = temp;
   }           
}

Here is the complete program.

#include<stdio.h>
void insertion_sort(int *arr,int sz,int offset)
{
   int i,j,k;
   for(i = 1;i<sz;i++)
   {
       int temp = arr[i+offset];
       int j = i-1;
       while(j>=0  && arr[j+offset]>temp)
       {          
          arr[j+1+offset] = arr[j+offset];          
          j--;
       }
       arr[j+1+offset] = temp;
   }           
}
void move_extreme_right(int *arr,int n,int position)
{
   int i;
   int temp = arr[position];
   for(i=position+1;i<n;i++)
      arr[i-1]=arr[i];
   arr[n-1]=temp;
}
int splitOddEven(int *arr,int n)
{
    int i;
    int evencount=0;
    for(i=n-1;i>=0;i--)
    {
       if(arr[i]%2==0)
           {
           move_extreme_right(arr,n,i);
    evencount++;
           }
    }
    return evencount;
}
       
void read_array(int *arr,int sz)
{
     int i;
     for(i  =0;i<sz;i++)
     {
       printf("arr[%d]=",i);
       scanf("%d",&arr[i]);
     }
}
void print_array(int *arr,int sz)
{
     int i;
     for(i  =0;i<sz;i++)
     {
       printf("arr[%d]=",i);
       printf("%d   ",arr[i]);
     }
     printf("\n");
}
int main()
{
    int arr[40];
    int evencount;
    int n,midpoint;
    printf("Enter size of array:");
    scanf("%d",&n);
    read_array(arr,n);
    evencount = splitOddEven(arr,n);    
    insertion_sort(arr,n-evencount,0);
    insertion_sort(arr,evencount,n-evencount);     
    print_array(arr,n);
}

You can download the program from here