0 Daumen
205 Aufrufe

Betrachte das folgende Array A.

\( A:=\left[\begin{array}{llllllll} 9 & 7 & 4 & 2 & 3 & 6 & 1 & 5 \end{array}\right] \)

Sortiere das Array A mit Hilfe von Quicksort.

Notiere dabei die Ergebnisse der Partition-Aufrufe, sofern sich das Array in dem jeweiligen Partition-Aufruf ändert.

Gib das Array und das genutzte Pivotelement nach dem ersten ändernden Partition-Aufruf an.

Gib das Array und das genutzte Pivotelement nach dem zweiten ändernden Partition-Aufruf an.

Avatar von

1 Antwort

0 Daumen

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]\).
Avatar von 4,6 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community