Learn Programming and technology with ease @ developerpublish.com

HomePythonPython Program to Implement Counting Sort

# Python Program to Implement Counting Sort

Counting Sort is a non-comparative sorting algorithm that works particularly well when the range of input values is known and relatively small. Itâ€™s efficient because it doesnâ€™t rely on comparisons between elements, unlike algorithms like Quick Sort or Merge Sort. Instead, it directly uses the input values themselves to determine their sorted positions. Counting Sortâ€™s time complexity is O(n + k), where n is the number of elements in the input array and k is the range of input values.

## Problem Statement

You are given an array of integers. Implement the Counting Sort algorithm in Python to sort the array in non-decreasing order.

## Python Program to Implement Counting Sort

```def counting_sort(arr):
# Find the range of elements in the array
max_value = max(arr)
min_value = min(arr)
range_of_elements = max_value - min_value + 1

# Initialize a count array to store the frequency of elements
count_array = [0] * range_of_elements

# Count the frequency of each element in the input array
for num in arr:
count_array[num - min_value] += 1

# Update the count array to store the cumulative count
for i in range(1, len(count_array)):
count_array[i] += count_array[i - 1]

# Create the output array
output_array = [0] * len(arr)

# Build the output array using the count array
for num in reversed(arr):
output_array[count_array[num - min_value] - 1] = num
count_array[num - min_value] -= 1

return output_array

# Example usage
input_array = [4, 2, 2, 8, 3, 3, 1]
sorted_array = counting_sort(input_array)
print("Input Array:", input_array)
print("Sorted Array:", sorted_array)
```

## How it Works

Step 1: Finding the Range

• Find the maximum and minimum values in the input array to determine the range of values. In this case, the maximum value is 8 and the minimum value is 1, so the range is [1, 8].

Step 2: Create a Count Array

• Create a count array to store the frequency of each value within the specified range `[1, 8]`. Initialize all elements of the count array to zero.

Step 3: Count Frequencies

• Count the occurrences of each value in the input array and update the count array accordingl

Step 4: Calculate Cumulative Counts

• Modify the count array to store cumulative counts. This step helps determine the positions of the elements in the sorted array.

mathematically.

Step 5: Build the Sorted Array

• Create a new array to store the sorted output. Traverse the input array in reverse order, and for each element, find its position in the sorted array using the cumulative count array. Decrease the cumulative count for that elementâ€™s value by one.

## Input/ Output

### You May Also Like

#### Python Program to Remove Duplicates from a Linked List

In this Python program, we will create a singly linked list and remove duplicate elements from it. A linked list...

#### Python Program to Solve the Celebrity Problem

This Python program solves the Celebrity Problem by finding a person who is known by everyone but does not know...

#### Python Program to Solve n-Queen Problem with Recursion

This Python program uses a recursive approach to solve the n-Queens problem. It explores all possible combinations of queen placements...