Programme C++ : trier les éléments du tableau par ordre croissant

Afin de résoudre efficacement certains problèmes, il est très important de disposer les éléments de données dans la bonne position commande. L’un des problèmes de permutation les plus courants est le problème de l’ordre des éléments. ce Cet article montrera comment trier les membres d'un tableau par ordre croissant (selon la valeur ne cesse d’augmenter).

Pour organiser des éléments numériques ou non numériques dans un ordre spécifique, il existe de nombreuses façons Des algorithmes de tri peuvent être utilisés dans ce domaine. Juste deux techniques de tri simples sera présenté dans cet article. Tri par sélection et tri à bulles. Vérifions-les un par un Implémentez le code individuellement en utilisant la technologie appropriée et le C++.

Trier le tableau par ordre croissant à l'aide de la technique de tri à bulles

L'un des moyens les plus populaires et les plus simples de trier les composants d'un tableau est Méthode de tri à bulles. Dans cette méthode, deux éléments sont vérifiés séquentiellement pour Vérifiez s'ils sont dans le bon ordre. Sinon, la méthode permute les éléments jusqu'à ce qu'ils La commande est correcte. Après cela, déplacez-vous vers la droite et répétez le processus avec l'autre groupe. valeurs. Les éléments individuels sont placés dans la position attendue correcte à la fin Chacune des différentes étapes de la technologie de tri des bulles. Regardez le tri des bulles algorithme.

Algorithme

• Lire le tableau A et sa taille n en entrée
• Pour i allant de 0 à n-1, exécutez
  • Pour j allant de 0 à n - 2, faites
    • Si A[j] > A[j + 1], alors
      • Échangez A[j] et A[j + 1]
    • Si ça se termine
  • Fin
• Fin

Exemple

#include <iostream>
using namespace std;
void display( int arr[], int n ){
   for ( int i = 0; i < n; i++ ) {
      cout << arr[i] << ", ";
   }
}
void swap ( int &a, int &b ){
   int temp = a;
   a = b;
   b = temp;
}
void solve( int arr[], int n ){
   int i, j;
   for ( i = 0; i < n; i++ ) {
      for ( j = 0; j < n-1; j++ ) {
         if ( arr[j] > arr[ j+1 ] ) {
            swap( arr[j], arr[ j + 1 ] );
         }
      }
   }
}
int main(){
   int arr[] = {8, 45, 74, 12, 10, 36, 58, 96, 5, 2, 78, 44, 25, 12, 89, 95, 63, 84};
   int n = sizeof( arr ) / sizeof( arr[0] );
   cout << "Array before sorting: ";
   display(arr, n);
   solve( arr, n );
   cout << "\nArray After sorting: ";
   display(arr, n);
}

Sortie

Array before sorting: 8, 45, 74, 12, 10, 36, 58, 96, 5, 2, 78, 44, 25, 12, 89, 95, 63, 84, 
Array After sorting: 2, 5, 8, 10, 12, 12, 25, 36, 44, 45, 58, 63, 74, 78, 84, 89, 95, 96, 

Trier le tableau par ordre croissant à l'aide de la technique de tri par sélection

Lorsque nous utilisons la stratégie de tri par sélection, nous partons de l'index I et allons jusqu'à la fin Étant donné un tableau, recherchez l'élément minimum ou maximum. Supposons que nous soyons Révélez chaque ingrédient. Il localise le plus petit élément de l'index I jusqu'à la fin A chaque étape, placez les éléments en place et répétez le processus Trouvez l'élément suivant le plus grand à partir de l'index I + 1, et ainsi de suite. Ces étapes sont sur le point d'être achevées, Ensuite, l'ensemble du tableau sera trié de manière appropriée.

Algorithme

• Lire le tableau A et sa taille n en entrée
• Pour i allant de 0 à n-1, exécutez
  • ind := plus petit indice d'élément de i à n dans A
  • Si A[ i ] > A[ ind ], alors
    • Échange A[ i ] et A[ ind ]​​i>
  • Si ça se termine
• Fin

Exemple

#include <iostream>
using namespace std;
void display( int arr[], int n ){
   for ( int i = 0; i < n; i++ ) {
      cout << arr[i] << ", ";
   }
}
void swap ( int &a, int &b ){
   int temp = a;
   a = b;
   b = temp;
}
int min_index( int arr[], int n, int s, int e ){
   int min = 99999, min_ind = -1;
   for ( int i = s; i < e; i++ ) {
      if ( arr[i] < min ) {
         min = arr[i];
         min_ind = i;
      }
   }
   return min_ind;
}
void solve( int arr[], int n ){
   int i, j, ind;
   for ( i = 0; i < n; i++ ) {
      ind = min_index( arr, n, i, n );
      if ( arr[i] > arr[ ind ] ) {
         swap( arr[i], arr[ ind ] );
      }
   }
}
int main(){
   int arr[] = {8, 45, 74, 12, 10, 36, 58, 96, 5, 2, 78, 44, 25, 12, 89, 95, 63, 84};
   int n = sizeof( arr ) / sizeof( arr[0] );
   cout << "Array before sorting: ";
   display(arr, n);
   solve( arr, n );
   cout << "\nArray After sorting: ";
   display(arr, n);
}

Sortie

Array before sorting: 8, 45, 74, 12, 10, 36, 58, 96, 5, 2, 78, 44, 25, 12, 89, 95, 63, 84, 
Array After sorting: 2, 5, 8, 10, 12, 12, 25, 36, 44, 45, 58, 63, 74, 78, 84, 89, 95, 96, 

Conclusion

Un problème fondamental est le tri, qui consiste à organiser les nombres ou d'autres éléments selon l'ordre Logique de mise en page prédéterminée. Il existe de nombreuses autres techniques de séquençage disponibles dans ce domaine, Mais dans cet article, nous nous concentrerons sur deux éléments faciles à utiliser et à comprendre. ces deux-là Les techniques de tri comprennent la technologie de tri par sélection et la technologie de tri à bulles. nous avons Utilisez ces deux techniques pour organiser l’ensemble de données par ordre croissant (et non décroissant). Bien que peu efficaces en termes de temps, ces deux techniques de tri sont simples. les deux Les deux techniques nécessitent un investissement en temps O(n²), où n est entrer. Tant qu'on juge s'il y a eu un changement, il n'y aura aucun changement dans les étapes suivantes. Il n’y a aucun échange à aucun moment, ce qui accélère le tri des bulles.

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!