quicksorts
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165
import random
import timeit
import sys
import resource
def quicksort_first(lst, start, end):
comparisons = 0
if start < end:
pivot = start
lst[end], lst[pivot] = lst[pivot], lst[end]
p, comparisons = partition_first(lst, start, end)
quicksort_rand(lst, start, p - 1)
quicksort_rand(lst, p + 1, end)
return comparisons
def partition_first(lst, start, end):
pivot = start
comparisons = 0
lst[end], lst[pivot] = lst[pivot], lst[end]
pivot_index = start - 1
for index in range(start, end):
comparisons += 1
if lst[index] < lst[end]:
pivot_index += 1
lst[index], lst[pivot_index] = lst[pivot_index], lst[index]
pivot_index += 1
lst[end], lst[pivot_index] = lst[pivot_index], lst[end]
return pivot_index, comparisons
def quicksort_last(lst, start, end):
comparisons = 0
if start < end:
pivot = end
lst[end], lst[pivot] = lst[pivot], lst[end]
p, comparisons = partition_first(lst, start, end)
quicksort_rand(lst, start, p - 1)
quicksort_rand(lst, p + 1, end)
return comparisons
def partition_last(lst, start, end):
pivot = end
comparisons = 0
lst[end], lst[pivot] = lst[pivot], lst[end]
pivot_index = start - 1
for index in range(start, end):
comparisons += 1
if lst[index] < lst[end]:
pivot_index += 1
lst[index], lst[pivot_index] = lst[pivot_index], lst[index]
pivot_index += 1
lst[end], lst[pivot_index] = lst[pivot_index], lst[end]
return pivot_index, comparisons
def quicksort_mid(lst, start, end):
comparisons = 0
if start < end:
pivot = int((start + end) / 2)
lst[end], lst[pivot] = lst[pivot], lst[end]
p, comparisons = partition_first(lst, start, end)
quicksort_rand(lst, start, p - 1)
quicksort_rand(lst, p + 1, end)
return comparisons
def partition_mid(lst, start, end):
pivot = int((start + end) / 2)
comparisons = 0
lst[end], lst[pivot] = lst[pivot], lst[end]
pivot_index = start - 1
for index in range(start, end):
comparisons += 1
if lst[index] < lst[end]:
pivot_index += 1
lst[index], lst[pivot_index] = lst[pivot_index], lst[index]
pivot_index += 1
lst[end], lst[pivot_index] = lst[pivot_index], lst[end]
return pivot_index, comparisons
def quicksort_rand(lst, start, end):
comparisons = 0
if start < end:
pivot = random.randint(start, end)
lst[end], lst[pivot] = lst[pivot], lst[end]
p, comparisons = partition_rand(lst, start, end)
quicksort_rand(lst, start, p - 1)
quicksort_rand(lst, p + 1, end)
return comparisons
def partition_rand(lst, start, end):
pivot = random.randint(start, end)
comparisons = 0
lst[end], lst[pivot] = lst[pivot], lst[end]
pivot_index = start - 1
for index in range(start, end):
comparisons += 1
if lst[index] < lst[end]:
pivot_index += 1
lst[index], lst[pivot_index] = lst[pivot_index], lst[index]
pivot_index += 1
lst[end], lst[pivot_index] = lst[pivot_index], lst[end]
return pivot_index, comparisons
def analysis():
size = 0
elements = [20000, 40000]
def quicksort_rand_analysis():
lst = [random.randrange(0, 1000, 1) for _ in range(size)]
comparisons = quicksort_rand(lst, 0, len(lst) - 1)
print(comparisons, end=", ")
def quicksort_first_analysis():
lst = [random.randrange(0, 1000, 1) for _ in range(size)]
comparisons = quicksort_first(lst, 0, len(lst) - 1)
print(comparisons, end=", ")
def quicksort_last_analysis():
lst = [random.randrange(0, 1000, 1) for _ in range(size)]
comparisons = quicksort_last(lst, 0, len(lst) - 1)
print(comparisons, end=", ")
def quicksort_mid_analysis():
lst = [random.randrange(0, 1000, 1) for _ in range(size)]
comparisons = quicksort_mid(lst, 0, len(lst) - 1)
print(comparisons, end=", ")
for size in elements:
print(size, end=", ")
time = timeit.timeit(quicksort_rand_analysis, number = 1)
print(time / 10**-6)
print(size, end=", ")
time = timeit.timeit(quicksort_first_analysis, number = 1)
print(time / 10**-6)
print(size, end=", ")
time = timeit.timeit(quicksort_last_analysis, number = 1)
print(time / 10**-6)
print(size, end=", ")
time = timeit.timeit(quicksort_mid_analysis, number = 1)
print(time / 10**-6)
if __name__ == "__main__":
analysis()
Python
INFO