# Den quicksort Algorithmus in Python implementieren, der eine Liste von Zahlen sortiert. 
# Der Algorithmus wählt ein Pivot-Element aus der Liste und teilt die anderen Elemente in drei Listen auf: 
# diejenigen, die kleiner als das Pivot sind, diejenigen, die gleich dem Pivot sind, und diejenigen, die größer als das Pivot sind. 
# Dann wird der Algorithmus rekursiv auf die kleineren und größeren Listen angewendet.
# Diesmal soll das Ganze "inplace" geschehen, d.h. die Liste soll direkt sortiert werden, ohne dass zusätzliche Listen erstellt werden.

array = [7, 2, 9, 4, 1, 8, 3, 6, 5, 0]
def inplace_quicksort(array, low, high):
    if low < high:
        pivot_index = partition(array, low, high)
        inplace_quicksort(array, low, pivot_index - 1)
        inplace_quicksort(array, pivot_index + 1, high)
def partition(array, low, high):
    pivot = array[high]
    i = low - 1
    for j in range(low, high):
        if array[j] <= pivot:
            i += 1
            array[i], array[j] = array[j], array[i]
    array[i + 1], array[high] = array[high], array[i + 1]
    return i + 1

inplace_quicksort(array, 0, len(array) - 1)
print(array)