“””Write a program for analysis of quick sort by using deterministic and randomized variant.”””
import time
import random
arr = [10, 7, 8, 9, 1, 5, 12, 15, 3, 6]
def quick_sort_deterministic(arr):
if len(arr) <= 1:
return arr
pivot = arr[0] #first element as pivot
left = [x for x in arr[1:] if x <= pivot]
right = [x for x in arr[1:] if x > pivot]
return quick_sort_deterministic(left) + [pivot] + quick_sort_deterministic(right) #recursion
def quick_sort_randomized(arr):
if len(arr) <= 1:
return arr
pivot_index = random.randint(0, len(arr)-1)
pivot = arr[pivot_index]
rest = arr[:pivot_index] + arr[pivot_index+1:]
left = [x for x in rest if x <= pivot]
right = [x for x in rest if x > pivot]
return quick_sort_randomized(left) + [pivot] + quick_sort_randomized(right)
start = time.time()
sorted_det = quick_sort_deterministic(arr.copy())
end = time.time()
print(“Deterministic Quick Sort Result:”, sorted_det)
print(f”Time Taken (Deterministic): {end – start:.6f} seconds”)
start = time.time()
sorted_rand = quick_sort_randomized(arr.copy())
end = time.time()
print(“Randomized Quick Sort Result:”, sorted_rand)
print(f”Time Taken (Randomized): {end – start:.6f} seconds”)