Sortieralgorithmen || Python || Datenstrukturen und Algorithmen-Python-Tutorial-php.cn

Sorting Algorithms || Python || Data Structures and Algorithms

Sortieralgorithmen

1. Blasensortierung

Dabei tauschen wir das höhere Element mit seinem Nachbarn aus, bis wir das Ende des Arrays erreichen. Jetzt steht das höchste Element an der letzten Position. Also ändern wir die Grenze und verringern sie gegenüber der letzten um 1. Im schlimmsten Fall müssen wir n-mal iterieren, um das Array zu sortieren.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False

        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # Swap the elements
                swapped = True
        if not swapped:
            break

    return arr

Nach dem Login kopieren

Algorithmus -

Durchlaufen Sie das Array, finden Sie das maximale Element und tauschen Sie es dann gegen das letzte aus.
Vergleichen Sie alle benachbarten Elemente und tauschen Sie sie aus, wenn das größere Element vor dem kleineren Element steht. Machen Sie so weiter, bis Sie das Ende des Arrays erreicht haben.
Behalten Sie ein Flag bei: Wenn kein Element ausgetauscht wird, können wir die Schleife unterbrechen, während das Array sortiert wird.

Zeitkomplexität:

Best Case – Wenn das Array bereits sortiert ist, ist nur eine Iteration erforderlich. Zeitkomplexität – O(n)
Durchschnittlicher Fall – wenn das Array zufällig sortiert ist, dann Zeitkomplexität – O(n2)
Worst Case – wenn das Array in absteigender Reihenfolge vorliegt, sind n*2 Iterationen erforderlich.

Raumkomplexität – O(1), kein zusätzlicher Speicher erforderlich.

Vorteile -

Kein zusätzlicher Speicher erforderlich.
Stabil, da die Elemente ihre relative Reihenfolge beibehalten.

Nachteile -

Zeitliche Komplexität – O(n2), die für große Datensätze sehr hoch ist.

Anwendungen-

Kann nur verwendet werden, wenn der Datensatz sehr klein ist und die Einfachheit aufgrund der hohen zeitlichen Komplexität die Ineffizienz überwiegt.

2. Auswahlsortierung

Dabei suchen wir das kleinste Element im Array und ersetzen es durch das erste Element. Dann erhöhen wir die Grenze um 1 und wiederholen die gleichen Schritte, bis wir das Ende des Arrays erreichen.

def selectionSort(a):
    i = 0
    while i<len(a):

        smallest = min(a[i:])
        index_of_smallest = a.index(smallest)
        a[i],a[index_of_smallest] = a[index_of_smallest],a[i]

        i=i+1
    return a

Nach dem Login kopieren

Algorithmus -

Durchlaufen Sie das Array und finden Sie das minimale Element.
Tausche es mit dem ersten Element und erhöhe den Zeiger um 1.
Wiederholen Sie diesen Vorgang, bis wir das Ende des Arrays erreicht haben.

Zeitkomplexität: Es hat eine Zeitkomplexität von O(n2) in allen drei Fällen: am besten, durchschnittlich und am schlechtesten. Dies liegt daran, dass wir das minimale Element auswählen müssen und jedes Mal austauschen, unabhängig davon, ob das Array bereits sortiert ist oder nicht.

Raumkomplexität – O(1), kein zusätzlicher Speicher erforderlich.

Vorteile -

Kein zusätzlicher Speicher erforderlich.
Es werden weniger Austauschvorgänge durchgeführt als bei der Blasensortierung.

Nachteile -

Zeitkomplexität – O(n2), die für große Datensätze sehr hoch ist.
Nicht stabil, da die relative Reihenfolge gleicher Elemente nicht beibehalten wird.

Anwendungen -

Es kann in Systemen mit begrenztem Speicher verwendet werden, da kein zusätzlicher Speicher erforderlich ist.
Es wird in Systemen verwendet, bei denen die Minimierung der Anzahl von Swaps von entscheidender Bedeutung ist, beispielsweise in Systemen mit langsamen Schreibvorgängen.

3. Einfügungssortierung

