Algorithmen in JavaScript für Anfänger

Algorithmen sind die Grundbausteine der Programmierung. Sie helfen, Probleme effizient und schnell zu lösen. In diesem Artikel werden wir uns einige beliebte Algorithmen in JavaScript ansehen und sehen, wie sie in der Praxis funktionieren. Wir werden Sortieren, Suchen und grundlegende Prinzipien der Arbeit mit Daten besprechen.

Was sind Algorithmen?

Ein Algorithmus ist eine Abfolge von Schritten, die ausgeführt werden, um ein bestimmtes Ziel zu erreichen oder ein Problem zu lösen. In der Programmierung verwenden wir Algorithmen, um Arrays zu sortieren, Werte zu suchen, Daten zu verwalten und vieles mehr. Je besser der Algorithmus ist, desto schneller und effizienter funktioniert er.

Beginnen wir mit den beliebtesten Algorithmen, die häufig in JavaScript verwendet werden.

Sortieralgorithmus: Blasensortierung (Bubble Sort)

Bubble Sort ist einer der einfachsten Sortieralgorithmen, der ein Array durchläuft, benachbarte Elemente vergleicht und sie austauscht, wenn sie in der falschen Reihenfolge sind. Dieser Vorgang wird wiederholt, bis das Array sortiert ist.

Beispiel für JavaScript-Code:

function bubbleSort(arr) {
    let swapped;
    do {
        swapped = false;
        for (let i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                // Wir tauschen Elemente aus
                [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
                swapped = true;
            }
        }
    } while (swapped);
    return arr;
}

// Anwendungsbeispiel
const array = [5, 3, 8, 4, 2];
console.log(bubbleSort(array)); // [2, 3, 4, 5, 8]

Wie funktioniert die Blasensortierung? Wir durchlaufen das Array und vergleichen die Elementpaare. Wenn das aktuelle Element größer als das nächste ist, tauschen wir sie aus. Nach einem Durchlauf „schwimmt“ das größte Element zum Ende des Arrays (daher der Name „Bubble Sort“). Der Vorgang wird wiederholt, bis das gesamte Array sortiert ist.

Suchalgorithmus: Binäre Suche

Die binäre Suche ist ein effizienter Suchalgorithmus, mit dem ein Element in einem sortierten Array gefunden werden kann. Im Gegensatz zur linearen Suche, bei der jedes Element nacheinander überprüft wird, teilt die binäre Suche das Array in zwei Teile und vergleicht den gesuchten Wert mit der Mitte. Dies reduziert die Anzahl der Überprüfungen erheblich.

Beispiel für JavaScript-Code:

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        if (arr[mid] === target) {
            return mid; // Wir haben das Element gefunden, geben seinen Index zurück
        }
        
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1; // Element nicht gefunden
}

// Anwendungsbeispiel
const sortedArray = [1, 2, 3, 4, 5, 6, 7, 8, 9];
console.log(binarySearch(sortedArray, 4)); // 3

Wie funktioniert die binäre Suche? Wir finden die Mitte des Arrays und vergleichen sie mit dem Zielelement. Wenn das Element kleiner ist, suchen wir in der linken Hälfte des Arrays weiter, wenn es größer ist, in der rechten Hälfte. Dieser Vorgang wird wiederholt, bis wir das Element gefunden haben oder sicher sind, dass es nicht im Array vorhanden ist.

Beachten Sie, dass die binäre Suche nur mit sortierten Arrays funktioniert. Wenn das Array nicht sortiert ist, müssen Sie es zuerst sortieren.

Rekursion: Algorithmus zur Berechnung der Fakultät

Rekursion - Dies ist der Fall, wenn eine Funktion sich selbst aufruft, um eine Unteraufgabe zu lösen. Ein klassisches Beispiel für Rekursion ist die Berechnung der Fakultät einer Zahl. Die Fakultät einer Zahl n ist das Produkt aller Zahlen von 1 bis n.

Beispiel für JavaScript-Code:

function factorial(n) {
    if (n === 0) {
        return 1; // Die Fakultät von 0 ist 1
    }
    return n * factorial(n - 1); // Rekursiver Funktionsaufruf
}

// Anwendungsbeispiel
console.log(factorial(5)); // 120

Wie funktioniert Rekursion in der Fakultät? Wenn factorial(5) aufgerufen wird, ruft die Funktion sich selbst mit dem Argument 5 - 1 auf, dann 4 - 1 und so weiter, bis sie 0 erreicht. Danach wird das Ergebnis entlang der Aufrufkette zurückgegeben und wir erhalten das Produkt aller Zahlen von 1 bis 5.

Sortieralgorithmus: Schnelle Sortierung (Quick Sort)

Quick Sort - Dies ist einer der beliebtesten Sortieralgorithmen, der in den meisten Fällen viel schneller funktioniert als die Blasensortierung. Er verwendet das Prinzip "Teile und Herrsche", indem er ein Bezugselement auswählt und das Array in zwei Teile teilt - weniger Bezugselement und mehr Bezugselement. Dann werden beide Teile rekursiv sortiert.

Beispiel für JavaScript-Code:

function quickSort(arr) {
    if (arr.length <= 1) {
        return arr; // Basisfall: Ein Array aus 1 Element ist bereits sortiert
    }

    const pivot = arr[arr.length - 1]; // Stützelement
    const left = [];
    const right = [];

    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]); // Elemente, die kleiner als das Referenzelement sind, werden in das linke Array verschoben
        } else {
            right.push(arr[i]); // Elemente, die größer als das Referenzelement sind, werden in das rechte Array verschoben
        }
    }

    return [...quickSort(left), pivot, ...quickSort(right)]; // Rekursiver Aufruf für jeden Teil
}

// Anwendungsbeispiel
const arrayToSort = [5, 3, 8, 4, 2];
console.log(quickSort(arrayToSort)); // [2, 3, 4, 5, 8]

Wie funktioniert die schnelle Sortierung? Wir wählen ein Bezugselement (in diesem Fall das letzte Element des Arrays) und teilen das Array dann in zwei Teile auf - Elemente, die kleiner als das Bezugselement sind, und Elemente, die größer als das Bezugselement sind. Diese Teile werden rekursiv sortiert, bis die Arrays sortiert sind.

Befund

Algorithmen sind ein wichtiger Teil der Programmierung, und wenn Sie verstehen, wie sie funktionieren, können Sie effizienteren Code schreiben. In diesem Artikel haben wir uns einige beliebte Algorithmen in JavaScript angesehen, darunter Sortieren, Suchen und Rekursion. Jeder dieser Algorithmen kann in der täglichen Entwicklung verwendet werden, um Probleme unterschiedlicher Komplexität zu lösen.

Versuchen Sie, diese Algorithmen in Ihren Projekten anzuwenden! Die Verbesserung Ihrer Fähigkeiten im Umgang mit Algorithmen macht Sie zu einem fortgeschritteneren Entwickler und hilft Ihnen, optimierten und sauberen Code zu schreiben.