Counting Sort Algorithm

Counting Sort is an integer sorting algorithm that operates by counting the occurrences of each unique element in the input list. It then uses this count information to place each element in its correct position in the output list. Counting Sort is particularly efficient when the range of the input data (the difference between the maximum and minimum values) is not significantly larger than the number of elements.

How Counting Sort Works:

1. Determine the Range:
   • First, determine the range of the input data by finding the minimum and maximum values. This range helps to initialize the counting array, which will hold the count of each unique element.
2. Count the Elements:
   • Initialize a counting array of size equal to the range of the input data. The counting array is used to store the count of each unique element. Traverse the input list and for each element, increment the corresponding index in the counting array.
3. Cumulative Count:
   • Transform the counting array such that each element at each index contains the sum of the previous counts. This step helps in placing the elements in the correct position in the output array. Essentially, it tells us the position of each element in the sorted array.
4. Build the Output Array:
   • Initialize an output array of the same size as the input list. Traverse the input list in reverse order, using the counting array to place each element in its correct position in the output array. Decrement the count in the counting array each time an element is placed in the output array.
5. Copy to Original Array:
   • Copy the sorted elements from the output array back to the original array if required.

Characteristics of Counting Sort:

• Time Complexity:
  • Best Case: O(n + k) where n is the number of elements in the input list, and k is the range of the input values.
  • Average Case: O(n + k)
  • Worst Case: O(n + k)
  • Counting Sort has a linear time complexity if the range of the input values (k) is not significantly larger than the number of elements (n).
• Space Complexity:
  • Counting Sort requires additional space for the counting array and the output array, making its space complexity O(n + k).
• Stability:
  • Counting Sort is a stable sorting algorithm, meaning it preserves the relative order of records with equal keys (i.e., values).
• Usage:
  • Counting Sort is particularly useful for sorting lists of integers or objects with integer keys when the range of the keys is not significantly larger than the number of elements. It is not suitable for sorting floating-point numbers or large ranges of integers due to the additional space requirements.

Code Example

def countingSort(myList, length):
    maximum = myList[0]
    position = 0

    for i in range(1, length):
        if myList[i] > maximum:
            maximum = myList[i]

    tmpList = [0] * (maximum + 1)
    for i in range(0, length):
        tmpList[myList[i]] += 1

    for i in range(0, maximum + 1):
        for j in range(0, tmpList[i]):
            myList[position] = i
            position += 1


def printArray(myList, length):
    for i in range(0, length):
        print(myList[i], end=" ")


length = int(input("How many numbers do you want to sort? "))
myList = [] * length
i = 0

while i < length:
    value = int(input("Please enter the next number: "))
    myList.append(value)
    i += 1


print("\nArray to be sorted:")
printArray(myList, length)
print("\nGradual sorting:")
countingSort(myList, length)
print("Sorted array:")
printArray(myList, length)

Output

How many numbers do you want to sort? 6
Please enter the next number: 88
Please enter the next number: 23
Please enter the next number: 2
Please enter the next number: 5
Please enter the next number: 9
Please enter the next number: 12

Array to be sorted:
88 23 2 5 9 12 
Gradual sorting:
Sorted array:
2 5 9 12 23 88

Code Explanation

The function starts by determining the maximum value in the input list myList and stores it in the maximum variable. It then creates a temporary list tmpList of size maximum + 1 to store the count of each integer in the input list. This is done using the loop:

for i in range(0, length):
    tmpList[myList[i]] += 1

The next step is to populate the input list myList with the sorted elements, which is done using the following loop:

for i in range(0, maximum + 1):
    for j in range(0, tmpList[i]):
        myList[position] = i
        position += 1

In this loop, the elements from tmpList are added to myList in the sorted order. The function printArray is used to print the input list myList and the sorted list.

In the main part of the code, the user is asked to enter length numbers, which are stored in the list myList. The input list is then passed to the countingSort function for sorting, and the sorted list is printed using the printArray function.