Es handelt sich um einen Algorithmus, der ein unsortiertes Element an seiner richtigen Position einfügt, indem es iterativ von der Position des Elements bis zum Anfang des Arrays rückwärts prüft.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False

        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # Swap the elements
                swapped = True
        if not swapped:
            break

    return arr

Nach dem Login kopieren

Algorithmus -

Beginnen Sie mit dem zweiten Element des Arrays und vergleichen Sie es mit dem ersten Element. Wenn das aktuelle Element kleiner als das erste Element ist, tauschen Sie sie aus.
Erhöhen Sie nun den Zeiger und machen Sie dies für das dritte Element: Vergleichen Sie es mit dem zweiten und ersten Element.
Wiederholen Sie den gleichen Vorgang für die restlichen Elemente, vergleichen Sie sie mit allen vorherigen Elementen und fügen Sie sie an der geeigneten Position ein.

Zeitkomplexität:

- Bester Fall - Wenn das Array bereits sortiert ist, ist nur eine Iteration erforderlich. Die Zeitkomplexität ist O(n)
- Durchschnittlicher Fall –Wenn das Array zufällig sortiert ist, beträgt die Zeitkomplexität O(n2)
- Schlimmster Fall -Wenn das Array in absteigender Reihenfolge vorliegt, sind n2 Iterationen erforderlich.

Raumkomplexität – O(1), kein zusätzlicher Speicher erforderlich.

Vorteile -

Kein zusätzlicher Speicher erforderlich.
Stabil, da die Elemente ihre relative Reihenfolge beibehalten.

Nachteile -

Zeitkomplexität – O(n2), die für große Datensätze sehr hoch ist.
Nicht stabil, da die relative Reihenfolge gleicher Elemente nicht beibehalten wird.

Anwendungen-

Es ist effizient für Szenarien, in denen Elemente in Echtzeit eintreffen und sortiert werden müssen, wie zum Beispiel Live-Datenströme.

4. Sortieren zusammenführen

Merge Sort ist ein Algorithmus, der dem Divide-and-Conquer-Ansatz folgt. Es besteht aus zwei Hauptschritten: erstens das rekursive Teilen des Arrays und zweitens das Zusammenführen der geteilten Arrays in sortierter Reihenfolge.

def selectionSort(a):
    i = 0
    while i<len(a):

        smallest = min(a[i:])
        index_of_smallest = a.index(smallest)
        a[i],a[index_of_smallest] = a[index_of_smallest],a[i]

        i=i+1
    return a

Nach dem Login kopieren

Algorithmus -

Teilen Sie das Array in zwei Hälften, indem Sie den Mittelpunkt berechnen.
Fahren Sie mit der Division fort, bis die Länge jedes Unterarrays 1 beträgt.
Rufen Sie die Zusammenführungsfunktion für beide Hälften auf: die linke Hälfte und die rechte Hälfte.
Verwenden Sie drei Hinweise für den Zusammenführungsprozess:

Der erste Zeiger für die linke Hälfte des Arrays.
Der zweite Zeiger für die rechte Hälfte des Arrays.
Der dritte Zeiger für das sortierte Array.

Durchlaufen Sie beide Hälften und vergleichen Sie ihre Elemente. Fügen Sie das kleinere Element in das sortierte Array ein und erhöhen Sie den entsprechenden Zeiger um 1.
Wiederholen Sie diesen Vorgang rekursiv, bis das gesamte Array sortiert ist.

Zeitkomplexität: Merge Sort hat in allen drei Fällen eine Zeitkomplexität von O(n log n): am besten, durchschnittlich und schlechtesten. Dies liegt daran, dass unabhängig davon, ob das Array bereits sortiert ist oder nicht, für jede Unterteilung und Zusammenführung dieselben Schritte ausgeführt werden.

O( log n ) – Die Array-Größe wird bei jedem Schritt während der Teilungsphase halbiert.

O(n) – Während des Zusammenführungsprozesses müssen wir alle Elemente einmal durchlaufen.

Die Gesamtzeitkomplexität beträgt also O (n) * O (log n) = O (n log n)

