Trier la liste chaînée en C++

Pour trier une liste simplement chaînée par ordre croissant, comparez les valeurs voisines et échangez celles qui ne sont pas dans le bon ordre. Les liens restent en place : cette version trie les valeurs stockées dans les nœuds sans réorganiser les nœuds eux-mêmes. L’implémentation ci-dessous utilise le tri à bulles et comprend un programme pilote complet.

Ce que stocke une liste simplement chaînée

Une liste simplement chaînée est une chaîne de nœuds. Chaque nœud stocke une valeur et un pointeur vers le nœud suivant ; le dernier pointe vers nullptr. Le pointeur head de la liste désigne son premier nœud. Contrairement à un tableau, les nœuds n’ont pas besoin d’occuper des emplacements mémoire consécutifs. Pour atteindre un nœud, partez de head et suivez les pointeurs next successivement.

Cette structure permet une insertion en tête en temps constant, mais trouver une position plus loin nécessite de parcourir la liste. Le tri visite donc les nœuds en suivant les liens. La liste est générique et peut contenir différents types, à condition que ceux-ci prennent en charge les comparaisons et les échanges utilisés par le tri.

Construire une liste simplement chaînée minimale en C++

Chaque nœud initialise ensemble sa valeur et son lien. La liste possède ses nœuds et les libère dans son destructeur ; la copie est désactivée pour éviter que deux listes ne tentent de supprimer les mêmes nœuds. insertAtHead ajoute une valeur avant le premier nœud actuel, et displayAll affiche les valeurs dans l’ordre du parcours.

Trier la liste chaînée par ordre croissant

Le tri à bulles effectue plusieurs passages sur des paires de valeurs voisines. Lorsque la valeur courante est supérieure à la suivante, std::swap échange les valeurs. À la fin d’un passage, la plus grande valeur qui n’est pas encore à sa place s’est déplacée vers la droite ; last marque la limite qui permet au passage suivant d’ignorer ce suffixe. L’algorithme s’arrête lorsqu’un passage n’effectue aucun échange. Une liste vide entraîne un retour immédiat, et une liste à un seul nœud ne nécessite aucune comparaison.

Dans le pire des cas, le tri prend un temps O(n²) et utilise un espace supplémentaire O(1). Il préserve les liens entre les nœuds, mais modifie la valeur que chacun contient. T doit prendre en charge operator> et être échangeable ; cette implémentation ne trie pas en réorganisant les nœuds.

Compiler et exécuter l’exemple

Enregistrez ce programme complet sous le nom sort.cpp. Le programme pilote insère 50, 16 et 45 en tête ; le parcours les affiche donc dans l’ordre 45, 16, 50 avant le tri. Il effectue ensuite le tri et affiche les valeurs par ordre croissant.

Le code et les libellés ou sorties affichés dans cette section restent en anglais.

#include <iostream>
#include <utility>

template <class T>
struct Node {
  T data;
  Node<T>* next;

  explicit Node(const T& value) : data(value), next(nullptr) {}
};

template <class T>
class SinglyLinkedList {
 private:
  Node<T>* head;

 public:
  SinglyLinkedList() : head(nullptr) {}

  SinglyLinkedList(const SinglyLinkedList&) = delete;
  SinglyLinkedList& operator=(const SinglyLinkedList&) = delete;

  ~SinglyLinkedList() {
    while (head != nullptr) {
      Node<T>* next = head->next;
      delete head;
      head = next;
    }
  }

  void insertAtHead(const T& value) {
    Node<T>* node = new Node<T>(value);
    node->next = head;
    head = node;
  }

  void displayAll() const {
    const Node<T>* current = head;
    while (current != nullptr) {
      std::cout << current->data << '\n';
      current = current->next;
    }
  }

  void sortLinkedList() {
    if (head == nullptr) {
      return;
    }

    Node<T>* last = nullptr;
    bool swapped;
    do {
      swapped = false;
      Node<T>* current = head;
      while (current->next != last) {
        if (current->data > current->next->data) {
          using std::swap;
          swap(current->data, current->next->data);
          swapped = true;
        }
        current = current->next;
      }
      last = current;
    } while (swapped);
  }
};

int main() {
  SinglyLinkedList<int> list;
  list.insertAtHead(50);
  list.insertAtHead(16);
  list.insertAtHead(45);

  std::cout << "Before sorting:\n";
  list.displayAll();
  list.sortLinkedList();
  std::cout << "After sorting:\n";
  list.displayAll();
}

L’exécution vérifiée affiche :

Before sorting:
45
16
50
After sorting:
16
45
50

Compilez et exécutez le programme avec un compilateur C++11 ou ultérieur, depuis le répertoire qui contient le fichier :

g++ -std=c++11 -Wall -Wextra -pedantic sort.cpp -o sort

./sort

L’opération d’affichage écrit une valeur par ligne, comme dans la sortie ci-dessus.