CareerCup

Solution 1

3 way partitioning

tinyurl.com/bg99tr8

Solution 2

Dutch Flag Sort

en.wikipedia.org/wiki/Dutch_national_flag_problem

It can be solved using three way partitioning:

#include <stdio.h>
#include <conio.h>

void makeArray(int arr[],int low,int high,int n)
{
	int startIndex=0,endIndex=n-1,i,temp;
	for(i=0;i<=endIndex;)
	{
		if(arr[i]<low)
		{
			temp=arr[i];
			arr[i]=arr[startIndex];
			arr[startIndex]=temp;
			startIndex++;
			i++;
		}
		else if(arr[i]>high)
		{
			temp=arr[i];
			arr[i]=arr[endIndex];
			arr[endIndex]=temp;
			endIndex--;
		}
		else
		{
			i++;
		}
	}
}
int main()
{
	int arr[]={1,14,5,20,4,2,54,20,87,98,3,1,32};
	int n=sizeof(arr)/sizeof(arr[0]);
	makeArray(arr,20,20,n);
	int i;
	for(i=0;i<n;i++)
		printf(" %d ",arr[i]);
}

the word sort and any order doesn't go together...i am hoping you meant 'arrange' rather than sort and that the element on the left and right of k are not sorted. what the interviewer is asking is exactly what quick sort does after selecting the pivot. in your case the pivot will be k. if we have an external array and couple of pointers then this is what i'll do..in the first pass through the array count number of elements less than k(say x), number of them equal to k (say y) then number of element greater than k will be n - x - y. Now fill the external array from position x to y-1 with k. on the second pass of the array if you find an element less than k fill it in a position less than x and if you find something greater than k fill it at a position greater than = x+y-1

description of quick sort has much more efficient solution.
split pivot with right-most element. remember left as a store position
go flom left to right-1. if current is smaler from pivot swap it with store position.
adjust store position by 1.
Last step swap store and pivot. Viola ! o(n)

This question is a step in a quicksort algorithm. 3-way partitioning.
So, could be done in-place.

/**
	 * 
	 * time: O(N)
	 * space: O(1)
	 * 
	 */
	public static void threeWayPartition( int[] arr, int pivot ){
		
		if( arr == null ){
			throw new IllegalArgumentException("Array is NULL");
		}
		
		int equalStartIndex = 0;
		int greaterStartIndex = 0;		
		
		for( int i =0; i < arr.length; i++ ){
			// equal case
			if( arr[i] == pivot ){
				swap(arr, greaterStartIndex, i);
				greaterStartIndex++;
			}
			// less case
			else if( arr[i] < pivot ){
				swap(arr, greaterStartIndex, i);
				swap(arr, equalStartIndex, greaterStartIndex);
				greaterStartIndex++;
				equalStartIndex++;
			}
		}		
	}

As the ordering doesn't matters, why not use two stacks?!
minStack - holds everything < k
maxStack - holds > k

Add into same/different array in the order : <minStack>k,k<maxStack>
It is O(n) - time.

comments?

1.Take an new array of length equal to that of the original array
2.Place K in the middle of the new array.
3. Take two pointers i, j: i pointing to the beginning of the array and j pointing to end of the array
3. Now start from the start of the old array.
a. If the element is less than k place it in the beginning of the array and increment i
b. If the element is greater than k place it in the end of the array and decrement j
c. If the element is equal to K just maintain a count of elements equal to k
4. Once the old array array is traversed completely, place these elements in the left over places in the new array. These places will be just next to k at the left/right side depending on the current values of i and j


Assumptions: Since we are asked to place K in the middle i am assuming that there are equal number of integers lesser/greater than K

import java.util.Scanner;

class SortArray
{
public static void main(String args[])
{
int m, n, c, d;
Scanner in = new Scanner(System.in);
int max = 0;
int min = 0;
int eql = 0;
int x;
int y;
int z;
System.out.println("Enter the size of an array");
m = in.nextInt();
int a[] = new int[m];
int b[] = new int[m];

System.out.println("Enter the elements of the matrix");

for ( c = 0 ; c < m ; c++ )
a[c] = in.nextInt();

int k;
System.out.println("Enter the search element");
k = in.nextInt();

for(int i = 0;i<m;i++){
if(a[i]>k)
max++;
else if(a[i]<k)
min++;
else
eql++;
}
x = 0;
y= min+eql;
z=min;
for(int i=0;i<m;i++){
System.out.print("value of i"+i+"\n");
if(a[i]<k){
System.out.print("value of a inside 1st loop"+a[i]+"\n");
b[x] = a[i];
x++;
if(x>=min)
continue;

}
else if(a[i]>k){
System.out.print("value of a inside 2st loop"+a[i]+"\n");
b[y] = a[i];
y++;
if(y>=m)
continue;
}

else{
System.out.print("value of a inside 3rd loop"+a[i]+"\n");
b[z]=a[i];
z++;
if(z>=min+eql)
continue;

}
}

for(int i=0;i<m;i++){
System.out.print(b[i]+"\t");
}

}}

import java.util.Scanner;
 
class SortArray
{
   public static void main(String args[])
   {
      int m, n, c, d;
      Scanner in = new Scanner(System.in);
      int max = 0;
      int min = 0;
      int eql = 0;    
      int x;
      int y;
      int z;
      System.out.println("Enter the size of an array");
      m = in.nextInt();  
      int a[] = new int[m];
      int b[] = new int[m];
      
      System.out.println("Enter the elements of the matrix");

     for (  c = 0 ; c < m ; c++ )
         a[c] = in.nextInt();   
    
      int k;
      System.out.println("Enter the search element");
      k = in.nextInt();     
      
      for(int i = 0;i<m;i++){  	  
      if(a[i]>k)
    	  max++;
      else if(a[i]<k)
    	  min++;
      else
    	  eql++;
      }
      x = 0;
     y= min+eql;
     z=min;
   for(int i=0;i<m;i++){
	   System.out.print("value of i"+i+"\n");
	if(a[i]<k){
		System.out.print("value of a inside 1st loop"+a[i]+"\n");
		b[x] = a[i];
		x++;
		if(x>=min)
			continue;
		
		}
	else if(a[i]>k){
		System.out.print("value of a inside 2st loop"+a[i]+"\n");
		b[y] = a[i];
		y++;		
		if(y>=m)
			continue;
		}

	else{
		System.out.print("value of a inside 3rd loop"+a[i]+"\n");
		b[z]=a[i];
	    z++;
	    if(z>=min+eql)
	    	continue;
		
	}
	}		
	
  for(int i=0;i<m;i++){
	 System.out.print(b[i]+"\t");
  }

}}