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