Code that generates a list of 100 integers with random numbers and quickly sorts them. I implemented it with a simple quicksort that does not use partitions.
Finally, a code to measure the execution time is attached.
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