Question

write a code in python for COUNTING SORT. check the runtime for the algorithms for varying input sizes.

Input size n (size of the list) the following list sizes

1. 10,000

2. 100,000

3. 1000,000

For each of these sizes we are going to have two types of input:

a. Sorted list (ascending order) of elements from range (1:n)

b. Sorted list (descending order) of elements from range (n:1)

Answer 1

 import time def countingSort(arr): n = len(arr) output = [0] * n count = [0] * 10 for i in range(0, n): count[arr[i]] += 1 for i in range(1, 10): count[i] += count[i - 1] i = n - 1 while i >= 0: output[count[arr[i]] - 1] = arr[i] count[arr[i]] -= 1 i -= 1 for i in range(0, n): array[i] = output[i] n = int(input("Enter size of array: ")) arr = []*n print("Sorted list (ascending order) of elements from range (1:n)") for i in range (0,n): arr[i] = int(input()) start = time.process_time() countingSort(arr) print(time.process_time() - start) print("Enter Sorted list (descending order) of elements from range (n:1)") for i in range (n-1,-1,-1): arr[i] = int(input()) start = time.process_time() countingSort(arr) print(time.process_time() - start) 

#Python program

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

for i in range(0, n):
count[arr[i]] += 1

for i in range(1, 10):
count[i] += count[i - 1]

i = n - 1
while i >= 0:
output[count[arr[i]] - 1] = arr[i]
count[arr[i]] -= 1
i -= 1

for i in range(0, n):
array[i] = output[i]

n = int(input("Enter size of array: "))
arr = []*n
print("Sorted list (ascending order) of elements from range (1:n)")
for i in range (0,n):
arr[i] = int(input())

start = time.process_time()
countingSort(arr)
print(time.process_time() - start)

print("Enter Sorted list (descending order) of elements from range (n:1)")

for i in range (n-1,-1,-1):
arr[i] = int(input())

start = time.process_time()
countingSort(arr)
print(time.process_time() - start)