Einführung in Sortieralgorithmen in JavaScript

Ähnlich wie in den meisten anderen Programmiersprachen können Szenarien auftreten, in denen Sie einige Zahlen in JavaScript in aufsteigender oder absteigender Reihenfolge sortieren müssen. Um dies zu erreichen, können wir viele Algorithmen wie Bubble-Sort, Selection-Sort, Merge-Sort, Quicksort usw. verwenden. Diese Algorithmen unterscheiden sich nicht nur in ihrer Funktionsweise, sondern stellen auch unterschiedliche Anforderungen an den Speicher und die benötigte Zeit Sehen Sie sich einige wichtige Sortieralgorithmen genauer an und erfahren Sie, wie Sie sie in Ihrem JavaScript-Code verwenden können.

Top 6 Sortieralgorithmen in JavaScript

Im Folgenden werden einige Sortieralgorithmen in Javascript anhand von Beispielen erläutert:

1. Blasensortierungsalgorithmus

Die Blasensortierung wird als eines der häufigsten Werkzeuge dieses Handels angesehen und erstellt eine Schleife, die jedes Element im Array mit einem anderen Element vergleicht. Ist der verglichene Artikel kleiner als der vorrätige, tauschen wir die Plätze. Dies geht so lange weiter, bis wir einen Durchgang haben, bei dem kein Element im Array größer ist als das Element, das daneben liegt.

Blasensortierung hat O (n 2 ) Zeitkomplexität und O (n) Raumkomplexität.

Code:

function swap(arr, firstIndex, secondIndex)(
var temp = arr(firstIndex);
arr(firstIndex) = arr(secondIndex);
arr(secondIndex) = temp;
)
function bubbleSortAlgo(arraaytest)(
var len = arraaytest.length,
i, j, stop;
for (i=0; i < len; i++)(
for (j=0, stop=len-i; j < stop; j++)(
if (arraaytest(j) > arraaytest(j+1))(
swap(arraaytest, j, j+1);
)
)
)return arraaytest;
)
console.log(bubbleSortAlgo((3, 6, 2, 5, -75, 4, 1)));

Ausgabe:

2. Auswahl-Sortieralgorithmus

Nachdem wir den Blasensortierungsalgorithmus besprochen haben, wollen wir uns einen bekannten Sortierungsalgorithmus ansehen, der als Auswahlsortierung bezeichnet wird.

Im Gegensatz zur Blasensortierung konzentrieren wir uns darauf, den kleinsten Wert im Array zu finden, um die Sortierung durchzuführen. Hier finden Sie eine schrittweise Aufschlüsselung der Funktionsweise der Auswahlsortierung:

  • Wir gehen davon aus, dass das erste Element im Array das kleinste ist.
  • Wir vergleichen diesen Artikel mit dem nächsten Artikel im Array.
  • Wenn der nächste Artikel kleiner als der aktuelle ist, legen wir den nächsten Artikel als neuen kleinsten Wert fest.
  • Wir wiederholen diese Schritte so oft, bis wir das Ende des Arrays erreicht haben.
  • Wenn wir in dem Array einen Wert finden, der kleiner ist als der Wert, mit dem wir begonnen haben, tauschen wir die Positionen aus.
  • Wir führen die Vergleiche fort und gehen zum nächsten Punkt über. Bis das gesamte Array sortiert ist.

Genau wie der Bubble Sort-Algorithmus hat die Selection-Sortierung die Komplexität von O (n 2 ) Zeit und O (n) Raum.

Code:

function SelectionSortAlgo(array, compare_Function) (
function comp(a, b) (
return a - b;
)
var min = 0;
var index = 0;
var temp = 0;
compare_Function = compare_Function || compare;
for (var i = 0; i < array.length; i += 1) (
index = i;
min = array(i);
for (var j = i + 1; j < array.length; j += 1) (
if (compare_Function(min, array(j)) > 0) (
min = array(j);
index = j;
)
)
temp = array(i);
array(i) = min;
array(index) = temp;
)
return array;
)
console.log(SelectionSortAlgo((9, 15, 2, 44, -1, 36, 1), function(a, b) ( return a - b; )));

Ausgabe:

3. Sortieralgorithmus zusammenführen

Ähnlich wie Bubble Sort und Selection Sort ist Merge Sort einer der beliebtesten Sortieralgorithmen in der Informatik. Sie können es in den meisten Programmiersprachen implementieren und haben eine gute Leistung, ohne dass es zu ressourcenschonend ist.

Merge Sort verwendet die Divide and Conquer-Methode, um ein Array oder eine Liste von Elementen zu sortieren. Der Begriff teilt und besiegt bedeutet, dass wir ein großes Problem in mehrere kleinere Probleme aufteilen und dann diese kleinen Probleme lösen. Sobald die kleineren Probleme gelöst sind, kombinieren wir die Ergebnisse, die zur Lösung des großen Problems führen.

