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:
- Sorting :
- Take the array and sort it ( Using inbuilt function or by implementation)
- display the array
- 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 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]+" ");
}
}
}
Top comments (0)