Auswahlsortierung in JavaScript

In diesem Artikel lernen Sie selection sort und wie es im JavaScript-Quellcode funktioniert. Wir sehen uns ein Beispiel zum Sortieren eines Array-Elements mit dem Selection-Sort-Algorithmus in JavaScript an.

Auswahlsortierung in JavaScript

Selectionsort wird in Programmiersprachen als einfacher Sortieralgorithmus betrachtet. Bei diesem Sortieralgorithmus wird die Liste in zwei Teile geteilt: einen sortierten Teil links und einen unsortierten Teil rechts.

Der sortierte Teil wird in der Anfangsphase leer sein, da wir zu diesem Zeitpunkt nur die unsortierten Daten haben.

Bei der Auswahlsortierung wird das kleinste Element aus der Liste ausgewählt und mit dem Element ganz links ausgetauscht, und dieses kleinste Element wird Teil der sortierten Liste. Dieser Prozess wird fortgesetzt.

Zeitkomplexität der Selektionssortierung

Dieser Algorithmus ist für eine große Datenmenge aufgrund seiner durchschnittlichen und Worst-Case-Komplexität nicht durchführbar. Die Zeitkomplexität dieses Algorithmus ist Ο(n^2), wobei n die Anzahl der Listenelemente ist.

Algorithmus der Auswahlsortierung

Der Auswahlsortieralgorithmus kann in 5 Schritte unterteilt werden:

Im folgenden Beispiel verwenden wir JavaScript, um den Auswahlsortieralgorithmus auszuführen. Wir verwenden eine for-Schleifeniteration für die Listenelemente.

let selectionSorting = function(array) {
  for (var i = 0; i < array.length; i++) {
    // set the min variable to the current iteration of i
    var min = i;
    for (var j = i + 1; j < array.length; j++) {
      if (array[j] < array[min]) {
        min = j;
      }
    }
    var temp = array[i];  // for swapping
    array[i] = array[min];
    array[min] = temp;
  }
  return array;
};
let unsortedArray = [3, 8, 2, 10, 1, 5, 7, 4, 9, 6]

console.log('Unsorted list --> ' + unsortedArray);

let sortedArray = selectionSorting(unsortedArray)

console.log('Sorted list --> ' + sortedArray);

Ausgang:

"Unsorted list --> 3,8,2,10,1,5,7,4,9,6"
"Sorted list --> 1,2,3,4,5,6,7,8,9,10"

Wie oben gezeigt, haben wir eine Funktion vom Typ let selectionSorting() deklariert, in der wir ein Array als Parameter nehmen. Innerhalb dieser Funktion haben wir eine for-Schleife für das übergebene Array verwendet.

Innerhalb des Schleifenkörpers haben wir das erste Element erhalten, da min eine andere Schleife für die restlichen Elemente verwendet hat. Die restlichen Elemente haben wir mit min mit der bedingten Anweisung if() überprüft.

Wenn das min-Element grösser ist als das erste Element der restlichen Daten, brauchen wir nur die min-Variable zu aktualisieren. Dann müssen wir die erste Schleife schließen und den Austausch durchführen, und derselbe Prozess wird fortgesetzt. Wenn das Array sortiert ist, gibt die Funktion das letzte sortierte Array zurück.

Wir haben das unsortierte Array initialisiert, als Argument an die Funktion selectionSort() übergeben und den Rückgabewert in der Variablen sortedArray gespeichert. Schließlich haben wir die Methode console.log() verwendet, um das Ergebnis in Protokollen anzuzeigen.

Kopieren und speichern Sie den obigen Quellcode und verwenden Sie den JavaScript-Compiler, um das Ergebnis anzuzeigen.