Implementierung des Quicksort-Algorithmus
In dieser Übung wirst du den Quicksort-Algorithmus implementieren, um eine Liste von Zahlen zu sortieren.
Im ersten Schritt implementierst du die Funktion partition(), die den Index des Drehpunkts zurückgibt, nachdem du die Liste der Zahlen so verarbeitet hast, dass alle Elemente links vom Drehpunkt kleiner als der Drehpunkt und alle Elemente rechts vom Drehpunkt größer als der Drehpunkt sind.
Im zweiten Schritt wirst du die Funktion quicksort() implementieren, die die Funktion partition() aufruft.
Diese Übung ist Teil des Kurses
Datenstrukturen und Algorithmen in Python
Interaktive Übung
Versuche dich an dieser Übung, indem du diesen Beispielcode vervollständigst.
def partition(my_list, first_index, last_index):
pivot = my_list[first_index]
left_pointer = first_index + 1
right_pointer = last_index
while True:
# Iterate until the value pointed by left_pointer is greater than pivot or left_pointer is greater than last_index
while ____ < ____ and ____ < ____:
left_pointer += 1
while my_list[right_pointer] > pivot and right_pointer >= first_index:
right_pointer -= 1
if left_pointer >= right_pointer:
break
# Swap the values for the elements located at the left_pointer and right_pointer
my_list[left_pointer], my_list[right_pointer] = ____, ____
my_list[first_index], my_list[right_pointer] = my_list[right_pointer], my_list[first_index]
return right_pointer