Sortieralgorithmen in Python

Was ist Sortieren?

Sortieren bezieht sich auf den Prozess der Anordnung von Daten in einer bestimmten Reihenfolge, typischerweise in aufsteigender oder absteigender Reihenfolge, basierend auf einer linearen Beziehung zwischen den Datenelementen.

Warum brauchen wir eine Sortierung?

Sortieren ist bei der Arbeit mit strukturierten Daten von entscheidender Bedeutung, da es einen effizienten Datenabruf ermöglicht, die Datenanalyse vereinfacht und die allgemeine Datenverwaltung verbessert.

Sortieralgorithmen

Dieser Beitrag behandelt die folgenden Sortieralgorithmen: Blasensortierung, Auswahlsortierung, Einfügungssortierung, Zusammenführungssortierung und Schnellsortierung.

Blasensortierung

Bubble Sort durchläuft wiederholt das Array, vergleicht benachbarte Elemente und tauscht sie aus, wenn sie in der falschen Reihenfolge sind. Dieser Vorgang wird fortgesetzt, bis das Array sortiert ist, wobei größere Elemente bis zum Ende „sprudeln“.

Algorithmus

Schritt 1: Beginnen
Schritt 2: i = 0
Schritt 3: Wenn ich < Länge(Array) – 1, gehe zu Schritt 4; Andernfalls gehen Sie zu Schritt 10
Schritt 4: j = 0
Schritt 5: Wenn j < Länge(Array) – i – 1, gehe zu Schritt 6; Andernfalls gehen Sie zu Schritt 3
Schritt 6: if array[j] > array[j + 1], gehe zu Schritt 7; Andernfalls gehen Sie zu Schritt 8
Schritt 7: Array[j] und array[j + 1] vertauschen
Schritt 8: j erhöhen; Gehen Sie zu Schritt 5
Schritt 9: i erhöhen; Gehen Sie zu Schritt 3
Schritt 10: Ende

Code

def bubble_sort(arr):
    print("Array Before Sorting: ", end='')
    print(arr)
    for i in range(len(arr)):
        for j in range(len(arr)-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

    print("Array After Sorting: ", end='')
    print(arr)

# Main
bubble_sort([7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6])

Zeitkomplexität

Bester Fall: O(n)
Durchschnittlicher Fall: O(n^2)
Schlimmster Fall: O(n^2)

Auswahlsortierung

Selection Sort findet den kleinsten Wert im unsortierten Teil des Arrays und platziert ihn am Anfang dieses Teils.

Algorithmus

Schritt 1: Beginnen
Schritt 2: i = 0
Schritt 3: Wenn ich < Länge(Array) – 1, gehe zu Schritt 4; Andernfalls gehen Sie zu Schritt 10
Schritt 4: Minimum_value = i; j = i + 1
Schritt 5: Wenn j < Länge(Array), gehe zu Schritt 6; Andernfalls gehen Sie zu Schritt 9
Schritt 6: if array[minimum_value] > array[j], gehe zu Schritt 7; Andernfalls gehen Sie zu Schritt 8
Schritt 7: Minimum_value = j
Schritt 8: j erhöhen; Gehen Sie zu Schritt 5
Schritt 9: Array[minimum_value] und array[i]
vertauschen Schritt 10: i erhöhen; Gehen Sie zu Schritt 3
Schritt 11: Ende

Code

def selection_sort(arr):
    print("Array Before Sorting: ", end='')
    print(arr)
    for i in range(len(arr) - 1):
        min_val = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_val]:
                min_val = j

        arr[i], arr[min_val] = arr[min_val], arr[i]

    print("Array After Sorting: ", end='')
    print(arr)

# Main
selection_sort([7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6])

Zeitkomplexität

Bester Fall: O(n^2)
Durchschnittlicher Fall: O(n^2)
Schlimmster Fall: O(n^2)

Einfügungssortierung

Einfügungssortierung erstellt das sortierte Array Element für Element, indem jedes Element aus dem unsortierten Teil entnommen und an der richtigen Position im sortierten Teil eingefügt wird.

Algorithmus

Schritt 1: Beginnen
Schritt 2: i = 1
Schritt 3: Wenn ich < len(arr), gehe zu Schritt 4; Andernfalls gehen Sie zu Schritt 12
Schritt 4: key = arr[i]
Schritt 5: j = i - 1
Schritt 6: Wenn j >= 0 und arr[j] > Schlüssel, gehe zu Schritt 7; Andernfalls gehen Sie zu Schritt 10
Schritt 7: arr[j + 1] = arr[j]
Schritt 8: Dekrementieren Sie j um 1
Schritt 9: Gehen Sie zu Schritt 6
Schritt 10: arr[j + 1] = key
Schritt 11: i um 1 erhöhen; Gehen Sie zu Schritt 3
Schritt 12: Ende

Code

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key

# Main
arr = [7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6]
print("Array Before Sorting:", arr)
insertion_sort(arr)
print("Array After Sorting:", arr)

Zeitkomplexität

Bester Fall: O(n)
Durchschnittlicher Fall: O(n^2)
Schlimmster Fall: O(n^2)

