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 vertauscht sie, 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 i Schritt 4: j = 0
Schritt 5: Wenn j Schritt 6: Wenn Array[j] > Array[j 1], gehen Sie zu Schritt 7; sonst gehe zu Schritt 8
Schritt 7: Array[j] und Array[j 1]
vertauschen Schritt 8: j erhöhen; gehe zu Schritt 5
Schritt 9: i erhöhen; gehe zu Schritt 3
Schritt 10: Beenden

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 i Schritt 4: Minimum_value = i; j = i 1
Schritt 5: Wenn j Schritt 6: Wenn Array[Minimalwert] > Array[j], gehe zu Schritt 7; sonst gehe zu Schritt 8
Schritt 7: Minimum_value = j
Schritt 8: j erhöhen; gehe zu Schritt 5
Schritt 9: Array[minimum_value] und array[i]
vertauschen Schritt 10: i erhöhen; gehe 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] 




  
  
  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 i 
Schritt 4: key = arr[i]

Schritt 5: j = i - 1

Schritt 6: Wenn j >= 0 und arr[j] > key, gehe zu Schritt 7; sonst gehe zu Schritt 10

Schritt 7: arr[j 1] = arr[j]

Schritt 8: j um 1 dekrementieren

Schritt 9: Gehe zu Schritt 6

Schritt 10: arr[j 1] = key

Schritt 11: i um 1 erhöhen; gehe zu Schritt 3

Schritt 12: Beenden


  
  
  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 sie dann wieder zusammenführt.


  
  
  Algorithmus


Sortieralgorithmus zusammenführen


Schritt 1: Beginnen

Schritt 2: Wenn Länge(Array) 
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: Beenden

Merge-Funktion


Schritt 1: Beginnen

Schritt 2: sorted_merge = []

Schritt 3: l = 0, r = 0

Schritt 4: Wenn l 
Schritt 5: Wenn left[l] 
Schritt 6: left[l] zu sorted_merge hinzufügen; l um 1 erhöhen

Schritt 7: right[r] zu sorted_merge hinzufügen; r um ​​1 erhöhen

Schritt 8: Gehe zu Schritt 4

Schritt 9: Wenn l 
Schritt 10: left[l] zu sorted_merge hinzufügen; l um 1 erhöhen 

Schritt 11: Gehe zu Schritt 9

Schritt 12: Wenn r 
Schritt 13: right[r] zu sorted_merge hinzufügen; r um ​​1 erhöhen

Schritt 14: Gehe zu Schritt 12

Schritt 15: Sortierte_merge
 zurückgeben
Schritt 16: Beenden


  
  
  Code




def merge(left, right):
    sorted_merge = []
    l = r = 0
    while l 




  
  
  Zeitkomplexität


Bester Fall: O(n log n)

Durchschnittlicher Fall: O(n log n)

Schlimmster Fall: O(n log n) 


  
  
  Schnelle Sortierung


Quick Sort ist ein effizienter In-Place-Sortieralgorithmus, der einen Divide-and-Conquer-Ansatz verwendet. Es wählt ein Pivot-Element aus und unterteilt das Array um den Pivot herum, sodass sich Elemente, die kleiner als der Pivot sind, links davon und Elemente, die größer als der Pivot sind, rechts davon befinden. Dieser Prozess wird dann rekursiv auf die Unterarrays angewendet.


  
  
  Algorithmus


Schnellsortierung


Schritt 1: Beginnen

Schritt 2: Wenn niedrig 
Schritt 3: Pivot_index = Partition(arr, low, high)

Schritt 4: Quicksort(arr, low, Pivot_index - 1)

Schritt 5: Quicksort(arr, Pivot_Index 1, High)

Schritt 6: Beenden 

Partitionsfunktion


Schritt 1: Beginnen

Schritt 2: Pivot = arr[high]

Schritt 3: links = niedrig, rechts = hoch - 1

Schritt 4: Wenn links 
Schritt 5: Wenn arr[left] > Pivot und arr[right] 
Schritt 6: Wenn arr[left] 
Schritt 7: Wenn arr[right] >= Pivot, dekrementieren Sie right

Schritt 8: Gehe zu Schritt 4

Schritt 9: arr[left] und arr[high]
 vertauschen
Schritt 10: Zurück nach links

Schritt 11: Ende 


  
  
  Code




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

def quicksort(arr, low, high):
    if low 




  
  
  Zeitkomplexität


Bester Fall: O(n log n)

Durchschnittlicher Fall: O(n log n)

Schlimmster Fall: O(n^2)