Raumkomplexität – O(n), Während des Zusammenführungsprozesses ist zusätzlicher Speicher erforderlich, um die temporären Arrays zu speichern.

Vorteile -

Stabil, da die Elemente ihre relative Reihenfolge beibehalten.
Die zeitliche Komplexität beträgt O (n log n), selbst für große Datensätze.
Geeignet für die parallele Verarbeitung, da Unterarrays unabhängig voneinander zusammengeführt werden.

Nachteile -

Zeitliche Komplexität – O(n2), die für große Datensätze sehr hoch ist.
Für den Zusammenführungsvorgang ist zusätzlicher Speicher erforderlich.
Nicht vorhanden, da zusätzlicher Speicher erforderlich ist.
Langsamer als QuickSort im Allgemeinen für die meisten Datensätze.

Anwendungen -

Es wird in Situationen verwendet, in denen die Daten zu groß sind, um in den Speicher zu passen, z. B. beim Zusammenführen großer Dateien.
Es wird zum Sortieren verknüpfter Listen verwendet, da kein Direktzugriff erforderlich ist.

5. Schnellsortierung

Quick Sort ist ein Algorithmus, der dem Divide-and-Conquer-Ansatz folgt. Wir wählen ein Pivot-Element aus und unterteilen das Array um das Pivot-Element, nachdem wir das Pivot an der richtigen sortierten Position platziert haben.

Der erste Schritt besteht darin, das Pivot-Element auszuwählen und dann das Array um den Pivot zu verteilen. Alle Elemente, die kleiner als der Drehpunkt sind, befinden sich links und alle Elemente, die größer als der Drehpunkt sind, rechts davon. Der Drehpunkt befindet sich dann in der korrekten Sortierposition. Rekursiv wird derselbe Prozess angewendet, indem das Array in zwei Hälften geteilt wird: Die erste Hälfte enthält die Elemente vor dem Pivot und die zweite Hälfte enthält die Elemente nach dem Pivot. Dieser Vorgang wird wiederholt, bis die Länge jedes Unterarrays 1 erreicht.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False

        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # Swap the elements
                swapped = True
        if not swapped:
            break

    return arr

Nach dem Login kopieren

Algorithmus -

Teilen Sie das Array in zwei Hälften, indem Sie den Mittelpunkt berechnen.
Wählen Sie einen Drehpunkt; Als Drehpunkt kann jedes beliebige Element gewählt werden.
Durchlaufen Sie das Array und vergleichen Sie jedes Element mit dem Pivot.
Platzieren Sie alle Elemente, die kleiner als der Drehpunkt sind, links und alle Elemente, die größer als der Drehpunkt sind, rechts.
Vertauschen Sie den Drehpunkt mit dem linken Zeiger, damit sich der Drehpunkt an der korrekten sortierten Position befindet.
Wiederholen Sie diesen Vorgang rekursiv, bis die Länge der Partition größer als 1 ist.

Zeitkomplexität:

1. Bester Fall – Zeitkomplexität – O(n log n), wenn der Pivot das Array in zwei gleiche Hälften teilt.
2. Durchschnittlicher Fall – Zeitkomplexität – O(n log n), wenn der Pivot das Array in zwei gleiche Hälften teilt. Aber nicht unbedingt gleich.
3. Schlimmster Fall –Zeitliche Komplexität – O(n2), wenn –

Das kleinste Element wird als Drehpunkt in einem bereits sortierten Array ausgewählt.
Das größte Element wird als Drehpunkt in einem in absteigender Reihenfolge sortierten Array ausgewählt.

O( log n ) – Die Array-Größe wird bei jedem Schritt während der Teilungsphase halbiert.

O(n) – Während der Reihenfolge der Elemente.

Die Gesamtzeitkomplexität beträgt also O (n) * O (log n) = O (n log n)

Weltraumkomplexität:

Bester und durchschnittlicher Fall – O( log n) – für den rekursiven Stapel.
Worst Case – O(n) – für den rekursiven Stapel.

Vorteile -

Effizient für große Datensätze, es sei denn, der Pivot ist schlecht gewählt.
Es ist Cache-freundlich, da wir zum Sortieren auf demselben Array arbeiten und keine Daten in ein Hilfsarray kopieren.
Einer der schnellsten Allzweckalgorithmen für große Datenmengen, wenn keine Stabilität erforderlich ist.

