Einführung in Insertion Sort in JavaScript
Sortieren ist eines der wichtigen Konzepte, die Programmierer lernen, um ihre Reise in die Informatik zu beginnen, unabhängig von der zu lernenden Programmiersprache. Durch Sortieren können wir die Zieldaten, nach denen wir suchen möchten, schneller und bequemer finden, indem wir sie in aufsteigender oder absteigender Reihenfolge sortieren.
Sortieralgorithmen werden verwendet, um Elemente neu anzuordnen, wobei ein Element eine Zahl oder eine Zeichenfolge sein kann. Es gibt viele Arten von Sortieralgorithmen, die auf ihrer Sortiermethode und der Vorgehensweise zum Sortieren der Elemente basieren. Jede Art hat ihre Vor- und Nachteile.
In diesem Blog konzentrieren wir uns auf Insertion Sort, eine häufig verwendete Sorte, die einfach zu verstehen und zu implementieren ist.
Was ist Einfügesortierung in JavaScript?
Einfügesortierung ist ein einfacher, leicht verständlicher Algorithmus, der am besten mit einer kleinen Datenliste funktioniert, indem jedes Element in der Datenliste nacheinander von links nach rechts sortiert wird. Es wird auch als Vergleichssortierung bezeichnet, bei der der aktuelle Wert mit den anderen Werten in derselben Datenliste verglichen wird, die sortiert wird. Es folgt einem iterativen Ansatz, um jedes Element in der Datenliste in der richtigen Reihenfolge zu platzieren.
Je länger ein Algorithmus zum Sortieren benötigt, desto schlechter wird die Leistung und desto mehr muss ein anderer Algorithmus zum Sortieren der Daten in Betracht gezogen werden. Die Einfügungssortierung hat eine Zeitkomplexität von O (n²) oder wird in quadratischer Zeit ausgeführt, um die Datenliste im ungünstigsten Fall zu sortieren. Dies ist normalerweise nicht sehr effektiv und sollte nicht für große Listen verwendet werden. Normalerweise übertrifft es jedoch fortgeschrittene Algorithmen wie QuickSort oder Mergesort bei kleineren Listen.
Einfügungssortierung ist die meiste Zeit effizienter als andere quadratische Sortieralgorithmen wie Blasensortierung oder Auswahlsortierung. Im besten Fall ist die Zeit O (n) oder linear, was auftritt, wenn das Eingabearray bereits sortiert ist. Im Durchschnitt ist die Laufzeit der Einfügesortierung immer noch quadratisch.
Im folgenden Beispiel haben wir einen einfachen Ansatz, um Daten, die in einer Array-Datenstruktur gespeichert sind, auf hoher Ebene zu sortieren und ihre Sortiermethode zu verwenden, um die Daten zu sortieren, ohne Algorithmen zu implementieren.
Beispiel - Einfügesortierungsalgorithmus
Code:
// Declaring unsorted data and storing it in array data structure
var dataArray = (96, 5, 42, 1, 6, 37, 21) // Function - Insertion Sort Algo.
function insertSort(unsortedData) (
for (let i = 1; i < unsortedData.length; i++) (
let current = unsortedData(i);
let j;
for(j=i-1; j >= 0 && unsortedData(j) > current;j--) (
unsortedData(j + 1) = unsortedData(j) )
unsortedData(j + 1) = current;
)
return unsortedData;
)
// print sorted array
console.log(insertSort(dataArray));
Ausgabe:
Erläuterung: Im Algorithmus haben wir 2 for-Schleifen implementiert, die äußere for-Schleife dient zum Iterieren über die Array-Elemente, und die innere for-Schleife dient zum Sortieren der Array-Elemente in aufsteigender Reihenfolge ihres Werts. Die aktuelle Variable enthält den aktuellen Wert des Arrays und die Variable j ist auf einen Wert kleiner als die aktuelle Indexposition des Arrays gesetzt. Wir prüfen, ob das aktuelle Element (current) kleiner ist als der Array-Wert an der j- ten Position (unsortedData (j) ) und ob es wahr ist, sortieren wir diese Werte.
Iteration 1 - aktuell (96): (96, 5, 42, 1, 6, 37, 21)
Iteration 2 - aktuell (5): (5, 96, 42, 1, 6, 37, 21)
Iteration 3 - aktuell (42): (5, 42, 96, 1, 6, 37, 21)
Iteration 4 - aktuell (1): (1, 5, 42, 96, 6, 37, 21)
Iteration 5 - aktuell (6): (1, 5, 6, 42, 96, 37, 21)
Iteration 6 - aktuell (37): (1, 5, 6, 37, 42, 96, 21)
Iteration 7 - aktuell (21): (1, 5, 6, 21, 37, 42, 96)
Die äußere for-Schleifeniteration beginnt an der ersten Indexposition, da das kleinste Element nach links verschoben werden soll, damit verglichen wird, ob das aktuelle Element kleiner ist als die Elemente auf der linken Seite.
Arten der Sortierung
Die Arten von Algorithmen, die zum Sortieren von Daten verwendet werden, umfassen die folgenden Konzepte oder Ideen in ihrem Ansatz zum Sortieren der Daten:
- Vergleich mit nicht vergleichsbasierten Strategien,
- Iterative versus rekursive Implementierung
- Divide-and-Conquer-Paradigma (dies oder das),
- Zufälliger Ansatz.
Betrachten wir einige Beispiele:
1. Sortierung zusammenführen verwendet einen Divide-and-Conquer-Ansatz, um Elemente in einem Array zu sortieren.
2. Einfügesortierung, Blasensortierung ist eine vergleichsbasierte Sortierung.
Wenn Daten sortiert werden, ist es einfacher, eine optimale Lösung für komplexe Probleme zu finden. beispielsweise,
- Suche nach einem bestimmten Wert,
- Finden des minimalen oder maximalen Wertes,
- Prüfen auf Eindeutigkeit und Löschen von Duplikaten,
- Zählen, wie oft ein bestimmter Wert aufgetreten ist usw.
Fazit
In diesem Artikel haben wir die Definition der Einfügesortierung und ihre zeitliche Komplexität sowie verschiedene andere Sortieralgorithmus-Typen auf der Grundlage ihres Ansatzes untersucht. Durch das Studium verschiedener Sortieralgorithmen können wir herausfinden, welcher Algorithmus unter bestimmten Umständen besser geeignet ist, oder anhand von Anwendungsfällen, mit denen wir die Daten schneller sortieren können.
Empfohlene Artikel
Dies ist eine Anleitung zum Sortieren von Einfügungen in JavaScript. Hier besprechen wir anhand eines Beispiels, was Einfügesortierung in Javascript und seine Typen ist. Sie können sich auch die folgenden Artikel ansehen, um mehr zu erfahren -
- Muster in JavaScript
- Case Statement in JavaScript
- Bedingte Anweisungen in JavaScript
- JavaScript-Objekte
- Verschiedene Arten von Schleifen mit ihren Vorteilen