Code, der eine Liste von 100 Ganzzahlen mit Zufallszahlen generiert und eine schnelle Sortierung durchführt. Ich habe es mit einer einfachen schnellen Sortierung implementiert, die keine Partition verwendet.
Schließlich wird ein Code zum Messen der Ausführungszeit angehängt.
quick_sort.py
from typing import List
import random
import time
def quick_sort(numbers: List[int]) -> List[int]:
numbers_set = set(numbers)
if len(numbers_set) <= 1:
return numbers
p1 = numbers[0]
p2 = 0
for i in range(len(numbers)):
if numbers[i] != p1:
p2 = numbers[i]
break
pivot = p1 if p1 > p2 else p2
left_list = []
right_list = []
for i in range(len(numbers)):
if numbers[i] < pivot:
left_list.append(numbers[i])
else:
right_list.append(numbers[i])
return quick_sort(left_list) + quick_sort(right_list)
if __name__ == "__main__":
nums = [random.randint(0,100) for _ in range(100)]
start = time.time()
quick_sort(nums)
elapsed_time = time.time() - start
print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")
Recommended Posts