Nachteile -

Zeitliche Komplexität – O(n2), die für große Datensätze sehr hoch ist.
Nicht stabil, da die relative Reihenfolge gleicher Elemente nicht beibehalten wird.

Anwendungen -

Es wird in Programmierbibliotheken und Frameworks verwendet. Beispielsweise basieren die Funktion sorted() von Python und Array.sort() von Java auf der Schnellsortierung.
Es wird zur Optimierung von Datenbankabfragen verwendet, indem Zeilen während der Abfrageausführung effizient sortiert werden.
Aufgrund seiner Cache-freundlichen Eigenschaften eignet es sich gut für die In-Memory-Sortierung großer Datensätze.

6.Heap-Sortierung

Heap Sort ist ein vergleichsbasierter Sortieralgorithmus. Es ist eine Erweiterung von Selection Sort. Bei der Heap-Sortierung erstellen wir einen binären Heap und tauschen das maximale oder minimale Element mit dem letzten Element aus. Dann reduzieren wir die Heap-Größe um 1. Dieser Vorgang wird wiederholt, bis die Länge des Heaps größer als 1 ist.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False

        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # Swap the elements
                swapped = True
        if not swapped:
            break

    return arr

Nach dem Login kopieren

Algorithmus -

Erstellen Sie mit dem Heapify-Prozess einen maximalen Heap. Heapify ist eine Methode zur Aufrechterhaltung der Heap-Eigenschaft einer binären Heap-Datenstruktur.
Wenn das Array die Größe n hat, enthält es n//2 übergeordnete Knoten.
Für einen Elternteil mit Index i:

a.Sein linkes Kind befindet sich am Index 2i 1

b. Sein rechtes Kind befindet sich am Index 2i 2

Iterieren Sie alle Teilbäume mit Eltern vom Index n//2 bis 0 und rufen Sie die Heapify-Funktion für sie auf.
Jetzt wird das Array zu einem maximalen Heap, wobei das größte Element am Index 0 liegt.
Tauschen Sie das erste Element mit dem letzten Element des Heaps und verringern Sie die Größe des Heaps um 1.
Wiederholen Sie diesen Vorgang, bis die Länge des Heaps größer als 1 ist

Zeitkomplexität: Heap Sort hat in allen drei Fällen eine Zeitkomplexität von O(n log n): am besten, im Durchschnitt und am schlechtesten. Dies liegt daran, dass unabhängig davon, ob das Array bereits sortiert ist oder nicht, jedes Mal, wenn ein Max-Heap erstellt und ein Element ausgetauscht wird, dieselben Schritte ausgeführt werden.

O( log n ) – Um maximalen Heap zu erstellen

O(n) – Da der maximale Heap erstellt und ein Element n-mal ausgetauscht wird.

Die Gesamtzeitkomplexität beträgt also O (n) * O (log n) = O (n log n)

Raumkomplexität: Für alle Fälle – O( log n) – für den rekursiven Stapel.

Vorteile -

Die zeitliche Komplexität beträgt O (n log n), selbst für große Datensätze.
Die Speichernutzung ist nahezu konstant.

Nachteile -

Nicht stabil, da die relative Reihenfolge gleicher Elemente nicht beibehalten wird.
Im Vergleich zur Zusammenführungssortierung sind viele Swaps erforderlich.

Anwendungen -

Es ist nützlich für die Implementierung von Prioritätswarteschlangen, bei denen häufig das maximale oder minimale Element extrahiert wird.
Nützlich in Systemen, in denen eine Sortierung vor Ort erforderlich ist und die Speichernutzung von entscheidender Bedeutung ist.
Es wird in Szenarien verwendet, in denen Rankings erforderlich sind.

7. Zählsortierung und Radixsortierung

