Question

data=[3831,4572,4219,2099,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]

In PYTHON please write a code that implements the counting sort algorithm by making a CountingSort function with an array input. Please make the array input in the form of a list. Then sort 3 randomly generated arrays by writing code, and the data array listed below. Test all 4 arrays and print the output.

Please develop then comment on the growth function of the code, and comment on the big O notation.

Answer 1

def countingSort(array):
    size = len(array)
    output = [0] * size

    # Initialize count array
    maxNum = max(array) 
    count = [0] * (maxNum+1)

    # Store the count of each elements in count array
    for i in range(0, size):
        count[array[i]] += 1

    # Store the cummulative count
    for i in range(1, maxNum+1):
        count[i] += count[i - 1]

    # Find the index of each element of the original array in count array
    # place the elements in output array
    i = size - 1
    while i >= 0:
        output[count[array[i]] - 1] = array[i]
        count[array[i]] -= 1
        i -= 1

    # Copy the sorted elements into original array
    for i in range(0, size):
        array[i] = output[i]

import random
# To generate 3 random size for our Array
n1 = random.randint(1,15)
n2 = random.randint(1,15)
n3 = random.randint(1,15)
print(n1,n2,n3)

#Generating 3 random list using random size and random number's range

randomlist1 = []
for i in range(0,n1):
  n = random.randint(1,30)
  randomlist1.append(n)
print(randomlist1)
randomlist2 = []
for i in range(0,n2):
  n = random.randint(100,300)
  randomlist2.append(n)
print(randomlist2)
randomlist3 = []
for i in range(0,n3):
  n = random.randint(500,999)
  randomlist3.append(n)
print(randomlist3)

#Data Listen given by Useer
dataList = [3831,4572,4219,2099,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]

countingSort(randomlist1)
print("Sorted Array in Ascending Order: ")
print(randomlist1)

countingSort(randomlist2)
print("Sorted Array in Ascending Order: ")
print(randomlist2)

countingSort(randomlist3)
print("Sorted Array in Ascending Order: ")
print(randomlist3)

countingSort(dataList)
print("Sorted Array in Ascending Order: ")
print(dataList)

There are mainly 4 for loops present within the function countSorting:

1st Loop - O(maxNum)

2nd Loop - O(size)

3rd Loop - O(maxNum)

4th Loop - O(size)

Overall Complexity - O(maxNum+size){ O(maxNum)+O(size)+O(maxNum)+O(size)}

For all the cases(Worst, Average, Best), the function is going to follow same number of iterations i.e complexity is not gonna differ in any of the case. It is dependent on arraysize and maximum element present within the array.

Hence O(n+k) where n is size of array and k is the maximum element.

But, it is bad if the integers are very large because the array of that size should be made.