Blasensortierung, Auswahlsortierung, Einfügungssortierung | Datenstrukturen und Algorithmen in JavaScript

Sortieralgorithmen sind das Rückgrat vieler Rechenaufgaben und spielen eine entscheidende Rolle bei der Organisation von Daten für einen effizienten Zugriff und eine effiziente Verarbeitung. Egal, ob Sie ein Anfänger sind, der gerade erst damit beginnt, die Welt der Algorithmen zu erkunden, oder ein erfahrener Entwickler, der sein Wissen auffrischen möchte, das Verständnis dieser grundlegenden Sortiertechniken ist unerlässlich. In diesem Beitrag werden wir einige der grundlegenderen Sortieralgorithmen untersuchen – Blasensortierung, Auswahlsortierung und Einfügungssortierung.

Blasensortierung

Bubble Sort ist ein einfacher, vergleichsbasierter Sortieralgorithmus. Es durchläuft wiederholt eine Liste, vergleicht benachbarte Elemente und tauscht sie aus, wenn sie in der falschen Reihenfolge sind. Dieser Vorgang wird fortgesetzt, bis keine weiteren Swaps mehr erforderlich sind, was anzeigt, dass die Liste sortiert ist. Obwohl Bubble Sort leicht zu verstehen und zu implementieren ist, ist es für große Datensätze ineffizient, sodass es hauptsächlich für Bildungszwecke und kleine Datensätze geeignet ist.

Bubble Sort hat eine zeitliche Komplexität von 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))

Auswahlsortierung

Selection Sort ist ein einfacher, vergleichsbasierter Sortieralgorithmus. Dabei wird die Liste in einen sortierten und einen unsortierten Bereich unterteilt. Es wählt wiederholt das kleinste (oder größte) Element aus dem unsortierten Bereich aus und tauscht es mit dem ersten unsortierten Element aus, wodurch der sortierte Bereich allmählich wächst. Die Auswahlsortierung ist für große Datenmengen nicht besonders effizient, aber leicht zu verstehen und hat den Vorteil, dass die Anzahl der Swaps minimiert wird.

Selection Sort hat eine zeitliche Komplexität von 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))

Einfügungssortierung

Insertion Sort ist ein intuitiver, vergleichsbasierter Sortieralgorithmus, der die endgültige sortierte Liste Element für Element aufbaut. Dabei werden Elemente aus dem unsortierten Teil der Liste übernommen und an der richtigen Position im sortierten Teil eingefügt. Insertion Sort ist effizient für kleine Datensätze oder nahezu sortierte Daten und wird in praktischen Anwendungen häufig als einfachere Alternative zu komplexeren Algorithmen verwendet.

Einfügungssortierung hat eine zeitliche Komplexität von 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))

Zusammenfassung

Auch wenn grundlegende Sortieralgorithmen wie Bubble Sort, Selection Sort und Insertion Sort für große Datensätze möglicherweise nicht die effizientesten sind, bieten sie eine hervorragende Grundlage für das Verständnis des Algorithmusdesigns. Wenn Sie diesen Beitrag hilfreich fanden, würde ich gerne Ihre Gedanken hören. Schreiben Sie unten einen Kommentar, teilen Sie Ihre Erkenntnisse mit oder stellen Sie Fragen – ich werde mein Bestes geben, um sie zu beantworten.

Viel Spaß beim Codieren!

Das obige ist der detaillierte Inhalt vonBlasensortierung, Auswahlsortierung, Einfügungssortierung | Datenstrukturen und Algorithmen in JavaScript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!