-
Hajipur, Bihar, 844101
Python
Introduction to Python
Python Basics
-
Python Syntax
-
Python Comments
-
Python Variables
-
Python Data Types
-
Python Casting
-
Python I/O
-
Python Operators
Cotrol Structures
Data Structures
-
Python Strings
-
Python Lists
-
Python Tuples
-
Python Dictionaries
-
Python Sets
-
Python Arrays
-
Python Bytes and Bytearray
Date and Time
Functions and Module
File Handling
Python OOP
Advanced Concepts
-
Python Scope
-
Python Modules
-
Python JSON
-
Python RegEx
-
Python PIP
-
Python Try...Except
-
Python String Formatting
-
Python User Input
-
Python VirtualEnv
-
Python Math
Python DSA
-
Python DSA
-
Lists and Arrays
-
Python Stacks
-
Python Queues
-
Linked Lists
-
Python Hash Tables
-
Python Trees
-
Python Binary Trees
-
Binary Search Trees
-
Python AVL Trees
-
Python Graphs
Searching Algorithms
Sorting Algorithms
Python Counting Sort
Counting Sort is a non-comparison-based sorting algorithm used to sort integers in a specific range.
It counts the number of occurrences of each element, then calculates positions to place them in sorted order.
It is efficient when the range of input data is not significantly greater than the number of items.
🔹 How Counting Sort Works
-
Count occurrences of each element
-
Store count in a separate array
-
Use that count to place each element at its correct position
-
Build the output array using the count array
🔹 Counting Sort in Python
def counting_sort(arr):
max_val = max(arr)
count = [0] * (max_val + 1)
# Count the frequency of each number
for num in arr:
count[num] += 1
# Reconstruct the sorted array
index = 0
for i in range(len(count)):
while count[i] > 0:
arr[index] = i
index += 1
count[i] -= 1
Example
nums = [4, 2, 2, 8, 3, 3, 1]
counting_sort(nums)
print("Sorted array:", nums)
✅ Output:
Sorted array: [1, 2, 2, 3, 3, 4, 8]
🔹 Limitations of Counting Sort
-
Works only with non-negative integers
-
Not efficient if the range is too large compared to input size
-
Not suitable for floating point numbers or strings (without modification)
🔹 Time and Space Complexity
| Case | Time |
|---|---|
| Best Case | O(n + k) |
| Average | O(n + k) |
| Worst Case | O(n + k) |
| Space | O(k) |
Where
n= number of elements,k= range of input
🔹 Use Cases of Counting Sort
-
Sorting test scores (0-100)
-
Sorting small-range integers
-
When stability and speed are more important than low space usage
Practice Questions
Q1. Write a Python program to sort the list [3, 6, 4, 1, 3, 4, 1, 4] using counting sort.
Q2. Write a Python program to modify counting sort so that it returns a new sorted array instead of modifying the original list.
Q3. Write a Python program to print the count array for the list [0, 2, 2, 3, 1] using counting sort.
Q4. Write a Python program to handle counting sort on a list with values up to 1000.
Q5. Write a Python program to count and display how many times each number appears in the list using counting sort logic.
Q6. Write a Python program to accept a list of integers from user input and sort it using counting sort.
Q7. Write a Python program to sort a list that includes 0 using counting sort.
Q8. Write a Python program to attempt sorting a list with negative numbers using counting sort and observe what breaks.
Q9. Write a Python program to count and print the total number of iterations (loops) made during the counting sort process.
Q10. Write a Python program to compare the output of counting sort with Python's built-in sorted() function for the same list.
Python
Introduction to Python
Python Basics
-
Python Syntax
-
Python Comments
-
Python Variables
-
Python Data Types
-
Python Casting
-
Python I/O
-
Python Operators
Cotrol Structures
Data Structures
-
Python Strings
-
Python Lists
-
Python Tuples
-
Python Dictionaries
-
Python Sets
-
Python Arrays
-
Python Bytes and Bytearray
Date and Time
Functions and Module
File Handling
Python OOP
Advanced Concepts
-
Python Scope
-
Python Modules
-
Python JSON
-
Python RegEx
-
Python PIP
-
Python Try...Except
-
Python String Formatting
-
Python User Input
-
Python VirtualEnv
-
Python Math
Python DSA
-
Python DSA
-
Lists and Arrays
-
Python Stacks
-
Python Queues
-
Linked Lists
-
Python Hash Tables
-
Python Trees
-
Python Binary Trees
-
Binary Search Trees
-
Python AVL Trees
-
Python Graphs
Searching Algorithms
Sorting Algorithms
