Algorithmen für Webentwickler in einfachen Worten (Teil 2) / Sudo Null IT News

Hallo Freunde!

Wir analysieren weiterhin Algorithmen und Datenstrukturen in JavaScript in der einfachstmöglichen Sprache. Und heute werden wir über den vielleicht berühmtesten Algorithmus sprechen, von dem jeder Entwickler gehört hat – nämlich Bubble Sort (Bubble Sort).

Wenn Sie unseren ersten Artikel (über Suchalgorithmen und Big-O-Notation) noch nicht gelesen haben, finden Sie ihn hier.

Und jetzt kommen wir zum Thema des Artikels.

Sortieralgorithmen

Wie Sie wissen, gibt es je nach Art des zu lösenden Problems viele verschiedene Arten von Algorithmen: Es gibt Algorithmen zum Suchen, Sortieren, Hashen, Datenkomprimieren usw.

Sortieralgorithmen sind Algorithmen zum Sortieren von Elementen in einem Array. Es gibt ein unsortiertes Array, und unsere Aufgabe ist es, es so schnell und effizient wie möglich zu sortieren.

Dieses Problem wurde zu verschiedenen Zeiten auf unterschiedliche Weise angegangen, sodass es mehr als ein Dutzend verschiedener Sortieralgorithmen gibt:

sortieren zusammenführen (Merge Sort);

Sortieren nach Beilagen (Insertion Sort);

Hoares schnelle Sortierung (Quick Sort);

Shell sortieren (Shell Sort);

Sortieren durch Zählen (Counting Sort);

Gnome Sort usw.

Aber der bekannteste Sortieralgorithmus ist natürlich Bubble Sort. Und das, obwohl dieser Algorithmus sehr langsam und ineffizient ist, wenn auch sehr einfach zu implementieren. Darüber hinaus wird es im wirklichen Leben praktisch nicht verwendet.

Es funktioniert so einfach wie möglich: Durchläuft das Array und vergleicht nacheinander benachbarte Elemente und tauscht sie aus, wenn das vorherige größer als das nächste ist. So stehen Elemente mit großen Werten am Ende der Liste, und solche mit kleineren Werten bleiben am Anfang. Das heißt, die Elemente des Arrays “schweben” sozusagen an die gewünschte Position, was dem Verhalten einer Luftblase im Wasser sehr ähnlich ist, daher hat dieser Sortieralgorithmus seinen Namen.

Sie können die Visualisierung von Bubble Sort (und vielen anderen Algorithmen) hier sehen Webseite.

Bubble Sort ist die Grundlage für viele andere Sortierverfahren, wie z. B. Cocktail Sort und Comb Sort.

So funktioniert Bubble Sort

Der Algorithmus besteht aus wiederholten Durchläufen durch das sortierte Array. Bei jedem Durchgang werden die Elemente nacheinander paarweise verglichen, und wenn die Reihenfolge im Paar falsch ist, werden die Elemente permutiert. Durchläufe durch das Array werden N-1 Mal wiederholt oder bis sich beim nächsten Durchlauf herausstellt, dass die Austauschvorgänge nicht mehr benötigt werden, was bedeutet, dass das Array sortiert ist.

Bei jedem Durchlauf des Algorithmus durch die innere Schleife wird das nächstgrößere Element des Arrays an seinen Platz am Ende des Arrays neben das vorher größte Element gestellt („schwebt“ an die gewünschte Position, wie eine Blase im Wasser) , und das kleinste Element verschiebt sich um eine Position an den Anfang des Arrays.

So sieht die einfachste Implementierung dieses Algorithmus in JavaScript aus:

const arr = [-5, 23, 7, 5, 3, -12, -29, 21, 54, 35, 0]; function bubbleSort(arr) { for (let i = 0; i < arr.length; i++) { for (let j = 0; j < arr.length; j++) { if (arr[j] > anf[j + 1]) { let tmp = arr[j]; Arr[j] = anf[j + 1]; Arr[j + 1] = tmp; } } } return arr; } console.log (bubbleSort (arr));

Lassen Sie uns nun diese Implementierung genauer untersuchen.

Detaillierte Analyse des Algorithmus

Wir haben also ein unsortiertes Array. Unsere Aufgabe ist es, es in aufsteigender Reihenfolge zu sortieren, vom kleinsten zum größten.

const arr = [-5, 23, 7, 5, 3, -12, -29, 21, 54, 35, 0];

Wir erstellen die Funktion bubbleSort und übergeben ihr unser unsortiertes arr-Array.

