25 lines
1.1 KiB
Python
25 lines
1.1 KiB
Python
# 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)
|