quicksort with analysis
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354
import timeit
import random
input = []
def partition(input, start, end):
pivot = start
comparisons = 0
for i in range(start, end):
# Decide whether to swap
if input[i] < input[end]:
input[i], input[pivot] = input[pivot], input[i]
pivot += 1
comparisons += 1
# Swap pivot back where it belongs
input[pivot], input[end] = input[end], input[pivot]
return {'pivot': pivot, 'comparisons': comparisons}
def quicksort(input, start, end):
# Record the comparisons
comparisons = 0
if start < end:
# Pivot contains the time of running the partitioning
pivot = partition(input, start, end)
# Recursion!
partition_1 = quicksort(input, start, pivot['pivot'] - 1)
partition_2 = quicksort(input, pivot['pivot'] + 1, end)
# Sum the comparisons
# Add one comparison for
# "if start < end" up top
comparisons += 1 + pivot['comparisons'] + partition_1['comparisons'] + partition_2['comparisons']
output = {'list': input, 'comparisons': comparisons}
return output
def sort():
result = quicksort(input, 0, len(input) - 1)
print(result['comparisons'], end=", ")
def analysis():
print(len(input), end=", ")
time = timeit.timeit('sort()', 'from __main__ import sort', number = 1)
print(time / (10 ** -6))
if __name__ == "__main__":
input = [random.randrange(1, 101, 1) for _ in range (1000)]
analysis()
Python
INFO