Tri par sélection d'un tableau dynamique en C++

Introduction

Dans ce laboratoire, vous allez apprendre à effectuer un tri par sélection pour trier un tableau dynamique non trié en C++ en utilisant l'algorithme de tri par sélection.

Créer un nouveau fichier C++

Tout d'abord, créez un nouveau fichier C++ nommé main.cpp dans le répertoire ~/project.

touch ~/project/main.cpp

Implémenter l'algorithme de tri par sélection

L'algorithme de tri par sélection fonctionne en sélectionnant l'élément minimum et en le plaçant au début du tableau, puis en sélectionnant le prochain élément minimum dans le reste du tableau et en le plaçant à l'index 1, et ainsi de suite jusqu'à ce que le tableau soit entièrement trié. Voici comment implémenter l'algorithme de tri par sélection en C++ :

#include <iostream>
using namespace std;

// fonction pour échanger la position de deux éléments
void swap(int *a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}

// fonction pour effectuer l'algorithme de tri par sélection
void selectionSort(int array[], int size) {
  for (int step = 0; step < size - 1; step++) {
    int min_idx = step;
    for (int i = step + 1; i < size; i++) {

      // Pour trier dans l'ordre décroissant, changez > en < dans cette ligne.
      // Sélectionnez l'élément minimum dans chaque boucle.
      if (array[i] < array[min_idx])
        min_idx = i;
    }

    // placez min à la position correcte
    swap(&array[min_idx], &array[step]);
  }
}

Dans ce bloc de code, nous définissons une fonction swap() pour échanger la position de deux éléments dans le tableau, et une fonction selectionSort() pour effectuer l'algorithme de tri par sélection sur le tableau.

Saisir le tableau

Dans cette étape, vous allez entrer le tableau dynamique qui doit être trié. Vous pouvez le faire en invitant l'utilisateur à entrer les éléments du tableau un par un :

// code principal
int main() {
  int size;
  cout<<"Entrez la taille du tableau : ";
  cin>>size; // Entrez la taille du tableau
  int* data = new int[size]; // Décarez dynamiquement le tableau

  // Entrez les éléments du tableau un par un
  for(int i = 0; i < size; i++) {
    cout<<"Entrez l'élément "<<i+1<<" : ";
    cin>>data[i];
  }

Effectuer un tri par sélection

Maintenant que nous avons le tableau non trié, nous pouvons effectuer l'algorithme de tri par sélection sur celui-ci en utilisant la fonction selectionSort() que nous avons définie précédemment. Voici comment faire :

  // Effectuez le tri par sélection
  selectionSort(data, size);

Afficher le tableau trié

Enfin, nous allons afficher le tableau trié dans la console en utilisant une boucle dans une fonction appelée printArray(). Voici comment faire :

  // Affichez le tableau trié
  cout << "\nTableau trié : ";
  for (int i = 0; i < size; i++)
    cout << data[i] << " ";

  // Libérez la mémoire utilisée par le tableau dynamique
  delete[] data;
  return 0;
}

Compiler et exécuter le code

Pour compiler et exécuter le code, ouvrez un terminal et accédez au dossier où se trouve votre fichier main.cpp. Ensuite, exécutez les commandes suivantes :

g++ main.cpp -o main
./main

Le tableau trié devrait être affiché dans la console.

Résumé

Dans ce laboratoire, vous avez appris à utiliser l'algorithme de tri par sélection pour trier un tableau dynamique non trié en C++. Pour ce faire, vous avez dû entrer le tableau, implémenter l'algorithme de tri par sélection, effectuer le tri, afficher le tableau trié, puis compiler et exécuter le code dans le terminal. Avec ces compétences, vous serez capable de trier des tableaux de toute taille en utilisant le tri par sélection.