Antwort mit KI erzeugt
Quicksort Algorithmus
Der Quicksort-Algorithmus ist ein rekursiver, auf dem Teile-und-herrsche-Prinzip basierender Algorithmus. Der Prozess kann in die folgenden Schritte unterteilt werden:
1. Wähle ein Pivotelement aus dem Array.
2. Teile das Array in zwei Teillisten auf: Eine Liste der Elemente, die kleiner als das Pivotelement sind, und eine Liste der Elemente, die größer als oder gleich dem Pivotelement sind.
3. Wende rekursiv den Quicksort auf die beiden Teillisten an.
Partitionierung
Die Partitionierungsfunktion organisiert das Array so, dass alle Elemente kleiner als das Pivotelement links vom Pivot stehen und alle Elemente größer oder gleich dem Pivot rechts davon.
Erster ändernder Partition-Aufruf
1. Initiales Array: \(A = [9, 7, 4, 2, 3, 6, 1, 5]\)
2. Wähle ein Pivotelement (häufig wird das letzte Element als Pivot gewählt), hier: 5.
3. Partitioniere das Array mit Pivot 5:
- Initial: \([9, 7, 4, 2, 3, 6, 1, 5]\)
- Nach der Partitionierung: \([4, 2, 3, 1, 5, 9, 6, 7]\)
- Pivot: 5
- Das Array ändert sich und wir erhalten: \([4, 2, 3, 1, 5, 9, 6, 7]\)
Zweiter ändernder Partition-Aufruf
Wir fokussieren uns zuerst auf den linken Teil \( [4, 2, 3, 1]\).
1. Teilliste: \( [4, 2, 3, 1]\)
2. Wähle ein neues Pivotelement, hier: 1.
3. Partitioniere das Array mit Pivot 1:
- Initial: \([4, 2, 3, 1]\)
- Nach der Partitionierung: \([1, 2, 3, 4]\)
- Pivot: 1
- Das Array ändert sich und wir erhalten: \([1, 2, 3, 4]\)
Nach den ersten beiden ändernden Partition-Aufrufen haben wir:
- Erster ändernder Partition-Aufruf:
- Array: \([4, 2, 3, 1, 5, 9, 6, 7]\)
- Pivotelement: 5
- Zweiter ändernder Partition-Aufruf:
- Array: \([1, 2, 3, 4]\)
- Pivotelement: 1
Kompletter Python-Code zum Sortieren des Arrays mittels Quicksort
python
def partition(arr, low, high):
pivot = arr[high] # Pivot ist das letzte Element
i = low - 1 # Index des kleineren Elements
for j in range(low, high):
# Wenn das aktuelle Element kleiner oder gleich dem Pivot ist
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j, arr[i] # Tausche
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def quicksort(arr, low, high):
if low < high:
pi = partition(arr, low, high)
quicksort(arr, low, pi - 1) # Separat sortiere die Elemente vor dem Pivot
quicksort(arr, pi + 1, high) # Separat sortiere die Elemente nach dem Pivot
# Beispiel-Array
A = [9, 7, 4, 2, 3, 6, 1, 5]
# Ausgabe initialen Arrays
print("Initiales Array:", A)
# Quicksort anwenden
quicksort(A, 0, len(A) - 1)
# Ausgabe des sortierten Arrays
print("Sortiertes Array:", A)
Dieser Code implementiert den Quicksort-Algorithmus und zeigt, wie das gegebene Array \(A\) sortiert wird. Die Partitionierungsfunktion wird verwendet, um das Array basierend auf einem Pivotelement zu sortieren und die Teillisten rekursiv zu verarbeiten.
Ergebnisse nach den Partition-Aufrufen:
- Nach dem ersten ändernden Partition-Aufruf:
- Array: \([4, 2, 3, 1, 5, 9, 6, 7]\)
- Pivotelement: 5
- Nach dem zweiten ändernden Partition-Aufruf:
- Array: \([1, 2, 3, 4]\)
- Pivotelement: 1
Das sortierte Array ist am Ende: \([1, 2, 3, 4, 5, 6, 7, 9]\).
