# Ich möchte ein Quicksort-Algorithmus 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.
import random
import time
n = 50000
Array = [random.randint(1, n) for _ in range(1, n)]

print(Array)
def quicksort(Array):
    Pivot = Array[0]
    links = []
    rechts = []
    gleich = []
    for i in range(len(Array)):
        if i < Pivot:
            links.append(i)
        elif i > Pivot:
            rechts.append(i)
        else:
            gleich.append(i)
    if len(links) > 1:
        quicksort(links)
    if len(rechts) > 1:
        quicksort(rechts)
    return links + gleich + rechts
        


start = time.time()
print(quicksort(Array))
end = time.time()
verstrichene_zeit = end - start
print(f'Ausführungszeit: {verstrichene_zeit} Sekunden')