## DEV Community is a community of 870,143 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. # 🔬Segregate 0's, 1's, and 2's🔬

Question:

Given an array of size N containing only 0s, 1s, and 2s; sort the array in ascending order.

Example 1:

``````Input:
N = 5
arr[]= {0 2 1 2 0}
Output:
0 0 1 2 2
Explanation:
0s 1s and 2s are segregated
into ascending order.
``````

Logic:

1. Sorting :
• Take the array and sort it ( Using inbuilt function or by implementation)
• display the array
2. Count Technique :
• Take the inpu in the array
• declare 3 variables zero, one and two. Count the number of 0's, 1's, 2's from the array and increment the variables accordingly.
• now run the loop across the array. According to the incrementation of the variable and replace the elements with 0, 1 and 2.
3. 3 Pointer:
• Declare three pointers low, mid high
• mid pointer rotates from low + 1 to high. Use swith case for simplicity
• if arr [ mid ] is 0 the case will be 1st and it will interchange arr [ low ] and arr [ mid ] . then low ++ and mid ++
• if arr [ mid ] is 1 the case will be 2nd and there will be only mid++
• if arr [ mid ] is 2 tthe case will be 3rd and it will interchange arr [ high] and arr [ mid ] . then high - -
• After the looping print the array.
``````
import java.util.*;

public class Solution{
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int sortingArr[] = new int[n];
int threePointer[] = new int[n];
int count[] = new int[n];
for(int i = 0; i < sortingArr.length; i++){
sortingArr[i] = sc.nextInt();
threePointer[i] = count[i] = sortingArr[i];
}

//This is solution through sorting
Arrays.sort(sortingArr);
System.out.println("Segregation through sorting: ");
for(int i = 0; i < sortingArr.length; i++){
System.out.print(sortingArr[i]+" ");
}

//This is solution through counting
int zero = 0;
int one = 0;
int two = 0;

for(int i = 0; i < count.length; i++){
if(count[i] == 0){
zero++;
}else if(count[i] == 1){
one++;
}else if(count[i] == 2){
two++;
}
}

for(int i = 0 ; i < count.length ; i++){
if(zero != 0){
count[i] = 0;
zero--;
}else if(one != 0){
count[i] = 1;
one--;
}else if(two != 0){
count[i] = 2;
two--;
}
}

System.out.println();
System.out.println("Segregation through counting technique: ");

for(int i = 0; i < sortingArr.length; i++){
System.out.print(count[i]+" ");
}

//This is solution through 3 pointer
int lo = 0;
int hi = threePointer.length - 1;
int mid = 0, temp = 0;
while (mid <= hi) {
switch (threePointer[mid]) {
case 0: {
temp = threePointer[lo];
threePointer[lo] = threePointer[mid];
threePointer[mid] = temp;
lo++;
mid++;
break;
}
case 1:
mid++;
break;
case 2: {
temp = threePointer[mid];
threePointer[mid] = threePointer[hi];
threePointer[hi] = temp;
hi--;
break;
}
}
}
System.out.println();
System.out.println("Segregation through 3 pointer technique is: ");
for(int i = 0; i < threePointer.length; i++){
System.out.print(threePointer[i]+" ");
}
}
}
``````