Apprendre l'algorithme de tri rapide

Le tri rapide est l'un des algorithmes les plus efficaces et il utilise la technique diviser pour régner pour trier les tableaux.

Comment fonctionne le tri rapide

L'idée principale du tri rapide est d'aider un élément à la fois à se déplacer vers sa position correcte dans un tableau non trié. Cet élément s'appelle le pivot.

L'élément pivot est dans la bonne position lorsque :

1. Tous les éléments à sa gauche sont plus petits.
2. Tous les éléments à sa droite sont plus grands.

Peu importe que les nombres à gauche ou à droite soient déjà triés. Ce qui compte c'est que le pivot soit dans la bonne position dans le tableau.

// examples of the pivot 23 positioned correctly in the array:
[3, 5, 6, 12, 23, 25, 24, 30]
[6, 12, 5, 3, 23, 24, 30, 25]
[3, 6, 5, 12, 23, 30, 25, 24]

Tous ces éléments sont des sorties valides d'un tableau dont le pivot est 23.

Trouver la bonne position du pivot

Le tri rapide aide le pivot à trouver sa position correcte dans le tableau. Par exemple, si le pivot est positionné au début du tableau mais ne correspond pas au plus petit nombre, le tri rapide détermine qu'il doit se déplacer de 5 étapes pour faire de la place aux 5 éléments plus petits du tableau - en supposant qu'il y en ait 5. chiffres.

Disons que nous avons le tableau : [10, 4, 15, 6, 23, 40, 1, 17, 7, 8] et 10 est le pivot :

À ce stade :

• Le chiffre 10 ne sait pas s’il est dans la bonne position ni combien de pas il doit faire pour y arriver. Le tri rapide commence par comparer 10 avec la valeur à l'index suivant.
• En voyant que 4 est plus petit, Quick Sort enregistre que le pivot doit avancer d'un pas pour permettre à 4 de passer devant lui.
• Donc numberOfStepsToMove augmente de 1.

Ensuite, à l'index 2, la valeur est 15, ce qui est supérieur à 10. Puisqu'aucun ajustement n'est nécessaire, Le tri rapide maintient le nombre de pas inchangé et passe à l'élément suivant du tableau.

À l'index suivant, la valeur est 6, ce qui est inférieur à 10. Le tri rapide augmente le nombre de pas à 2, car le pivot doit maintenant faire de la place pour deux nombres plus petits : 4 et 6 .

Maintenant, 6 devra être échangé avec 15 pour garder les plus petits nombres les uns à côté des autres sur le côté gauche du tableau. Nous échangeons les nombres en fonction des valeurs actuelles de l'index et du numberOfStepsToMove.

Le tri rapide continue de parcourir le tableau, augmentant le nombre de pas à déplacer en fonction du nombre de nombres plus petits que le pivot. Cela aide à déterminer jusqu'où le pivot doit se déplacer pour atteindre sa position correcte.

Le numberOfStepsToMove ne change pas pour 23 ou 40 car les deux valeurs sont supérieures au pivot et ne devraient pas le précéder dans le tableau :

Maintenant, lorsque le tri rapide boucle sur la valeur 1 à l'index 6, numberOfStepsToMove passe à 3 et l'échange avec le numéro à l'index 3 :

Le tri rapide poursuit ce processus jusqu'à ce qu'il atteigne la fin du tableau :

Maintenant que nous avons atteint la fin du tableau, nous savons qu'il y a 5 nombres inférieurs à 10. Par conséquent, le pivot (10) doit avancer de 5 pas jusqu'à sa position correcte, où il est supérieur à tous les nombres. chiffres avant lui.

Voyons à quoi cela ressemble dans le code :

// examples of the pivot 23 positioned correctly in the array:
[3, 5, 6, 12, 23, 25, 24, 30]
[6, 12, 5, 3, 23, 24, 30, 25]
[3, 6, 5, 12, 23, 30, 25, 24]

Maintenant que nous avons une fonction pour nous aider à trouver où placer le pivot, voyons comment Qucik Sort divise le tableau en tableaux plus petits et utilisons la fonction getNumberOfStepsToMove pour placer tous les éléments du tableau.

const getNumberOfStepsToMove = (arr, start = 0, end = arr.length - 1) => {
  let numberOfStepsToMove = start;
  // we're picking the first element in the array as the pivot
  const pivot = arr[start];

  // start checking the next elements to the pivot
  for (let i = start + 1; i <= end; i++) {
    // is the current number less than the pivot?
    if (arr[i] < pivot) {
      // yes - so w should increase numberOfStepsToMove
// or the new index of the pivot
      numberOfStepsToMove++;

      // now swap the number at the index of numberOfStepsToMove with the smaller one
      [arr[i], arr[numberOfStepsToMove]] = [arr[numberOfStepsToMove], arr[i]];
    } else {
      // what if it's greater?
      // do nothing -- we need to move on to the next number
      // to check if we have more numbers less that pivot to increase numberOfStepsToMove or not
    }
  }

  // now we know the pivot is at arr[start] and we know that it needs to move numberOfStepsToMove
  // so we swap the numbers to place the pivot number to its correct position
  [arr[start], arr[numberOfStepsToMove]] = [
    arr[numberOfStepsToMove],
    arr[start],
  ];

  return numberOfStepsToMove;
};

Le tri rapide exploite la récursivité pour diviser efficacement le tableau en sous-tableaux plus petits, garantissant ainsi que les éléments sont triés en les comparant avec un pivot.

function quickSort(arr, left = 0, right = arr.length - 1) {
  // pivotIndex the new index of the pivot in in the array
  // in our array example, at the first call this will be 5, because we are checking 10 as the pivot
  // on the whole array
  let pivotIndex = getNumberOfStepsToMove(arr, left, right);
}

• L'algorithme trie de manière récursive le sous-tableau gauche qui contient des éléments plus petits que le pivot.
• La récursion s'arrête lorsque le sous-tableau contient un ou zéro élément, car il est déjà trié.

Maintenant, nous devons effectuer le même processus sur le côté droit du tableau :

// examples of the pivot 23 positioned correctly in the array:
[3, 5, 6, 12, 23, 25, 24, 30]
[6, 12, 5, 3, 23, 24, 30, 25]
[3, 6, 5, 12, 23, 30, 25, 24]

Dans cet exemple, le côté droit est déjà trié mais l'algorithme ne le sait pas et il aurait été trié s'il ne l'avait pas été.

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!