Sortieralgorithmen für Anfänger in JavaScript: Blase, Auswahl und Einfügesortierung

Wenn Sie Ihre Datensätze beliebig angeordnet haben, werden mehr Zeit und Ressourcen für die Verwaltung und Suche benötigt. Ob Ihre Daten sortiert sind oder nicht, wirkt sich direkt darauf aus, welche Suchmethoden Sie verwenden können, und kann den Unterschied zwischen einer Suche mit einer Million Operationen oder 10 Operationen wie bei der binären Suche bedeuten.

Der Einfachheit halber konzentrieren wir uns nur auf das Sortieren eines Arrays von Zahlen vom kleinsten zum größten, aber diese Algorithmen können leicht für andere Sortierziele geändert werden. Denken Sie daran, dass dies allgemeinere Konzepte und Muster sind und weniger ein „How-to“ zum Sortieren von Daten, da Ihre spezielle Implementierung sehr unterschiedlich sein kann, aber am Ende diesen Mustern konzeptionell ähneln kann.

Hier ist das Übungsarray von 50 Zufallszahlen.

const unsortedArr = ;

Ich werde alles durch die Linse der Big O-Notation betrachten, daher ist es sehr hilfreich zu verstehen, wie die Komplexität im Laufe der Zeit zunimmt.

Bubble Sort

Dies ist die „Hallo Welt“ der Sortiermethoden, nichts Verrücktes, aber es erledigt die Arbeit.

Für jedes Element im Array möchten wir überprüfen, ob das nächste Element größer ist, wenn es dann ihre Indizes im Array vertauscht. Um ein erneutes Vergleichen sortierter Zahlen zu vermeiden, beginnen wir am Ende des Arrays, während ein anderer for loop die vorhergehende Zahl erhält. Auf diese Weise bauen sich am Ende alle größten Werte auf oder „Blasen“.

Bubble Sort Animation

Grafik/Animation dank VisuAlgo.net

Unsere Version funktioniert umgekehrt von der Animation, aber es ist nah genug.

const bubble = arr => { const swap = (list, a, b) => , list] = , list]; for (let i = arr.length; i > 0; i--) { for (let j = 0; j < i - 1; j++) { if (arr > arr) swap(arr, j, j + 1); }; }; return arr;};console.log(bubble(unsortedArr));

Auswahlsortierung

Die Auswahlsortierung funktioniert wie das Gegenteil der Blasensortierung, während die Blasensortierung alle größten Werte bis zum Ende verschiebt.

Jedes Mal, wenn es das Array durchläuft, wählt es den kleinsten Wert aus, wenn es einen niedrigeren Wert findet, wird dieser zum neuen niedrigsten Wert. Wenn die Schleife beendet ist, wird dieses Minimum genommen und auf die Vorderseite des Arrays gelegt, bevor die Schleife erneut gestartet wird. Auf diese Weise wird der niedrigste Wert jeder Iteration auf die Vorderseite gestapelt, bis das gesamte Array sortiert ist.

Auswahl Sortieren Animation

Grafik/Animation dank VisuAlgo.net

const selection = arr => { const swap = (list, a, b) => , list] = , list]; arr.forEach((item, i) => { let min = i; for (let j = i + 1; j < arr.length; j++) { if (arr < arr) min = j; }; swap(arr, i, min); }); return arr;};console.log(selection(unsortedArr));

Einfügesortierung

Mein persönlicher Favorit und der leistungsstärkste der drei, die Einfügesortierung, ähnelt eher der Art und Weise, wie Sie etwas von Hand sortieren würden.

Wir betrachten das Array als zwei Teile, das sortierte und das unsortierte, wobei wir jedes Mal, wenn wir einen neuen Wert finden, zurückschleifen, um seinen Platz in der sortierten Hälfte zu finden. Mit jeder Addition wächst unsere sortierte Gruppe, bis sie das gesamte Array ist.

Einfügung Sortieren Animation

Grafik /Animation dank VisuAlgo.net

const insertion = arr => { arr.forEach((item, i) => { let num = arr; let j; for (j = i - 1; j >= 0 && arr > num; j--) { arr = arr; }; arr = num; }); return arr;};console.log(insertion(unsortedArr));

Vergleich

Ein Problem bei der Verwendung der Big O-Notation zum Vergleichen von Algorithmen besteht darin, dass sie auf dem Worst-Case-Szenario basiert, das für alle Algorithmen gleich sein kann und die falsche Illusion vermittelt, dass sie gleich sind. Während Blasen-, Auswahl- und Einfügesorten alle O (n ^ 2) sind, sagt uns das nicht viel über das Durchschnitts- oder Best-Case-Szenario aus oder darüber, wie sie mit der Datenstruktur variieren.

Die Einfügesortierung gewinnt jedes Mal. Es hat auch den Vorteil, dass nicht das gesamte Array vor dem Start vorhanden sein muss, sodass Sie die Dinge in Echtzeit sortieren können, wenn Daten eingehen.

Denken Sie daran, da Sie nicht entscheiden sollten, welcher Algorithmus „am besten“ ist, bevor Sie überlegen, wie Ihre Daten bereits organisiert sind.

Fazit

Diese drei sind bei weitem nicht die besten Lösungen, um große Datenmengen effizient zu sortieren, aber sie sind einige der intuitivsten, um Ihre Zehen in einen überwältigenden Ozean zu tauchen. 🌊