Question

Please write a python code which implements the counting sort algorithm by creating a CountingSort function with an array input in the form of a list. Then write code to sort 3 randomly generated arrays and the data array listed below, print the output clearly for all four test arrays, develop and comment on the growth function of your code. Comment on the Big O notation of the code. ( Please do not forget to comment on your code to explain what each line is doing )

The Given Data =[3720,4479,4218,2899,285,2391,3836,2290,410,4690,2031,1778,1468,4031,4513,1709,3603,4146,498,118,2635,3097,689,1340,617,394,3196,3676,4263,4110,2850,885,1926,2225,659,2643,4847,4579,977,2405,918,1256,4194,719,1218,3218,1969,395,156,3091,1860,44,2519,1763,2938,1246,1384,4034,2008,876,4346,1975,2612,2531,4518,4554,2187,3938,3396,434,4679,1681,2652,371,3884,1681,4636,3420,4880,111,566,2107,1810,4672,1716,303,1102,3777,3635,1485,2301,3127,2487,3058,1171,4240,4108,2990,334,3746,27,651,1299,1125,2475,2760,411,1932,4071,4099,4452,670,3229,2010,997,3274,2182,3072,42,4610,3657,844,1070,2697,322,4059,2255,3140,1162,1856,4111,4007,2599,4246,3508,2093,2597,1686,1014,158,1389,1032,1832,1481,2117,4947,4835,2820,2227,4469,1203,4665,3935,3946,792,1510,4940,3659,193,1603,3690,1531,761,2477,199,830,1920,1060,4717,3585,2830,3635,3205,3941,2677,3709,4544,3415,1222,3101,1010,4810,3052,3427,4702,2707,4488,458,1637,597,2105,1933,1587,231,1638,4713,1893,449,213,3822,1175,990,3349,440,2665,4248,2909,3221,1328,249,2576,4531,908,4302,728,3923,541,1330,4443,4655,2033,4761,4769,1540,48,600,2932,97,3161,2790,2093,2695,2735,3728,4879,2927,325,1244,1070,2056,2162,1367,4503,3924,3691,683,1553,716,4262,4760]

Answer 1

Algorithm: Counting sort is used to sort the elements by storing count of each elements in a frequency array where elements are mapped to its index and then returning those elements sequentially according to their count.

Have a look at the below code. I have put comments wherever required for better understanding.

# function for counting sort
def counting_sort(arr,n):
  res = [] # array to store the sorted result
  
  freq = [0]*(max(arr)+1) # Intialize the frquency array t store count of each array element

  # store the count in freq array
  for i in arr:
    freq[i]+=1 
  # populate the resultant array
  for i in range(len(freq)):
    # check if count is greater than 0
    if freq[i]>0:
      # add those elements to resultant array
      res.extend([i]*freq[i])
  # return sorted array
  return res 

arr1 = [3720,4479,4218,2899,285,2391,3836,2290,410,4690,2031,1778,1468,4031,4513,1709,3603,4146,498,118,2635,3097,689,1340,617,394,3196,3676,4263,4110,2850,885,1926,2225,659,2643,4847,4579,977,2405,918,1256,4194,719,1218,3218,1969,395,156,3091,1860,44,2519,1763,2938,1246,1384,4034,2008,876,4346,1975,2612,2531,4518,4554,2187,3938,3396,434,4679,1681,2652,371,3884,1681,4636,3420,4880,111,566,2107,1810,4672,1716,303,1102,3777,3635,1485,2301,3127,2487,3058,1171,4240,4108,2990,334,3746,27,651,1299,1125,2475,2760,411,1932,4071,4099,4452,670,3229,2010,997,3274,2182,3072,42,4610,3657,844,1070,2697,322,4059,2255,3140,1162,1856,4111,4007,2599,4246,3508,2093,2597,1686,1014,158,1389,1032,1832,1481,2117,4947,4835,2820,2227,4469,1203,4665,3935,3946,792,1510,4940,3659,193,1603,3690,1531,761,2477,199,830,1920,1060,4717,3585,2830,3635,3205,3941,2677,3709,4544,3415,1222,3101,1010,4810,3052,3427,4702,2707,4488,458,1637,597,2105,1933,1587,231,1638,4713,1893,449,213,3822,1175,990,3349,440,2665,4248,2909,3221,1328,249,2576,4531,908,4302,728,3923,541,1330,4443,4655,2033,4761,4769,1540,48,600,2932,97,3161,2790,2093,2695,2735,3728,4879,2927,325,1244,1070,2056,2162,1367,4503,3924,3691,683,1553,716,4262,4760]
arr2 = [3,4,5,3,1,0,6,7,]
arr3 = [23,55,44,23,0,67,55,2]
arr4 = [4,5,6,4,3,4,5]

print(counting_sort(arr1,len(arr1)))
print(counting_sort(arr2,len(arr2)))
print(counting_sort(arr3,len(arr3)))
print(counting_sort(arr4,len(arr4)))

  

Time Complexity: For frequency array to we need to find the max elemet of the array and to fill the that frequency array we have to loop in to the inout array.

So the overall time complexity will be O(max+size_of_array)

Space Complexity: We are creating a frequency array with size of maximum element of the array. So the overall space complexity will be O(max_element_of_array).

This is algorithm is only suitable where max element is not that much high.

Happy Learning!