const arr = [-5, 23, 7, 5, 3, -12, -29, 21, 54, 35, 0]; function bubbleSort(arr) { // Implementierung des Algorithmus }

Als nächstes müssen wir zwei for-Schleifen erstellen – äußere und innere. Eines wird in das andere verschachtelt. Mit Hilfe der inneren Schleife werden wir das Array durchlaufen, die Elemente paarweise vergleichen und vertauschen. Somit “schwebt” nach jeder Iteration der inneren Schleife das größte Element an das Ende des Arrays.

Aber nachdem das Array nur einmal durchlaufen und das größte Element gefunden wurde, bleibt das Array immer noch unsortiert.

Und hier brauchen wir eine äußere Schleife. Sie wird benötigt, damit die Permutationsdaten am Ende für alle Elemente des Arrays durchgeführt werden.

Sobald die innere Schleife ihre Ausführung abgeschlossen hat und wir das größte Element erhalten, wiederholen wir diese Operation mit der äußeren for-Schleife und erhalten zwei bereits sortierte Elemente am Ende des Arrays. Ferner wird dieser Vorgang wiederholt, bis das Array vollständig sortiert ist.

Lassen Sie uns also zuerst eine äußere for-Schleife erstellen.

Darin initialisieren wir den Zähler und setzen seinen Anfangswert, der gleich Null ist, da wir das Array ab dem allerersten Element durchlaufen werden.

sei i = 0;

Unsere Schleife wird fortgesetzt, bis sie alle Elemente im Array durchlaufen hat. Wir verwenden arr.length als Endpunkt, der die Anzahl der Elemente im Array zurückgibt. Da das arr-Array bei Index Null beginnt, verwenden wir beim Vergleichen das „<“-Zeichen.

i < Arrangementlänge;

Erhöhen Sie nach jedem Durchlauf der Schleife den Wert der Variablen i um eins (i++).

const arr = [-5, 23, 7, 5, 3, -12, -29, 21, 54, 35, 0]; function bubbleSort(arr) { for (let i = 0; i < arr.length; i++) { } }

Als nächstes müssen wir eine weitere for-Schleife erstellen und sie in die bereits erstellte verschachteln.

Wie Sie sich erinnern, ist die innere Schleife dafür verantwortlich, das größte Element zu finden, und hier tauschen wir die Elemente aus.

Daher erstellen wir eine weitere for-Schleife. Setzen Sie wie beim letzten Mal beim Initialisieren des Zählers seinen Wert auf 0.

Wir werden auch arr.length als Endpunkt verwenden, der die Anzahl der Elemente im Array zurückgibt.

Nach jedem Durchlauf der Schleife erhöhen wir den Wert der Variablen j um eins.

const arr = [-5, 23, 7, 5, 3, -12, -29, 21, 54, 35, 0]; function bubbleSort(arr) { // Äußere for-Schleife (wiederhole die verschachtelte Schleife für jedes Array-Element) for (let i = 0; i < arr.length; i++) { // Innere for-Schleife (finde das größte unsortierte Element) for ( let j = 0; j < arr.length; j++) { // Vergleiche Array-Elemente und vertausche sie } }

Als nächstes erstellen wir mit dem konditionalen if-Konstrukt eine Überprüfung: Wenn das Array-Element am Index j größer ist als das Array-Element am Index j + 1, müssen Sie sie austauschen. Wie Sie sich erinnern, sortieren wir die Elemente im Array in aufsteigender Reihenfolge, sodass die größten Elemente am Ende des Arrays gesammelt werden.

const arr = [-5, 23, 7, 5, 3, -12, -29, 21, 54, 35, 0]; function bubbleSort(arr) { for (let i = 0; i < arr.length; i++) { for (let j = 0; j < arr.length; j++) { // Vergleiche benachbarte Array-Elemente if (arr[j] > anf[j + 1]) { // benachbarte Array-Elemente tauschen } } }

Die Permutation zweier Elemente realisieren wir stellenweise durch die dritte Variable. Dazu erstellen wir eine temporäre Variable tmp (vom englischen temporär – temporär). Darin setzen wir den Wert des Array-Elements auf den Index j (arr[j]). Dadurch wird der Wert von arr gespeichert[j] in der dritten Variablen können wir bereits arr zuweisen[j] Wert des benachbarten Elements arr[j + 1]. Und dann weisen wir arr zu[j + 1] der Wert der tmp-Variablen.

Dadurch werden zwei benachbarte Elemente im Array vertauscht.

function bubbleSort(arr) { for (let i = 0; i < arr.length; i++) { for (let j = 0; j < arr.length; j++) { if (arr[j] > anf[j + 1]) { // Elemente mit dritter Variable tauschen let tmp = arr[j]; Arr[j] = anf[j + 1]; Arr[j + 1] = tmp; } } } }

Jetzt müssen wir nur noch das sortierte Array arr zurückgeben, nachdem wir die innere und äußere for-Schleife ausgeführt haben.

Rufen Sie auch die Funktion bubbleSort auf, übergeben Sie das unsortierte Array arr und geben Sie dann das Ergebnis der Funktionsausführung an die Konsole aus.

function bubbleSort(arr) { for (let i = 0; i < arr.length; i++) { for (let j = 0; j < arr.length; j++) { if (arr[j] > anf[j + 1]) { let tmp = arr[j]; Arr[j] = anf[j + 1]; Arr[j + 1] = tmp; } } } return arr; // Sortiertes Array zurückgeben } console.log(bubbleSort(arr)); // Das Ergebnis an die Konsole ausgeben

Ein paar Worte zur Abschätzung der Komplexität eines Algorithmus.

Im vorangegangenen Artikel haben wir bereits das Thema Abschätzung der Komplexität von Algorithmen angerissen und über die sogenannte Big-O-Notation gesprochen, die den schlimmstmöglichen Fall für die Ausführung eines Algorithmus beschreibt.

Wenn wir sagen, dass Bubble Sort in O(n^2)-Zeit läuft, bedeutet das, dass es definitiv nicht langsamer arbeiten wird. Hier ist n, wie Sie sich erinnern, die Anzahl der Operationen, die der Algorithmus ausführen muss.

In diesem Fall wird Bubble Sort in quadratischer Zeit ausgeführt, da wir zwei verschachtelte for-Schleifen haben, die dieselbe Anzahl von Operationen ausführen.

Mit anderen Worten, im schlimmsten Fall übergeben wir ein absteigend sortiertes Array an die Funktion bubbleSort, während wir es aufsteigend sortieren müssen. In diesem Fall müssen wir es n-mal durchlaufen (wie Sie sich erinnern, ist die äußere Schleife dafür verantwortlich).

Außerdem führen wir bei jeder Iteration der Schleife im schlimmsten Fall n-1 Vergleiche durch, d. h. Wenn wir 4 Elemente im Array haben, müssen wir 3 Vergleiche durchführen.

In diesem Fall kann die Einheit vernachlässigt werden, und bei zwei Schleifen, von denen eine in der anderen verschachtelt ist, beträgt die Anzahl der Operationen n * n oder n^2.

Zusätzlich zum ungünstigsten Ausführungsfall (Big O) ist bei der Bewertung der Geschwindigkeit des Algorithmus die durchschnittliche Ausführungszeit des Algorithmus Big Theta (Big Θ) und die beste Zeit Big Omega (Big Ω).

Im Durchschnitt läuft Bubble Sort in quadratischer Zeit, sodass die erwartete Leistung des Algorithmus Θ(n^2) beträgt.

Im besten Fall übergeben wir ein bereits in aufsteigender Reihenfolge sortiertes Array an die bubbleSort-Funktion, sodass der Algorithmus nur einen Durchlauf durch das Array ausführen muss, der eine konstante Zeit ist.

Aber der Algorithmus muss immer noch n Vergleiche durchführen, also erhalten wir hier 1 * n oder n Operationen. Somit läuft der Bubble-Sort-Algorithmus bestenfalls in linearer Zeit – Ω(n).

Was, wie Sie sich erinnern, immer noch ziemlich langsam ist, also ist Bubble Sort ein extrem ineffizienter Algorithmus.

Um die lineare Ausführungszeit des Algorithmus zu erhalten, müssen wir außerdem die aktuelle Implementierung von Bubble Sort leicht modifizieren.

So wird unser Algorithmus aussehen, der die Chance hat, in linearer Zeit ausgeführt zu werden:

function bubbleSort(arr) {let isSorted; // Füge eine Variable hinzu, die die Frage beantwortet – ist unser Array sortiert oder nicht. for (let i = 0; i anf[j + 1]) { let tmp = arr[j]; Arr[j] = anf[j + 1]; Arr[j + 1] = tmp; istSortiert = falsch; // Da wir Elemente vertauscht haben, ist unser Array nicht sortiert. Setzen Sie den Wert auf false. } } if (isSorted) return arr; // Wenn isSorted === true, dann ist unser Array sortiert und wir geben es sofort zurück. } return arr; }

Auch bei der Bewertung der Komplexität von Algorithmen wird deren Komplexität aus dem Gedächtnis geschätzt, d.h. wie viel Speicher letztendlich vom Algorithmus verwendet wird.

Hier interessiert uns nur der schlimmste Fall, also verwenden wir die Big-O-Notation.

Bubble Sort verbraucht eine konstante Menge an Speicher. Tatsache ist, dass wir ein bereits vorhandenes Array sortieren und keine zusätzlichen Datenstrukturen erstellen, in denen wir theoretisch etwas speichern könnten.

Daher ist die Speicherkomplexität unseres Algorithmus konstant und wird als O (1) geschrieben.

Aber wenn wir zum Beispiel ein leeres Array erstellen und sortierte Elemente hinzufügen, dann wäre die Komplexität eines solchen Algorithmus bereits linear oder O (n), weil die Menge an zusätzlichem Speicher proportional zur Anzahl der Elemente wachsen würde im Eingabedatenarray.

Damit endet der zweite Artikel in unserem Zyklus von Artikeln zu Algorithmen. Vielen Dank für Ihre Aufmerksamkeit und bis bald.

Similar Posts

Leave a Reply

Your email address will not be published.