Counting Sort Algorithm in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Counting Sort on a small array

What is the output of the following counting sort implementation on the array [4, 2, 2, 8, 3, 3, 1]?

DSA C

void countingSort(int arr[], int n) {
    int output[n];
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) max = arr[i];
    }
    int count[max + 1];
    for (int i = 0; i <= max; i++) count[i] = 0;
    for (int i = 0; i < n; i++) count[arr[i]]++;
    for (int i = 1; i <= max; i++) count[i] += count[i - 1];
    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }
    for (int i = 0; i < n; i++) arr[i] = output[i];
}

int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    countingSort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

A [1, 2, 2, 3, 3, 4, 8]

B [8, 4, 3, 3, 2, 2, 1]

C [1, 2, 3, 4, 8]

D [4, 2, 2, 8, 3, 3, 1]

💡 Hint

Counting sort sorts numbers by counting occurrences and placing them in order.

Counting sort counts how many times each number appears, then places them in sorted order. The output is the sorted array.

🧠 Conceptual

intermediate

Counting Sort Stability Property

Which statement best describes the stability property of counting sort?

A Counting sort is unstable because it changes the order of equal elements.

B Counting sort is unstable because it uses a hash table internally.

C Counting sort is stable only if the input array is already sorted.

D Counting sort is stable because it preserves the relative order of equal elements.

💡 Hint

Think about whether equal numbers keep their original order after sorting.

Counting sort is stable because it places elements in output array in a way that preserves their original order when equal.

❓ Predict Output

advanced

Counting Sort with Negative Numbers

What will happen if the following counting sort code is run on the array [-2, -5, -3, 0, -1]?

DSA C

void countingSort(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) max = arr[i];
    }
    int count[max + 1];
    for (int i = 0; i <= max; i++) count[i] = 0;
    for (int i = 0; i < n; i++) count[arr[i]]++;
    for (int i = 1; i <= max; i++) count[i] += count[i - 1];
    int output[n];
    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }
    for (int i = 0; i < n; i++) arr[i] = output[i];
}

A The code will sort only positive numbers and ignore negatives.

B The code will produce an empty output array.

C The code will cause a runtime error due to negative array index.

D The code will sort the array correctly including negative numbers.

💡 Hint

Array indices cannot be negative in C.

Counting sort as implemented uses array indices equal to values. Negative numbers cause invalid negative indices, leading to runtime error.

🔧 Debug

advanced

Identify the bug in counting sort code

What is the bug in this counting sort code snippet?

DSA C

void countingSort(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) max = arr[i];
    }
    int count[max];
    for (int i = 0; i < max; i++) count[i] = 0;
    for (int i = 0; i < n; i++) count[arr[i]]++;
    for (int i = 1; i < max; i++) count[i] += count[i - 1];
    int output[n];
    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }
    for (int i = 0; i < n; i++) arr[i] = output[i];
}

A The loop initializing count should start from 1, not 0.

B The count array size should be max + 1, not max.

C The output array should be declared before count array.

D The counting loop should use count[arr[i] - 1] instead of count[arr[i]].

💡 Hint

Check the size of the count array and the maximum index accessed.

The count array must have size max + 1 to include the max value index. Using max size causes out-of-bounds access.

🚀 Application

expert

Counting Sort Time Complexity Analysis

Given an input array of size n with values ranging from 0 to k, what is the time complexity of counting sort?

A O(n + k)

B O(n log n)

C O(k log n)

D O(n * k)

💡 Hint

Counting sort counts occurrences and then outputs sorted array.

Counting sort runs in O(n + k) because it counts frequencies (k) and processes n elements.

Practice

1. What is the main idea behind the Counting Sort algorithm?

easy

A. Counting the number of occurrences of each element to sort

B. Comparing each element with every other element

C. Dividing the array into halves and sorting recursively

D. Swapping adjacent elements repeatedly

Solution

1. Step 1: Understand Counting Sort principle

   Counting Sort counts how many times each value appears in the input.

2. Step 2: Use counts to place elements in order

   Using these counts, it places elements directly into the sorted output.

