# Sorting in Linear Time

question-SORTING IN LINEAR TIME
You will be given an array containing only 0s, 1s and 2s. you have sort the array in linear time that is O(N) where N is the size of the array.

Input Format:
The first line contains N, which is the size of the array. The following N lines contain either 0, or 1, or 2.

Constraints:
Each input element x, such that x ∈ { 0, 1, 2 }.

Output Format
Output the sorted array with each element separated by a newline.

Sample Input
5
0
1
2
1
2
Sample Output
0
1
1
2
2

BOTH TEST CASE IS FAILED.

// Java program to sort an array of 0, 1 and 2
import java.util.*;

class Main {

``````// Sort the input array, the array is assumed to
// have values in {0, 1, 2}
static void sort012(int a[], int arr_size)
{
int lo = a[0];
int hi = arr_size - 1;
int mid = a[0], temp = 0;
while (mid <= hi) {
switch (a[mid]) {
case 0: {
temp = a[lo];
a[lo] = a[mid];
a[mid] = temp;
lo++;
mid++;
break;
}
case 1:
mid++;
break;
case 2: {
temp = a[mid];
a[mid] = a[hi];
a[hi] = temp;
hi--;
break;
}
}
}
}

/* Utility function to print array arr[] */
static void printArray(int arr[], int arr_size)
{
int i;
for (i = 0; i < arr_size; i++)
System.out.println(arr[i] );
System.out.println("");
}

/*Driver function to check for above functions*/
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int N=sc.nextInt();
int arr[] = new int[N];//{ 0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1 };
int i,temps;
for(i=0;i<N;)
{
temps=sc.nextInt();
if(temps>=0 && temps<3)
{	arr[i]=temps;
i++;
}
else
{
continue;
}
}
int arr_size = arr.length;
sort012(arr, arr_size);
printArray(arr, arr_size);
}
``````

}