Das Verständnis des Algorithmus ist eigentlich einfach:

  • Wir teilen das gegebene Array in n Arrays auf. Jedes dieser Arrays enthält nur 1 Element.
  • Führen Sie die Arrays zusammen, um ein neues Array zu erstellen.
  • Wiederholen Sie Schritt 2, bis nur noch 1 Array übrig ist. Dies ist das sortierte Array.

Code:

function merge_sort_algo(left, right)
(
var i = 0;
var j = 0;
var result = ();
while (i < left.length || j < right.length) (
if (i === left.length) (
// j is the only index left_part
result.push(right(j));
j++;
)
else if (j === right.length || left(i) <= right(j)) (
result.push(left(i));
i++;
) else (
result.push(right(j));
j++;
)
)
return result;
)
console.log(merge_sort_algo((1, 44, 6), (84, 7, 5)));

Ausgabe:

4. Schnellsortierungsalgorithmus

Quicksort ist eine der effizientesten Methoden zum Sortieren von Elementen in Computersystemen. Um sortieren zu können, arbeitet Quicksort am Divide and Conquer-Algorithmus. In diesem Abschnitt finden Sie ein Pivot-Element im Array, mit dem Sie alle anderen Elementarrays vergleichen können. Anschließend verschieben Sie die Elemente so, dass alle Elemente vor den ausgewählten Pivot-Elementen kleiner und alle Elemente nach dem Pivot-Element größer sind. Sobald wir das getan haben, ist der Schlüssel, es wiederholt zu tun und wir werden unser sortiertes Array haben.

Im Folgenden sind die Schritte aufgeführt, die zum Implementieren des QuickSort-Algorithmus ausgeführt werden können:

  • Wir wählen ein Element des Arrays aus und nennen es "Pivot Point".
  • Wir starten einen Zeiger, der als linker Zeiger bezeichnet wird und sich am ersten Element im Array befindet.
  • In ähnlicher Weise starten wir einen Zeiger, der als rechter Zeiger beim letzten Element im Array bezeichnet wird.
  • Wenn der Wert des Elements am linken Zeiger kleiner als der ausgewählte Drehpunkt ist, bewegen wir den linken Zeiger nach links (addieren +1 dazu) und wiederholen ihn so oft, bis der Wert am linken Zeiger größer als der Wert ist Wert des Drehpunktes oder gleich diesem.
  • Wenn der Wert des Elements am rechten Zeiger in der Liste höher ist als der Wert des Pivot-Elements, modifizieren wir den rechten Zeiger nach links. Wiederholen Sie diesen Vorgang, bis der Wert am rechten Zeiger kleiner (oder gleich) dem Wert von Pivot ist.
  • Wenn der Wert des linken Zeigers kleiner oder gleich dem Wert des rechten Zeigers ist, tauschen Sie die Werte aus.
  • Bewegen Sie den rechten Zeiger um eins nach links, den linken Zeiger um eins nach rechts.
  • Wiederholen, bis sich der linke und der rechte Zeiger treffen.

Code:

function quickSortAlgo(origArray) (
if (origArray.length <= 1) (
return origArray;
) else (
var left = ();
var right = ();
var newArray = ();
var pivot = origArray.pop();
var length = origArray.length;
for (var i = 0; i < length; i++) (
if (origArray(i) <= pivot) (
left.push(origArray(i));
) else (
right.push(origArray(i));
)
)
return newArray.concat(quickSortAlgo(left), pivot, quickSortAlgo(right));
)
)
var myArray = (13, 50, 2, 45, -1, 74, 11 );
var arreySorted = quickSortAlgo(myArray);
console.log(arreySorted);

Ausgabe:

5. Einfügesortierungsalgorithmus

Wenn es um die einfache Implementierung geht, ist Insertion Sort als einer der einfacheren Algorithmen weithin bekannt. Bei der Einfügesortierung werden Elemente des Arrays miteinander verglichen und dann in einer bestimmten Reihenfolge angeordnet. Dies ähnelt dem Anordnen von Karten in einem Stapel. Die Sortierung zum Einfügen von Namen ergibt sich aus dem Vorgang, bei dem ein Element ausgewählt und an der richtigen Stelle eingefügt und anschließend für alle Elemente wiederholt wird.

So funktioniert der Algorithmus:

  • Das erste Element des Arrays gilt als bereits sortiert.
  • Wählen Sie das nächste Element des Arrays.
  • Vergleichen Sie das ausgewählte Element mit allen Elementen im Array.
  • Verschieben Sie jedes Element im Array, das größer als der Wert des ausgewählten Elements ist.
  • Fügen Sie das Element ein
  • Wiederholen Sie die Schritte 2 bis 5, bis das Array sortiert ist.

Code:

function insertion_Sort_algo(arr)
(
for (var i = 1; i < arr.length; i++)
(
if (arr(i) < arr(0))
(
arr.unshift(arr.splice(i, 1)(0));
)
else if (arr(i) > arr(i-1))
(
continue;
)
else (
for (var j = 1; j < i; j++) (
if (arr(i) > arr(j-1) && arr(i) < arr(j))
(
arr.splice(j, 0, arr.splice(i, 1)(0));
)
)
)
)
return arr;
)
console.log(insertion_Sort_algo((44, 20, 26, 54, -9, 41, 16)));

