Code qui génère une liste de 100 entiers avec des nombres aléatoires et effectue un tri rapide. Je l'ai implémenté avec un tri simple et rapide qui n'utilise pas de partition.
Enfin, un code pour mesurer le temps d'exécution est joint.
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