• Hajipur, Bihar, 844101

☰
❮
❯

Python

Introduction to Python

Python Basics

Cotrol Structures

Data Structures

Date and Time

Functions and Module

File Handling

Python OOP

Advanced Concepts

Python DSA

Searching Algorithms

Sorting Algorithms

Python Counting Sort

← Previous Next →

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

  1. Count occurrences of each element

  2. Store count in a separate array

  3. Use that count to place each element at its correct position

  4. 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 Counting Sort Quiz

Q1: What type of algorithm is counting sort?

A. Comparison-based
B. Divide and conquer
C. Non-comparison-based
D. Merge-based

Q2: Counting sort works best when:

A. Data is very large
B. Data is reversed
C. Range of values is small
D. Data is sorted

Q3: Time complexity of counting sort is:

A. O(n log n)
B. O(n²)
C. O(n + k)
D. O(log n)

Q4: Counting sort is stable when:

A. Output order of duplicates is preserved
B. Pivot is always mid
C. Recursion is used
D. Sorting is in-place

Q5: What does the count array store?

A. Sorted elements
B. Frequencies
C. Pivot positions
D. Divisions

Q6: Counting sort does not work well on:

A. Integers
B. Strings
C. Negative numbers (without changes)
D. Small lists

Q7: Can Counting Sort be performed in-place?

A. Yes
B. No
C. Only for binary data
D. Only if list is sorted already

Q8: What is a key requirement of input for counting sort?

A. Sorted data
B. Unique values
C. Integer values in known range
D. Floating-point numbers

Q9: What is the space complexity of counting sort?

A. O(n)
B. O(k)
C. O(1)
D. O(log n)

Q10: Which of the following uses no comparison between elements?

A. Merge sort
B. Quick sort
C. Counting sort
D. Bubble sort
← Previous Next →
Login
Go Back Top