Counting Sort ist ein nicht vergleichsbasierter Sortieralgorithmus. Dies ist besonders effizient, wenn der Bereich der Eingabewerte im Vergleich zur Anzahl der zu sortierenden Elemente klein ist. Die Grundidee von Counting Sort besteht darin, die Häufigkeit jedes einzelnen Elements im Eingabearray zu zählen und diese Informationen zu verwenden, um die Elemente an ihren korrekten sortierten Positionen zu platzieren.

Radix Sort verwendet Counting Sort als Unterroutine. Es wendet die Zählsortierung auf jede Ziffernstelle einer Zahl an und sortiert wiederholt, bis alle Ziffern der größten Zahl im Array verarbeitet sind.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False

        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # Swap the elements
                swapped = True
        if not swapped:
            break

    return arr

Nach dem Login kopieren

def selectionSort(a):
    i = 0
    while i<len(a):

        smallest = min(a[i:])
        index_of_smallest = a.index(smallest)
        a[i],a[index_of_smallest] = a[index_of_smallest],a[i]

        i=i+1
    return a

Nach dem Login kopieren

Algorithmus -

Finden Sie die maximale Zahl im Array und bestimmen Sie die Anzahl der Ziffern (d) darin. Wenn die Länge der Zahl d beträgt, wird Counting Sort d-mal im Array aufgerufen.
Anrufzählsortierung für jede Ziffernstelle im Array, beginnend mit der Einerstelle, dann der Zehnerstelle usw.
In Zählsortierung:

Erstellen Sie zunächst ein Index-Array und ordnen Sie die Elemente basierend auf ihren Werten zu. Wenn eine Ziffer beispielsweise 4 ist, erhöhen Sie den Wert am 4. Index des Index-Arrays.
Erstellen Sie ein Präfix-Summen-Array aus dem Index-Array.
Erstellen Sie mit dem Präfix-Summenarray ein neues sortiertes Array, das der Länge des Eingabearrays entspricht
Wenn das Präfix-Summen-Array beispielsweise an Index 1 den Wert 2 hat, platzieren Sie den Wert 1 an Position 2 im sortierten Array und dekrementieren den Wert im Präfix-Summen-Array um 1

Zeitkomplexität:

Counting Sort hat eine zeitliche Komplexität von O(n k), wobei n die Anzahl der zu sortierenden Elemente und k der Wertebereich (Größe des Indexarrays) ist. Diese Komplexität gilt für alle drei Fälle: am besten, durchschnittlich und schlechtesten.

Das liegt daran, dass unabhängig davon, ob das Array bereits sortiert ist oder nicht, jedes Mal die gleichen Schritte ausgeführt werden.

Die Zeitkomplexität von Radix Sort erhöht sich um den Faktor d, wobei d die Anzahl der Ziffern in der größten Zahl im Array ist. Die zeitliche Komplexität beträgt O (d * (n k))

Die Gesamtzeitkomplexität beträgt also O (d) * O(n k) = O (d * (n k))

Raumkomplexität: Für alle Fälle – O(n k), wobei n die Länge des Eingabearrays und k der Wertebereich im Indexarray ist.

Vorteile -

Stabil, da die Elemente ihre relative Reihenfolge beibehalten.
Zählsortierung ist im Allgemeinen schneller als alle vergleichsbasierten Sortieralgorithmen, wie z. B. Zusammenführungssortierung und Schnellsortierung, wenn der Eingabebereich in der Größenordnung der Anzahl der Eingaben liegt.

Nachteile -

Die Zählsortierung funktioniert nicht bei Dezimalwerten.
Die Zählsortierung ist ineffizient, wenn der Bereich der zu sortierenden Werte sehr groß ist.
Nicht vorhandener Sortieralgorithmus, da er zusätzlichen Platz O(O(n m)) benötigt.

Anwendungen -

Es wird in Anwendungen wie dem Zählen von Zeichenvorkommen in Zeichenfolgen verwendet.
Nützlich zum Sortieren von Ganzzahlen mit einem großen Wertebereich, wie z. B. IDs oder Telefonnummern.
Effizient zum Sortieren von Daten mit mehreren Schlüsseln, wie Datumsangaben oder Tupeln.

Das obige ist der detaillierte Inhalt vonSortieralgorithmen || Python || Datenstrukturen und Algorithmen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!