3. Final Answer:

   Counting the number of occurrences of each element to sort -> Option A

4. Quick Check:

   Counting occurrences = A [OK]

Hint: Counting occurrences helps sort without comparisons [OK]

Common Mistakes:

• Thinking it compares elements like bubble sort
• Confusing with divide and conquer methods
• Assuming it swaps elements repeatedly

2. Which of the following is the correct way to declare the count array in C for counting sort if the maximum value in input is max_val?

easy

A. int count[max_val + 1];

B. int count[max_val];

C. int count[max_val - 1];

D. int count[max_val * 2];

Solution

1. Step 1: Understand array size for counts

   The count array must hold counts for all values from 0 to max_val inclusive, so size is max_val + 1.

2. Step 2: Choose correct declaration

   Declaring int count[max_val + 1]; ensures space for all possible values.

3. Final Answer:

   int count[max_val + 1]; -> Option A

4. Quick Check:

   Count array size = max_val + 1 [OK]

Hint: Count array size must cover all values including max_val [OK]

Common Mistakes:

• Using max_val size misses last element count
• Using max_val - 1 causes out-of-range errors
• Using double size wastes memory unnecessarily

3. What will be the output of the counting sort on the array [4, 2, 2, 8, 3, 3, 1]?

medium

A. [1, 3, 2, 4, 8, 3, 2]

B. [1, 2, 2, 3, 3, 4, 8]

C. [8, 4, 3, 3, 2, 2, 1]

D. [2, 2, 3, 3, 4, 8, 1]

Solution

1. Step 1: Count occurrences of each element

   1 appears once, 2 appears twice, 3 appears twice, 4 once, 8 once.

2. Step 2: Place elements in sorted order using counts

   Sorted array is [1, 2, 2, 3, 3, 4, 8].

3. Final Answer:

   [1, 2, 2, 3, 3, 4, 8] -> Option B

4. Quick Check:

   Sorted array = C [OK]

Hint: Count then output in order for sorted array [OK]

Common Mistakes:

• Confusing input order with output order
• Forgetting to repeat elements by their counts
• Mixing up counts and positions

4. Given the following code snippet for counting sort, what is the error?

int count[5] = {0};
int arr[6] = {1, 3, 4, 2, 3, 0};
for (int i = 0; i < 6; i++) {
    count[arr[i]]++;
}
for (int i = 0; i <= 5; i++) {
    printf("%d ", count[i]);
}

medium

A. Incrementing count[arr[i]] is wrong

B. Count array not initialized to zero

C. Array arr size is incorrect

D. Loop accessing count array goes out of bounds

Solution

1. Step 1: Check count array size and loop range

   Count array size is 5 (indices 0 to 4), but loop runs i from 0 to 5 inclusive, accessing count[5] which is out of bounds.

2. Step 2: Identify out-of-bounds access

   Accessing count[5] causes undefined behavior or error.

3. Final Answer:

   Loop accessing count array goes out of bounds -> Option D

4. Quick Check:

   Loop index > count size = D [OK]

Hint: Check array size vs loop limits carefully [OK]

Common Mistakes:

• Ignoring array size when looping
• Assuming initialization fixes out-of-bounds
• Confusing arr size with count size

5. You want to sort an array containing negative and positive integers using counting sort. Which modification is necessary?

hard

A. Use the array as is because counting sort handles negatives naturally

B. Sort only positive numbers and ignore negatives

C. Shift all numbers by adding the absolute value of the minimum element before sorting

D. Use bubble sort instead

Solution

1. Step 1: Understand counting sort limitation

   Counting sort works only with non-negative integers because it uses array indices as counts.

2. Step 2: Adjust negative values for indexing

   Shift all numbers by adding the absolute value of the minimum element to make all values non-negative before counting.

3. Final Answer:

   Shift all numbers by adding the absolute value of the minimum element before sorting -> Option C

4. Quick Check:

   Shift negatives to non-negative = B [OK]

Hint: Shift negatives to zero or above before counting [OK]

Common Mistakes:

• Trying to count negatives directly
• Ignoring negative values in input
• Switching to other sorts unnecessarily