Trier un tableau de 0, 1 et 2 en utilisant Java

Étant donné un tableau composé de 0, 1 et 2, triez les éléments dans l'ordre de telle sorte que tous les 0 viennent avant les 1 et que tous les 2 viennent en dernier. Nous devons trier tous les éléments du tableau sur place.

Nous pouvons utiliser l'algorithme de tri DNF (Dutch Flag) pour résoudre ce problème. Par exemple,

Input-1 -

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

Output -

0 0 1 1 2 2

Explanation - Utilisez l'algorithme de tri DNF pour trier le tableau donné contenant 0, 1 et 2, il affichera {0, 0, 1,1,2,2}.

Input-2 −

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

Output -

0 0 1 1 1 1 2

Explication − Triez le tableau donné d'éléments contenant 0, 1 et 2 à l'aide de l'algorithme de tri DNF, il affichera {0,0, 1, 1,1,1,2}.

Comment résoudre ce problème

Dans le tableau donné de 0, 1 et 2, nous pouvons utiliser l'algorithme de tri DNF.

Algorithme de tri DNF - Cet algorithme nécessite 3 pointeurs pour parcourir l'ensemble du tableau et échanger les éléments nécessaires.

• Créez un pointeur bas au début du tableau et un pointeur haut pointant vers la fin du tableau.

• Trouvez le point médian du tableau et créez un pointeur médian qui itère du début du tableau jusqu'à la fin.

• Si le pointeur du milieu du tableau est « 0 », échangez l'élément pointant vers le pointeur bas. Ajout de pointeurs bas et milieu.

• Si le pointeur du milieu du tableau est « 2 », échangez-le avec l'élément pointant vers le pointeur haut. Augmentez le pointeur du milieu et diminuez le pointeur haut.

• Si le pointeur du milieu du tableau est « 1 », incrémentez le pointeur du milieu.

Exemple

Démonstration

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

L'exécution du code ci-dessus générera la sortie suivante :

0 0 0 0 1 1 1 1 2

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!