Trier un tableau contenant des éléments de deux types

Il existe différentes manières de trier un tableau ne contenant que deux types d'éléments (c'est-à-dire seulement 1 et 0). Nous discuterons de trois manières différentes d’atteindre cet objectif. La première méthode utilise simplement la fonction prédéfinie sort() pour trier le tableau donné. La deuxième méthode est la méthode de tri par comptage où nous compterons le nombre de 0 et de 1, puis mettrons à jour le tableau en écrivant d'abord le nombre de 0 puis le nombre de 1. Dans la dernière méthode, nous utilisons la méthode du double pointeur.

Énoncé du problème

Nous recevons un tableau contenant uniquement des 1 et des 0. Notre tâche est d'organiser tous les 0 et 1 de sorte que 1 soit à l'extrême droite du tableau et 0 à gauche du tableau

La traduction chinoise de

Exemple

est :

Exemple

Given array: a[] = [ 1, 1, 0, 1, 0, 1, 0, 1 ]
Resultant array: a[] = [ 0, 0, 0, 1, 1, 1, 1, 1 ]

Méthode 1 : Méthode de fissuration par force brute.

Dans cette méthode, nous trierons le tableau directement à l'aide de la fonction sort(). Puisque 1>0, après le tri, tous les 1 seront disposés sur le côté droit du tableau et tous les 0 seront disposés à gauche.

Fonction Sort() : la fonction Sort() prend un temps O(NlogN) et renvoie le tableau par ordre croissant.

La traduction chinoise de

Exemple

est :

Exemple

Vous trouverez ci-dessous une implémentation C++ pour trier un tableau contenant deux types d'éléments.

#include <bits/stdc++.h>
using namespace std;
int main(){
   int a[] = { 1, 1, 0, 1, 0, 1, 0, 1 };
   int len = sizeof(a) / sizeof( a[0] );
   
   // sort function to
   // sort the array
   sort( a, a + len);
   cout<< " After sorting the array, the array obtained is ";
   for(int iterator =0; iterator<len; iterator++){
      cout << a[iterator] <<" ";
   }
   return 0;
}

Sortie

Une fois compilé, le programme ci-dessus produira le résultat suivant : 

After sorting the array, the array obtained is 0 0 0 1 1 1 1 1

Méthode 2 : Méthode de tri par comptage

Dans cette méthode, nous compterons simplement le nombre de 0 et 1 dans le tableau, puis mettrons à jour le tableau avec 0 au début et 1 à la fin.

En faisant cela, nous aurons tous les 0 dans la partie la plus à gauche du tableau et tous les 1 dans la partie la plus à droite du tableau, ce qui représentera automatiquement le tableau trié souhaité.

Il s'agit d'une méthode simple, mais elle insère de nouvelles valeurs dans le tableau au lieu de simplement échanger leurs positions, cette méthode n'est donc pas efficace.

La traduction chinoise de

Exemple

est :

Exemple

Ce qui suit est l'implémentation de la méthode ci-dessus en utilisant C++.

#include <iostream>
using namespace std;
int main() {
   int count = 0 ;
   int a[] = { 1, 1, 0, 1, 0, 1, 0, 1 };
   int len = sizeof(a) / sizeof(a[0]);
   for(int iterator=0; iterator<len; iterator++){
      if( a[iterator] == 0 )
      count++;
   }
   for(int iterator=0 ; iterator<len ; iterator++){
      if(count){
         a[iterator] = 0 ;
         count-- ;
      }
      else a[iterator] = 1;
   }
   cout<< " After sorting the array, the array obtained is ";
   for(int iterator =0 ; iterator<len ; iterator++){
      cout<< a[iterator] << " ";
   }
   return 0;
}

Sortie

Une fois compilé, il produira le résultat suivant : 

After sorting the array, the array obtained is 0 0 0 1 1 1 1 1

Complexité temporelle - Puisque nous n'avons utilisé qu'une seule boucle, la complexité temporelle de cette méthode est O(N)

Complexité spatiale - O(1). Bien que nous utilisions des variables supplémentaires, puisqu’elles sont linéaires, la complexité spatiale est constante.

Méthode 3 : La meilleure façon de résoudre ce problème

Dans cette méthode, nous garderons deux pointeurs, début et fin. Nous allons simultanément parcourir depuis le début du tableau (index 0) en utilisant le pointeur de début et parcourir depuis la fin (index len-1) en utilisant le pointeur de fin.

Notre tâche est d'organiser tous les 1 à l'extrême droite du tableau, ce qui organisera automatiquement tous les 0 sur le côté gauche du tableau.

Nous partons de l'index initial et si l'élément trouvé est 1 nous l'échangeons avec l'élément à l'index "end" et décrémentons le pointeur de fin de 1.

Si l'élément trouvé est 0, alors il n'est pas nécessaire d'effectuer une opération d'échange car il est déjà à la position la plus à gauche, nous augmentons simplement le pointeur de départ de 1.

La traduction chinoise de

Exemple

est :

Exemple

Voici le code pour implémenter cette méthode -

#include <bits/stdc++.h>
using namespace std;
int main(){
   int start =0 ;
   int a[] = { 1, 1, 0, 1, 0, 1, 0, 1 } ;
   int len = sizeof(a) / sizeof( a[0] ) ;
   int end = len-1;
   while(start < end){
      if( a[start] ==1){
         swap(a[start], a[end]);
         end--;
      }
      else
         start++;
   }
   cout<< " After sorting the array, the array obtained is ";
   for(int iterator =0 ; iterator<len ; iterator++){
      cout<< a[iterator] << " ";
   }
   return 0;
}

Sortie

After sorting the array, the array obtained is 0 0 0 1 1 1 1 1

Complexité temporelle - Puisque nous parcourons le tableau une seule fois, la complexité temporelle de cette approche est linéaire, c'est-à-dire O(N)

Complexité spatiale - Puisque nous n'utilisons aucun espace supplémentaire, la complexité spatiale est O(1).

Conclusion

Dans cet article, nous avons abordé trois manières différentes de trier un tableau ne contenant que deux types d'éléments, c'est-à-dire uniquement 1 et 0.

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!