Sortierung zusammenführen

Merge Sort ist ein Divide-and-Conquer-Algorithmus, der das Array rekursiv in kleinere Unterarrays aufteilt, sie sortiert und dann wieder zusammenführt.

Algorithmus

Sortieralgorithmus zusammenführen

Schritt 1: Beginnen
Schritt 2: Wenn Länge(Array) <= 1, Array zurückgeben; Gehen Sie zu Schritt 9
Schritt 3: mid_point = length(array) // 2
Schritt 4: left_half = array[:mid_point]
Schritt 5: right_half = array[mid_point:]
Schritt 6: sorted_left = merge_sort(left_half)
Schritt 7: sorted_right = merge_sort(right_half)
Schritt 8: return merge(sorted_left, sorted_right)
Schritt 9: Ende

Zusammenführungsfunktion

Schritt 1: Beginnen
Schritt 2: sorted_merge = []
Schritt 3: l = 0, r = 0
Schritt 4: Wenn l < len(links) und r < len(rechts), gehe zu Schritt 5; Andernfalls gehen Sie zu Schritt 9
Schritt 5: Wenn left[l] <= right[r], gehe zu Schritt 6; Andernfalls gehen Sie zu Schritt 7
Schritt 6: left[l] zu sorted_merge hinzufügen; Erhöhe l um 1
Schritt 7: right[r] zu sorted_merge hinzufügen; Erhöhe r um 1
Schritt 8: Gehen Sie zu Schritt 4
Schritt 9: Wenn l < len(links), gehe zu Schritt 10; Andernfalls gehen Sie zu Schritt 12
Schritt 10: left[l] zu sorted_merge hinzufügen; l um 1 erhöhen
Schritt 11: Gehen Sie zu Schritt 9
Schritt 12: Wenn r < len(rechts), gehe zu Schritt 13; Andernfalls gehen Sie zu Schritt 15
Schritt 13: right[r] zu sorted_merge hinzufügen; Erhöhe r um 1
Schritt 14: Gehen Sie zu Schritt 12
Schritt 15: Geben Sie sorted_merge
zurück Schritt 16: Ende

Code

def merge(left, right):
    sorted_merge = []
    l = r = 0
    while l < len(left) and r < len(right):
        if left[l] <= right[r]:
            sorted_merge.append(left[l])
            l += 1
        else:
            sorted_merge.append(right[r])
            r += 1

    while l < len(left):
        sorted_merge.append(left[l])
        l += 1

    while r < len(right):
        sorted_merge.append(right[r])
        r += 1

    return sorted_merge

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid_point = len(arr) // 2
    left_half = arr[:mid_point]
    right_half = arr[mid_point:]

    sorted_left = merge_sort(left_half)
    sorted_right = merge_sort(right_half)

    return merge(sorted_left, sorted_right)

# Main
arr = [7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6]
print("Array Before Sorting:", arr)
arr = merge_sort(arr)
print("Array After Sorting:", arr)

Zeitkomplexität

Bester Fall: O(n log n)
Durchschnittlicher Fall: O(n log n)
Schlimmster Fall: O(n log n)

Quick Sort

Quick Sort is an efficient, in-place sorting algorithm that uses a divide-and-conquer approach. It selects a pivot element and partitions the array around the pivot so that elements less than the pivot are on its left and elements greater than the pivot are on its right. This process is then recursively applied to the sub-arrays.

Algorithm

Quick Sort

Step 1: Begin
Step 2: If low < high, goto Step 3; else goto Step 6
Step 3: pivot_index = partition(arr, low, high)
Step 4: quicksort(arr, low, pivot_index - 1)
Step 5: quicksort(arr, pivot_index + 1, high)
Step 6: End

Partition Function

Step 1: Begin
Step 2: pivot = arr[high]
Step 3: left = low, right = high - 1
Step 4: if left <= right goto Step 5, else goto Step 9
Step 5: if arr[left] > pivot and arr[right] < pivot, swap arr[left] and arr[right]
Step 6: if arr[left] <= pivot, increment left
Step 7: if arr[right] >= pivot, decrement right
Step 8: goto Step 4
Step 9: swap arr[left] and arr[high]
Step 10: return left
Step 11: End

Code

def partition(arr, low, high):
    pivot = arr[high]
    left = low
    right = high - 1
    while left <= right:
        if arr[left] > pivot and arr[right] < pivot:
            arr[left], arr[right] = arr[right], arr[left]
        if arr[left] <= pivot:
            left += 1
        if arr[right] >= pivot:
            right -= 1
    arr[left], arr[high] = arr[high], arr[left]
    return left

def quicksort(arr, low, high):
    if low < high:
        pivot_index = partition(arr, low, high)
        quicksort(arr, low, pivot_index - 1)
        quicksort(arr, pivot_index + 1, high)

# Main
arr = [7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6]
print("Array Before Sorting:", arr)
quicksort(arr, 0, len(arr) - 1)
print("Array After Sorting:", arr)

Time Complexity

Best Case : O(n log n)
Average Case : O(n log n)
Worst Case : O(n^2)

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