Counting Sort is a linear time sorting algorithm that is used to sort an array of integers in a specific range. In this blog, we will explore the implementation of Counting Sort in Python.
Counting Sort Algorithm
Counting Sort works by counting the number of occurrences of each distinct element in the input array and then using that information to determine the relative position of each element in the sorted output array. Here's the algorithm for Counting Sort:
Find the maximum value in the input array.
Create a count array with a size equal to the maximum value.
Count the number of occurrences of each distinct element in the input array and store it in the count array.
Modify the count array to store the cumulative sum of the counts.
Traverse the input array from right to left and place each element in its correct sorted position based on the count array.
Decrement the count of the placed element in the count array.
Repeat step 5-6 until all elements have been placed in their sorted positions.
Return the sorted array.
Counting Sort Implementation in Python
Let's implement the Counting Sort algorithm in Python:
def counting_sort(arr):
max_val = max(arr)
count = [0] * (max_val + 1)
# Count the number of occurrences of each element
for num in arr:
count[num] += 1
# Modify the count array to store cumulative sum
for i in range(1, len(count)):
count[i] += count[i-1]
# Place each element in its correct sorted position
sorted_arr = [0] * len(arr)
for num in reversed(arr):
index = count[num] - 1
sorted_arr[index] = num
count[num] -= 1
return sorted_arr
In the counting_sort function, we first find the maximum value in the input array and create a count array with a size equal to the maximum value. We then count the number of occurrences of each element in the input array and store it in the count array.
Next, we modify the count array to store the cumulative sum of the counts. We then traverse the input array from right to left and place each element in its correct sorted position based on the count array. We decrement the count of the placed element in the count array and repeat this process until all elements have been placed in their sorted positions.
Finally, we return the sorted array.
Conclusion
Counting Sort is a linear time sorting algorithm that is used to sort an array of integers in a specific range. It works by counting the number of occurrences of each distinct element in the input array and then using that information to determine the relative position of each element in the sorted output array. The implementation of Counting Sort in Python is simple and requires only a few lines of code, making it an efficient choice for sorting large datasets.
Here is detail on each sorting algorithm in python
0 Comments