Write code including timeit, to compare algorithms' performance in sorting a list in ascending order for the best case scenario the worst case scenario Remember: each trial should have the same ordered data. Note, there are many strategies to select the partition for QuickSort. Please describe a method you would select to implement partitioning.
Please use python and comment on code so I can better understand. The
Program ScreenShot :-
Fully Working Program (In Text fomat) :-
import random
def quicksort(arr, start, end, pivot_mode='random'):
if start < end:
split = partition(arr, start, end, pivot_mode)
# sort elements before partition and after partition(seperately)
quicksort(arr, start, split-1, pivot_mode)
quicksort(arr, split+1, end, pivot_mode)
return arr
def partition(arr, start, end, pivot_mode):
if pivot_mode == 'first':
pivot = arr[start]
else:
pivot_index = random.randrange(start,end)
pivot = arr[pivot_index]
arr[pivot_index], arr[start] = arr[start], arr[pivot_index]
i = start + 1
for j in range(start+1,end+1):
if arr[j] < pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[start], arr[i-1] = arr[i-1], arr[start]
return i-1
def main():
import timeit
# Example to check that sorting works
arr = [3,8,1,9,12,2,11,7,5,4]
print('Not sorted: %s' % arr)
print('Sorted: %s' % quicksort(arr, 0, len(arr)-1))
# Comparison between quick sort, if first element as a pivot and random pivot
big_arr = [random.random() for _ in range(6000)]
t1 = timeit.Timer(lambda: quicksort(big_arr, 0, len(big_arr)-1, 'first')).timeit(number=1)
big_arr = [random.random() for _ in range(6000)]
t2 = timeit.Timer(lambda: quicksort(big_arr, 0, len(big_arr)-1, 'random')).timeit(number=1)
print('Time to sort 6000 floats with quick sort (first element as pivot): %f seconds' % t1)
print('Time to sort 6000 floats with quick sort (random pivot): %f seconds' % t2)
if (__name__ == '__main__'):
main()
Step by step
Solved in 2 steps with 2 images
