Monday, May 10, 2010

Array manuplation

Given a array of random integers, sort the odd elements in descending order and even numbers in ascending order. Optimize for time complexity.
e.g. for i/p (1,4,5,2,3,6,7) O/p = (7,5,3,1,2,4,6)

Answer :
We can solve this by doing a simple bubble sort, with the below logic
  1. if first number and second number are odd >> compare and exchange >> push lower odd to first
  2. if first is odd and second is even >> no exchange >> we want odd in the first
  3. if first is even and second is also even >> compare and exhange >> push higher even number to last
  4. if first is even and second is odd >> always exchange >> since we want odd numbers first
Here is the complete solution in C
#include <stdio.h>

int a[] = {1,4,5,2,3,6,7};
int len = 7;

void main(void)
{
    int i,j, temp;
    for(i = 0; i < len-1; i++)
    {
        for(j = 0; j< len-1; j++)
        {
         if( a[j] %2  != 0) 
         {     // first odd number
             if(a[j+1] % 2 != 0) 
             {   
                 // second odd number
                 if(a[j] < a[j+1]) 
                 {
                     temp = a[j+1];
                     a[j+1] = a[j];
                     a[j] = temp;
                 }
             }
             else 
             {     // second even number 
                 //do nothing
             }
         }
         else 
         {     // first even number
             if(a[j+1] % 2 != 0) 
             {   
                 // second odd number
                 // always interchange
                 temp = a[j+1];
                 a[j+1] = a[j];
                 a[j] = temp;
             }
             else
             {
                 // second even number
                 if(a[j] > a[j+1])
                 {
                     temp = a[j+1];
                     a[j+1] = a[j];
                     a[j] = temp;
                 }
             }
         }
        }
    }
    for(i=0; i<len; i++)
    printf("%d ", a[i]);
}

No comments:

Post a Comment