Algorithmes JavaScript: tri par sélection

Supposons que nous ayons un tableau de nombres et que nous voulions le trier par taille d'élément.

Vous pouvez avoir un tableau d'objets, et vous pouvez comparer une propriété d'objet, comme le tri par âge, ou par ordre alphabétique par nom de famille. Les détails ne changent pas.

Nous travaillons de cette manière: nous sélectionnons le premier élément. Ensuite, nous le comparons avec le deuxième élément. Si le deuxième élément est plus petit, nous le remplaçons par le premier. Et ainsi de suite, nous comparons ce premier élément avecchaqueélément du tableau.

Une fois que nous savons que nous avons le plus petit élément, nous passons au deuxième élément, et nous le comparons avecchaqueitem dans le tableau, en ignorant l'index 0, puisque nous savons déjà que c'est le minimum. Et ainsi de suite, jusqu'à la fin du tableau.

Comme vous pouvez le voir, l'algorithme est très coûteux. Il ne se contente pas d'itérer sur chaque élément du tableau: pour chaque élément, il itère à nouveau le tableau.

Sa complexité estO(n^2). Notez que techniquement, le nombre d'éléments que nous comparons ne cesse de diminuer, mais cela ne veut rien dire en termes de conventions Big O pour la complexité.

Voici notre implémentation detri par sélection.

const selectionSort = (originalList) => {
  //we first copy the array to avoid modifying the original array, since objects are passed by reference in JS
  const list = [...originalList]
  const len = list.length
  for (let i = 0; i < len; i++) {
    let min = i
    for (let j = i + 1; j < len; j++) {
      if (list[min] > list[j]) {
        min = j
      }
    }
    if (min !== i) {
      // a new minimum is found. Swap that with the current element
      ;[list[i], list[min]] = [list[min], list[i]]
    }
  }
  return list
}

const listOfNumbers = [1, 6, 3, 4, 5] console.log(selectionSort(listOfNumbers)) //[1,3,4,5,6]

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


Plus de tutoriels js: