Programme JavaScript pour trier une liste chaînée de 0, 1 et 2

Dans ce tutoriel, nous allons apprendre un programme JavaScript pour trier une liste chaînée de 0, 1 et 2. Les algorithmes de tri sont essentiels pour tout langage de programmation, et JavaScript ne fait pas exception. Le tri d'une liste chaînée de 0, de 1 et de 2 est un problème courant auquel les développeurs sont confrontés lors des entretiens de codage et des applications du monde réel.

Voyons donc comment trier une liste chaînée de 0, 1 et 2 à l'aide de la programmation JavaScript.

Qu'est-ce que le tri ?

Le tri est le processus de disposition des éléments dans un ordre spécifique (ascendant ou décroissant). Il s’agit d’une opération fondamentale en informatique et a de nombreuses applications dans des scénarios réels. Les algorithmes de tri sont utilisés pour organiser les données pour des recherches efficaces, réduire la redondance et optimiser la complexité spatiale et temporelle.

Voici quelques exemples de tri en JavaScript :

Exemple 1 - Trier un tableau de nombres par ordre croissant :

Input: ar[]= [5, 3, 8, 1, 2, 9]
Output: [1, 2, 3, 5, 8, 9]

Exemple 2 - Trier un tableau de chaînes par ordre alphabétique :

Input: ['apple', 'banana', 'orange', 'grape']
Output: ['apple', 'banana', 'grape', 'orange']

Qu'est-ce qu'une liste chaînée ?

Une liste chaînée est une structure de données linéaire composée de nœuds liés entre eux par des pointeurs. Chaque nœud contient un élément de données et une référence au nœud suivant dans la liste. Les listes chaînées sont souvent utilisées dans les structures de données dynamiques où la taille des données change fréquemment.

Énoncé du problème

Le but est d'organiser et d'afficher la liste chaînée composée de 0, 1 et 2 dans l'ordre. Comprenons-le avec un exemple :

Exemple

Input: 1 -> 1 -> 2 -> 0 -> 2 -> 0 -> 1 -> NULL 
Output: 0 -> 0 -> 1 -> 1 -> 1 -> 2 -> 2 -> NULL
Input: 1 -> 1 -> 2 -> 1 -> 0 -> NULL 
Output: 0 -> 1 -> 1 -> 1 -> 2 -> NULL 

Algorithme de tri des listes chaînées de 0, 1 et 2

Étapes pour trier la liste chaînée de 0, 1 et 2 à l'aide de l'algorithme de tri par comptage -

Étape 1 - Définissez une fonction sortList(head) qui prend en entrée l'en-tête de la liste chaînée.

ÉTAPE2 - Initialisez un tableau count count[] de taille 3, avec tous les éléments égaux à 0.

ÉTAPE 3 - Parcourez la liste chaînée et incrémentez le nombre de données de nœud à l'index correspondant dans le tableau de comptage.

ÉTAPE 4 - Parcourez à nouveau la liste chaînée et remplacez les données du nœud par la valeur d'index la plus basse par un nombre supérieur à 0.

Étape 5 - Réduisez le nombre de données de nœud pour chaque remplacement.

Étape 6 - Imprimez la liste chaînée avant et après le tri.

Essayons maintenant de comprendre l'algorithme ci-dessus avec un exemple de son implémentation à l'aide de JavaScript.

Exemple

Le programme JavaScript suivant trie une liste chaînée contenant 0, 1 et 2 à l'aide de l'algorithme de tri par comptage. L'algorithme compte d'abord la fréquence d'apparition de 0, 1 et 2 dans la liste, puis met à jour la valeur du nœud dans la liste en fonction du nombre de chaque valeur.

/* Link list node */
class Node {
   constructor(data) {
      this.data = data;
      this.next = null;
   }
}
class LinkedList {
   constructor() {
      this.head = null;
   }
   push(new_data) {
      const new_node = new Node(new_data);
      new_node.next = this.head;
      this.head = new_node;
   }
   printList() {
      let currentNode = this.head;
      let value = "";
      while (currentNode !== null) {
         value += currentNode.data + " -> ";
         currentNode = currentNode.next;
      }
      console.log(value + "null");
   }
   sortList() {
      const count = [0, 0, 0]; // Initialize count of '0', '1' and '2' as 0
      let ptr = this.head;
      while (ptr !== null) {
         count[ptr.data] += 1;
         ptr = ptr.next;
      }
      ptr = this.head;
      let i = 0;
      while (ptr !== null) {
         if (count[i] === 0) {
            ++i;
         } else {
            ptr.data = i;
            --count[i];
            ptr = ptr.next;
         }
      }
   }
}
const linkedList = new LinkedList();
linkedList.push(0);
linkedList.push(1);
linkedList.push(0);
linkedList.push(2);
linkedList.push(1);
linkedList.push(1);
linkedList.push(2);
linkedList.push(1);
linkedList.push(2);
console.log("Before sorting:");
linkedList.printList();
linkedList.sortList();
console.log("After sorting:");
linkedList.printList();

Conclusion

Dans l'ensemble, le programme Javascript ci-dessus démontre un moyen efficace de trier une liste chaînée contenant uniquement 0, 1 et 2 à l'aide de techniques de comptage. L'algorithme a une complexité temporelle de O(n) et une complexité spatiale de O(1), ce qui en fait la solution optimale pour ce problème de tri particulier.

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!