Tri à bulles, tri par sélection, tri par insertion | Structures de données et algorithmes en JavaScript

Les algorithmes de tri sont l'épine dorsale de nombreuses tâches informatiques, jouant un rôle crucial dans l'organisation des données pour un accès et un traitement efficaces. Que vous soyez un débutant commençant tout juste à explorer le monde des algorithmes ou un développeur chevronné cherchant à rafraîchir ses connaissances, comprendre ces techniques de tri fondamentales est essentiel. Dans cet article, nous explorerons certains des algorithmes de tri les plus basiques : tri à bulles, tri par sélection et tri par insertion.

Tri à bulles

Bubble Sort est un algorithme de tri simple basé sur des comparaisons. Il parcourt une liste à plusieurs reprises, compare les éléments adjacents et les échange s'ils sont dans le mauvais ordre. Ce processus se poursuit jusqu'à ce qu'aucun échange ne soit plus nécessaire, indiquant que la liste est triée. Bien que facile à comprendre et à mettre en œuvre, Bubble Sort est inefficace pour les grands ensembles de données, ce qui le rend principalement adapté à des fins éducatives et aux petits ensembles de données.

Bubble Sort a une complexité temporelle de O(n²).

// a random array of 20 numbers
const inputArray = [34, 100, 23, 45, 67, 89, 12, 56, 78, 90, 23, 45, 67, 89, 12, 56, 78, 90, 23, 45]

function bubbleSort (input) {
  const n = input.length
  const sortedArray = [...input]

  // loop n times
  for (let i = 0; i < n; i++) {
    // loop through all n-1 pairs
    for (let j = 0; j < n-1; j++) {
      // if a > b, swap; else do nothing
      if (sortedArray[j] > sortedArray[j+1]) {
        const temp = sortedArray[j]
        sortedArray[j] = sortedArray[j+1]
        sortedArray[j+1] = temp
      }
    }
  }

  return sortedArray
}

console.log("Input:", inputArray)
console.log("Ouput:", bubbleSort(inputArray))

Tri de sélection

Selection Sort est un algorithme de tri simple, basé sur une comparaison. Cela fonctionne en divisant la liste en une région triée et une région non triée. Il sélectionne à plusieurs reprises l'élément le plus petit (ou le plus grand) de la région non triée et l'échange avec le premier élément non trié, agrandissant progressivement la région triée. Le tri par sélection n'est pas le plus efficace pour les grands ensembles de données, mais il est facile à comprendre et présente l'avantage de minimiser le nombre d'échanges.

Le tri par sélection a une complexité temporelle de O(n²).

// a random array of 20 numbers
const inputArray = [34, 100, 23, 45, 67, 89, 12, 56, 78, 90, 23, 45, 67, 89, 12, 56, 78, 90, 23, 45]

function selectionSort (input) {
  const n = input.length
  const sortedArray = [...input]

  // loop n times
  for (let i = 0; i < n; i++) {
    // start from i'th position
    let lowestNumberIndex = i
    for (let j = i; j < n-1; j++) {
      // identify lowest number
      if (sortedArray[j] < sortedArray[lowestNumberIndex]) {
        lowestNumberIndex = j
      }
    }

    // swap the lowest number with that in i'th position
    const temp = sortedArray[i]
    sortedArray[i] = sortedArray[lowestNumberIndex]
    sortedArray[lowestNumberIndex] = temp
  }

  return sortedArray
}

console.log("Input:", inputArray)
console.log("Ouput:", selectionSort(inputArray))

Tri par insertion

Le tri par insertion est un algorithme de tri intuitif basé sur des comparaisons qui construit la liste triée finale, un élément à la fois. Cela fonctionne en prenant des éléments de la partie non triée de la liste et en les insérant dans leur position correcte dans la partie triée. Le tri par insertion est efficace pour les petits ensembles de données ou les données presque triées et est souvent utilisé dans des applications pratiques comme alternative plus simple aux algorithmes plus complexes.

Le tri par insertion a une complexité temporelle de O(n²).

function insertionSort (input) {
  const n = input.length
  const sortedArray = [...input]

  // loop n times, starting at index 1
  for (let i = 1; i < n; i++) {
    // start at index 1
    const comparedNumber = sortedArray[i]
    let tempIndex = i

    // compare with previous numbers (right to left)
    for (let j = i-1; j >= 0; j--) {
      // if number in current index is larger than compared number, swap
      if (sortedArray[j] > comparedNumber) {
        sortedArray[tempIndex] = sortedArray[j]
        sortedArray[j] = comparedNumber
        tempIndex = j
      } else {
        // OPTIONAL: else exit
        break
      }
    }
  }

  return sortedArray
}

console.log("Input:", inputArray)
console.log("Ouput:", insertionSort(inputArray))

Conclusion

Bien que les algorithmes de tri de base tels que le tri à bulles, le tri par sélection et le tri par insertion ne soient peut-être pas les plus efficaces pour les grands ensembles de données, ils offrent une excellente base pour comprendre la conception des algorithmes. Si vous avez trouvé cet article utile, j'aimerais connaître votre avis. Déposez un commentaire ci-dessous, partagez vos idées ou posez toutes vos questions – je ferai de mon mieux pour y répondre.

Bon codage !

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!