Question

In Python please.

Construct a large file of data in random order where the key is a 13-digit number.
Then sort in two different ways. Use a Quick sort and then use a radix sort of some kind. Code both sorts in the same language and run experiments to see at what size of data does the radix run faster than the Quick sort.

Answer 1

"""
The time compexity of quicksort is nlogn
where as time complesitiy of radixsort is n+k
k->range of value max-min
n->size if array
i tested for different range value of k but quick sort always
out performed the radix sort
as k the value approachs large value it will become impossible for it to
outperform the quick sort
"""
import time
import random

def countingSort(arr, exp1):
n = len(arr)
output = [0] * (n)
count = [0] * (10)

for i in range(0, n):
index = int(arr[i]/exp1)
count[ index%10 ] += 1
  
for i in range(1,10):
count[i] += count[i-1]
  
i = n-1
while i>=0:
index = int(arr[i]/exp1)
output[ count[ (index)%10 ] - 1] = arr[i]
count[ (index)%10 ] -= 1
i -= 1
  
i = 0
for i in range(0,len(arr)):
arr[i] = output[i]

def radixSort(arr):
max1 = max(arr)
exp = 1
while max1/exp > 0:
countingSort(arr,exp)
exp *= 10

def partition(arr,low,high):
i = ( low-1 )
pivot = arr[high]
for j in range(low , high):
if(arr[j] <= pivot):
i = i+1
arr[i],arr[j] = arr[j],arr[i]
arr[i+1],arr[high] = arr[high],arr[i+1]
return ( i+1 )

def quickSort(arr,low,high):
if low < high:
pi = partition(arr,low,high)
quickSort(arr, low, pi-1)
quickSort(arr, pi+1, high)
  
limit =5
start = 1
end = 2
while(True):
arr = [random.randint(start,end) for _ in range(limit)]
t1 = time.time()
radixSort(arr)
t2 = time.time()
quickSort(arr,0,len(arr)-1)
t3 = time.time()
if(t2-t1<=t3-t2):
print(limit)
break
limit+=1
print(limit)