Sort an array of 0, 1 and 2 using Java

Given an array consisting of 0, 1 and 2, sort the elements in order such that all 0's come before 1's and all 2's come last. We have to sort all elements of the array in-place.

We can use the DNF (Dutch Flag) sorting algorithm to solve this problem. For example,

Input-1 -

arr[ ]= {2,0,0,1,2,1 }

Output -

0 0 1 1 2 2

Explanation − Use DNF The sorting algorithm sorts the given array containing 0, 1 and 2, it will output as {0,0,1,1,2,2}.

Input-2 −

arr[ ] = {0,1,1,2,1,1,0}

Output -

0 0 1 1 1 1 2

Explanation − Use DNF sorting algorithm Sort the given array of elements containing 0, 1 and 2, it will output as {0,0,1,1,1,1,2}.

Method to solve this problem

In the given array of 0, 1 and 2, we can use the DNF sorting algorithm.

DNF sorting algorithm − This algorithm requires 3 pointers to traverse the entire array and exchange the necessary elements.

• Create a low pointer at the beginning of the array and a high pointer pointing to the end of the array.

• Find the midpoint of the array and create a midpointer that iterates from the beginning to the end of the array.

• If the middle pointer of the array is '0', swap the element pointing to the low pointer. Added low and mid pointers.

• If the middle pointer of the array is '2', swap it with the element pointing to the high pointer. Increase the middle pointer and decrease the high pointer.

• If the middle pointer of the array is '1', increase the middle pointer.

Example

Demonstration

public class Solution {
   public static void binarySorting(int arr[], int n){
      int low=0;
      int high= n-1;
      int mid=0;
      while(mid<=high){
         if(arr[mid]==0){
            int temp= arr[mid];
            arr[mid]= arr[low];
            arr[low]= temp;
            mid++;
            low++;
         }
         if(arr[mid]==1){
            mid++;
         }
         if(arr[mid]==2){
            int temp= arr[mid];
            arr[mid]= arr[high];
            arr[high]= temp;
            high--;
         }
      }
   }
   public static void print(int arr[], int n){
      for (int i = 0; i < n; i++)
         System.out.print(arr[i] +" ");
   }
   public static void main(String[] args){
      int arr[] ={ 0,0,1,0,1,0,1,2,2};
      int n = arr.length;
      binarySorting(arr, n);
      print(arr, n);
   }
}

Output

Running the above code will generate the following output:

0 0 0 0 1 1 1 1 2

The above is the detailed content of Sort an array of 0, 1 and 2 using Java. For more information, please follow other related articles on the PHP Chinese website!