CareerCup

dutch national flag algorithm? , in place sorting, O(n) complexity.

In this case we can use count sort as all the numbers are less than number 7 which can act as a key in count sort and the range of the numbers is also small so count sort is best suited in these cases with complexity O(k+N) = O(N) in a linear time

So the input is fixed {4,5,6,4,5,6} ?

function(array[ ])   //O(1)
{
return {4,4,5,5,6,6};
}

Or can we please define the input instances in their fully generality, please?

// int[] input = {4,5,6,6,6,6,5,4,4,6}
public static void sortArray(int[] input)
{
int start=0;
int end = input.length-1;
int counter_4 = 0;
int counter_6 = input.length-1;
while(input[counter_4]==4)
{
counter_4++;
start++;
}
while(input[counter_6]==6)
{
counter_6--;
end --;
}
while(start <end) {
if(input[start]==4 && start > counter_4)
{
int tmp = input[counter_4];
input[counter_4] = input[start];
input[start] = tmp;
counter_4++;
if(tmp!=4 && tmp!=6)
start++;
}
else if(input[start] == 6 && start<counter_6)
{
int tmp = input[counter_6];
input[counter_6] = input[start];
input[start] = tmp;
counter_6--;
if(tmp!=4 && tmp!=6)
start++;
}
else
start++;
}
System.out.println("Printing sorted array ");
for (int i = 0; i < input.length; i++) {
System.out.print(input[i]+" ");
}
System.out.println();
}

Quicksort in this case won't be a good option as data is almost sorted and this is the worst case for quick sort (n square).
An merge sort (require additional space) and a insert sort (no additional space) could be a nice option.

Just use merge procedure of merge sort?

Divide the array into two parts and use merge sort. Best case time complexity is O(n).

void Partition(int data[], int size1, int low, int high)
{
int p = -1;
int q = size1;
for (int i = 0; i < q;)
{
if (data[i] < low)
{
swap(data[i], data[++p]);
++i;
}
else if (data[i] > high)
swap(data[i], data[--q]);
else ++i;
}
}
//low=5 and high=5

As elements are partially sorted and array has only few elements, it would be a perfect use case for Insertion Sort!

Actually none of the above ! waste of time guys, all same answers but no out of box thinking.

If you see input, the numbers are out of order at most by 4 numbers.

so what to do : build heap of 4 numbers, remove min and keep advancing after 5th number and adding new number. At the end when all numbers exhaust, add all remaining numbers on heap one by one by deleting min.

This is what the interviewer is expecting.