Ausgabe:

6. Heap-Sortieralgorithmus

Die Heap-Sortierung ist eine Methode zum Sortieren von Elementen mithilfe der Datenstruktur „Heap“. Die Methode ist der oben beschriebenen Auswahlsortiertechnik sehr ähnlich. Jetzt wundern Sie sich vielleicht über Heaps und wie sie definiert sind. Bevor Sie sich mit dem Algorithmus befassen, sollten Sie sich zunächst mit Heaps befassen.

Kurz gesagt, ein Heap ist ein Binärbaum mit einigen hinzugefügten Regeln. Eine Regel besagt, dass der Baum in Heap ein vollständiger Binärbaum sein muss, was einfach bedeutet, dass alle Knoten auf der aktuellen Ebene gefüllt werden müssen, bevor ein weiterer hinzugefügt wird. Die nächste Regel für den Heap ist, dass eine definierte Beziehung zwischen untergeordneten und übergeordneten Elementen zu den Elementwerten des Heaps bestehen muss.

In einem Min-Heap muss der Wert eines übergeordneten Elements kleiner sein als der seiner untergeordneten Elemente. Wie Sie sich vorstellen können, muss der Wert eines übergeordneten Elements in einem maximalen Heap größer sein als sein untergeordnetes Element.

Nachdem die Definitionen nicht mehr möglich sind, schauen wir uns an, wie Heapsort funktioniert:

  • Wir bauen zuerst einen Max-Heap auf, der sicherstellt, dass sich das Element mit dem höchsten Wert oben befindet.
  • Wir tauschen das oberste Element gegen das letzte Element des Heapspeichers und entfernen das oberste Element aus dem Heapspeicher und speichern es in einem sortierten Array.
  • Wir wiederholen die Schritte eins und zwei so oft, bis nur noch ein Element im Heap vorhanden ist.

Beachten Sie, dass Heaps in JavaScript nicht nativ unterstützt werden. Daher müssen wir Heaps mithilfe von Arrays implementieren. Die Speicherkomplexität von Heapsort ist O (1), was ausgezeichnet ist, und obwohl es im Vergleich zu Mergesort oder Einfügesort etwas komplizierter ist, was das Verständnis und die Implementierung betrifft, denke ich, ist es aus Gründen der Leistung letztendlich besser, es in zu verwenden große Projekte.

Code:

var arrLength;
function heapRoot(input, i) (
var left = 2 * i + 1;
var right = 2 * i + 2;
var max = i;
if (left input(max)) (
max = left;
)
if (right input(max)) (
max = right;
)
if (max != i) (
swap(input, i, max);
heapRoot(input, max);
)
)
function swap(input, index_A, index_B) (
var temp = input(index_A);
input(index_A) = input(index_B);
input(index_B) = temp;
)
function heapSortAlgo(input) (
arrLength = input.length;
for (var i = Math.floor(arrLength / 2); i >= 0; i -= 1) (
heapRoot(input, i);
)
for (i = input.length - 1; i > 0; i--) (
swap(input, 0, i);
arrLength--;
heapRoot(input, 0);
)
)
var arr = (12, 10, 22, 55, -8, 64, 14);
heapSortAlgo(arr);
console.log(arr);

Ausgabe:

Fazit

Die Sortierung ist ein wichtiger Bestandteil beim Erstellen von Anwendungen und Websites mit JavaScript. Nachdem Sie mit einigen der wichtigsten Algorithmen vertraut sind, sollten Sie sich in JS Development sicherer fühlen.

Eine wichtige Tatsache, die Sie bei der Sortierung berücksichtigen sollten, ist, dass Sie sich in den meisten Fällen nicht zu sehr überlegen müssen, welchen Algorithmus Sie verwenden müssen. Da die Computerhardware so leistungsfähig ist, können moderne Telefon- und Desktop-Prozessoren selbst Hunderte von Elementen in wenigen Millisekunden problemlos sortieren. Es gibt nur Fälle, in denen Sie mit langsamer Hardware nicht weiterkommen oder Situationen, in denen Sie jeden einzelnen Codeabschnitt optimieren müssen, in denen das Ändern von Sortieralgorithmen von Vorteil sein kann.

Empfohlene Artikel

Dies ist eine Anleitung zum Sortieren von Algorithmen in JavaScript. Hier besprechen wir die Top-6-Sortieralgorithmen in Javascript zusammen mit Beispielen und Code-Implementierung. Sie können sich auch die folgenden Artikel ansehen, um mehr zu erfahren -

  1. JavaScript-Compiler
  2. In JavaScript umkehren
  3. Einführung in JavaScript
  4. Quadrate in Java
  5. Schnelle Sortieralgorithmen in Java
  6. Arrays in der Datenstruktur
  7. C ++ Algorithmus | Beispiele für den C ++ - Algorithmus

Kategorie:

Software-Entwicklung