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

Organiser les éléments de données sous une forme appropriée est une tâche importante tout en résolvant certains problèmes.

manière efficace. Le problème du tri des éléments est l’un des plus couramment discutés. Problème d'agencement. Dans cet article, nous verrons comment organiser les éléments d'un tableau Trier par leur valeur par ordre décroissant (en C++).

Il existe de nombreux algorithmes de tri différents dans ce champ pour trier les nombres ou les non-chiffres

éléments dans un ordre donné. Dans cet article, nous ne présenterons que deux méthodes simples tri. Le tri à bulles et le tri par sélection Voyons-les un par un avec le bon. Algorithme et code d’implémentation C++.

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

La technologie de tri à bulles est l’une des méthodes de tri les plus courantes et les plus simples.

éléments du tableau. Cette méthode vérifie deux éléments adjacents s'ils sont corrects dans l'ordre, puis passez aux éléments suivants, sinon intervertissez-les pour les placer dans le bon ordre. Disposez les autres éléments dans l'ordre puis passez à l'élément suivant, sinon échangez-les pour le placer à la bonne position ordre. Ensuite, déplacez-vous vers la droite et faites de même pour l’autre paire de valeurs. Disposez dans l'ordre. Déplacez-vous ensuite vers la droite et faites de même avec l’autre paire de valeurs. bulle La technique de tri comporte plusieurs étapes, à la fin de chaque étape un élément est placé dans Position attendue correcte. Jetons un coup d'œil à l'algorithme de la technique de tri à bulles.

Algorithme

• Lire le tableau A et sa taille n en entrée
• Pour la plage de i de 0 à n-1, exécutez
  • Pour j allant de 0 à n - 2, faites
  • Si A[j]
  • Échangez A[j] et A[j + 1]
• Fin si

fin pour

fin pour

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: 96, 95, 89, 84, 78, 74, 63, 58, 45, 44, 36, 25, 12, 12, 10, 8, 5, 2, 

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

Dans la technique de tri par sélection, nous trouvons l'élément minimum ou l'élément maximum À partir de l'index i dans le tableau donné, traduit en chinois : élément du tableau donné à partir de l'index i jusqu'à la fin de ce tableau. Supposons que nous le soyons. Trouvez le plus grand élément. À chaque étape, il trouve la valeur minimale de l'indice i jusqu'à la fin, puis Placez l'élément là où il doit être et recherchez à nouveau l'élément le plus grand suivant. l'index i + 1 et ainsi de suite. Après avoir terminé ces phases, l'ensemble du tableau sera trié. indice je + 1 etc. Après avoir terminé ces étapes, l'ensemble du tableau sera trié par conséquent.

Algorithme

• Lire le tableau A et sa taille n en entrée
• Pour la plage de i de 0 à n-1, exécutez
  • ind := indice du plus grand élément de A de i à n
  • Si A[ i ] <
    • Échange A[i] et A[ind]
  • Fin si
• fin pour

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 max_index( int arr[], int n, int s, int e ){
   int max = 0, max_ind = 0;
   for ( int i = s; i < e; i++ ) {
      if ( arr[i] > max ) {
         max = arr[i];
         max_ind = i;
      }
   }
   return max_ind;
}
void solve( int arr[], int n ){
   int i, j, ind;
   for ( i = 0; i < n; i++ ) {
      ind = max_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: 96, 95, 89, 84, 78, 74, 63, 58, 45, 44, 36, 25, 12, 12, 10, 8, 5, 2,

Conclusion

Un problème de tri est un problème fondamental dans lequel nous organisons des nombres ou d'autres valeurs

dans une logique de permutation donnée. Il existe de nombreuses techniques de tri différentes disponibles ici comprendre et mettre en œuvre Mis en œuvre et facile à comprendre. Ces deux méthodes sont la technique de tri des bulles et Techniques de tri par sélection. En utilisant ces deux méthodes, nous avons trié l'ensemble de données Tri décroissant (non croissant). Ces deux méthodes de tri ne sont pas très efficaces Respectez l’heure, mais elle est facile à comprendre. Les deux méthodes nécessitent un temps O(n2) Durée, où n est la taille de l’entrée. Le tri à bulles peut être rendu plus rapide et simple Vérifiez s'il n'y a pas d'échange dans aucune phase, la prochaine phase consécutive n'aura pas lieu Changez n'importe quoi.

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!