Arrays/sort0s1sAnd2s.java at main · rjsrkr9/Arrays · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
//Question: sort the array in ascending order where the elements only contains 0s , 1s & 2s.
//           (Dutch Flag Algorithm) [sort three color problem]
package arrays;

public class sort0s1sAnd2s {
    public static void main(String[] args) {
        int [] arr={0, 1, 2, 2, 0, 1, 1, 2, 0};
        int n=arr.length;
//         //Method 1: two pass method
//         int noOfZeros=0, noOfOnes=0;
//       for(int i=0; i<n; i++){
//          if(arr[i]==0) noOfZeros++;
//          if(arr[i]==1) noOfOnes++;
//       }
//       for(int i=0; i<n; i++){
//         if(i<noOfZeros) arr[i]=0;
//         else if(i>=noOfZeros && i<noOfOnes+noOfZeros) arr[i]=1;
//         else arr[i]=2;
//       }
//       for(int ele : arr){
//      System.out.print(ele+" ");
//   }
             //Method 2: one pass method (Dutch Flag Algorithm) or three pointer method.
            int lo=0, md=0, hi=n-1;
            while(md<=hi){
                if(arr[md]==0){
                    int temp=arr[md];
                    arr[md]=arr[lo];
                    arr[lo]=temp;
                    md++;
                    lo++;
                }else if(arr[md]==1){
                    md++;
                }else{  //arr[md]==2
                    int temp=arr[md];
                    arr[md]=arr[hi];
                    arr[hi]=temp;
                    hi--;
                }
            }
            for(int ele : arr){
     System.out.print(ele+" ");
  }
    }
}