Algorithmes JavaScript: tri rapide

Quicksort est un algorithme de recherche plus efficace quetri par sélection,dans la plupart des cas, et il utilise la récursivité.

La récursivité signifie que nous appelons une fonction à partir de la même fonction. C'est une pratique très utile, parfois, et c'est l'un de ces cas.

J'ai dit «dans la plupart des cas», car comme nous le verrons, dans le pire des cas, le tri à bulles peut prendre le même temps que le tri par sélection:O(n^2). Mais dans le meilleur des cas, il fonctionnera àO(n log n), qui est au milieu entreO(n)etO(n^2).

Comment ça marche? Étant donné un tableau, nous choisissons un élément, appelépivot. Nous obtenons alors tous les éléments plus petits que le pivot et les éléments plus gros que le pivot.

Ensuite, nous exécutons la même opération sur le tableau 2 qui composent les éléments de plus en plus petits.

Il est plus facile de voir le code que de le décrire:

const quickSort = (originalList) => {
  const list = [...originalList]

if (list.length < 2) { return list }

const pivot = list[0]

const smaller = list.filter((item) => item < pivot) const bigger = list.filter((item) => item > pivot)

return […quickSort(smaller), pivot, …quickSort(bigger)] }

Dans ce cas, j'ai choisi le pivot comme premier élément du tableau, mais cela pourrait aussi être l'élément du milieu, par exemple:

const pivot = list[Math(floor(list.length / 2)]

Remarquez comment nous copions d'abord le tableau, donc en appelantquickSort()ne modifie pas le tableau d'origine, il renvoie simplement un nouveau tableau trié:

const a = [1, 6, 3, 4, 5, 1, 0, 4, 8]

console.log(quickSort(a)) //[0, 1, 1, 3, 4, 4, 5, 6, 8 console.log(a) //[1, 6, 3, 4, 5, 1, 0, 4, 8]

Téléchargez mon gratuitManuel du débutant JavaScript


Plus de tutoriels js: