Skip to main content

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

Comments

Popular posts from this blog

In order traversal of nodes in the range x to y

Question : Write a function for in-order traversal of nodes in the range x to y from a binary search tree. This is quite a simple function. As a first solution we can just traverse our binary search tree in inorder and display only the nodes which are in the range x to y. But if the current node has a value less than x, do we have to traverse its left subtree? No. Because all the nodes in left subtree will be smaller than x. Similarly if the current node has a key value more than y, we need not visit its right subtree. Now we are ready to write our algorithm.     if nd is NOT NULL  if nd->val >=x then visit all the nodes of left subtree of nd recursively display nd->val if nd->val <y then visit all the nodes of right subtree of nd recursively  That's all. We have our function ready. void in_order_middle (NODEPTR nd, int x, int y) { if (nd) { if (nd -> val >= x) in_order_middle(nd...

Josephus problem

Question: Write a function to delete every k th node from circular linked list until only one node is left. This has a story associated with it. Flavius Josephus was Jewish Historian from 1st century. He and 40 other soldiers were trapped in a cave by Romans. They decided to kill themselves rather than surrendering to Romans. Their method was like this. All the soldiers will stand in a circle and every k th soldier will be shot dead. Josephus said to have calculated the starting point so that he would remain alive. So we have similar problem at hand. We delete every kth node in a circular list. Eventually only one node will be left. e.g. Let us say this is our list And we are deleting every third node.  We will delete 30. Then we delete 60. Next we delete 10. Next it will be 50. Next to be deleted is 20. Next 80. This continues. Implementation   We can count k-1 nodes and delete next node. This can be repeated in  a loop. What must be the termina...

Lowest common ancestor of binary search tree

Question : Write a function to print the lowest common ancestor of two nodes in a binary search tree.  Lowest common ancestor of two nodes x and y in a binary tree is the lowest node that has both x and y as descendants. Here lowest common ancestor of 1 and 7 is 3. LCA of 13 and 7 is root - 8. And LCA of 6 and 7 is 6 itself. The program to find gets complicated for an ordinary binary tree. But for a binary search tree, it is quite simple. As we see from the diagram above, the paths to 1 and 4 are common till the node 3. And at 3 they branch in different directions. So 3 is our LCA. That is lowest common ancestor is the node where the paths to x and y from root deviate. As long as they branch in same direction, we continue to traverse. When they branch in different directions, that is the lowest common ancestor. So let us write a simple algorithm, set temp=root if temp->val >x and temp->val>y temp = temp->left else if temp->val<x and ...