Counting Sort in C++

Counting Sort Algorithm in C++ (Complete Implementation).

IntermediateSorting & Searching ProgramsExample 8 of 13

counting-sort.cpp

1#include <iostream>
2#include <algorithm>
3using namespace std;
4
5void countingSort(int arr[], int n) {
6    int max = *max_element(arr, arr + n);
7    int min = *min_element(arr, arr + n);
8    int range = max - min + 1;
9    
10    int count[range] = {0};
11    int output[n];
12    
13    // Store count of each element
14    for (int i = 0; i < n; i++)
15        count[arr[i] - min]++;
16    
17    // Change count to position
18    for (int i = 1; i < range; i++)
19        count[i] += count[i - 1];
20    
21    // Build output array
22    for (int i = n - 1; i >= 0; i--) {
23        output[count[arr[i] - min] - 1] = arr[i];
24        count[arr[i] - min]--;
25    }
26    
27    // Copy output to original array
28    for (int i = 0; i < n; i++)
29        arr[i] = output[i];
30}
31
32void printArray(int arr[], int n) {
33    for (int i = 0; i < n; i++) {
34        cout << arr[i] << " ";
35    }
36    cout << endl;
37}
38
39int main() {
40    int arr[] = {4, 2, 2, 8, 3, 3, 1};
41    int n = sizeof(arr) / sizeof(arr[0]);
42    
43    cout << "Original array: ";
44    printArray(arr, n);
45    
46    countingSort(arr, n);
47    
48    cout << "Sorted array: ";
49    printArray(arr, n);
50    
51    return 0;
52}

Output

Original array: 4 2 2 8 3 3 1
Sorted array: 1 2 2 3 3 4 8

What's going on

The program sorts an array of integers using the Counting Sort algorithm. For example:

Input array: [4, 2, 2, 8, 3, 3, 1]

Output array: [1, 2, 2, 3, 3, 4, 8]

Counting Sort works by counting how many times each value appears, then placing each element in its correct position based on these counts.

Header Files Used

1.#include <iostream>

Provides cout and cin for input/output operations.

2.#include <algorithm>

Provides max_element() and min_element() functions to find range.

Understanding Counting Sort

Algorithm Concept

Count occurrences of each value

Calculate cumulative counts (positions)

Place elements in correct positions

Stable sorting algorithm

Visual Example

Array: [4, 2, 2, 8, 3, 3, 1]

Step 1: Count occurrences

Value 1: count = 1

Value 2: count = 2

Value 3: count = 2

Value 4: count = 1

Value 8: count = 1

Step 2: Calculate positions (cumulative counts)

Position for 1: 0

Position for 2: 1

Position for 3: 3

Position for 4: 5

Position for 8: 6

Step 3: Place elements

Result: [1, 2, 2, 3, 3, 4, 8]

Function: countingSort()

void countingSort(int arr[], int n) {

int max = *max_element(arr, arr + n);

int min = *min_element(arr, arr + n);

int range = max - min + 1;

int count[range] = {0};

int output[n];

for (int i = 0; i < n; i++)

count[arr[i] - min]++;

// Change count to position

for (int i = 1; i < range; i++)

count[i] += count[i - 1];

// Build output array

for (int i = n - 1; i >= 0; i--) {

output[count[arr[i] - min] - 1] = arr[i];

count[arr[i] - min]--;

}

// Copy output to original array

for (int i = 0; i < n; i++)

arr[i] = output[i];

}

1// Store count of each element

How it works

Finds min and max to determine range

Counts occurrences of each value

Converts counts to positions (cumulative)

Places elements in correct positions (right to left for stability)

Step-by-Step Algorithm

Step 1: Find Range

max = 8, min = 1

range = 8 - 1 + 1 = 8

Count array size: 8

Step 2: Count Occurrences

arr[i] - min: maps value to count array index

Example: 4 - 1 = 3 → count[3]++

Builds frequency array

Step 3: Calculate Positions

Cumulative sum: count[i] += count[i-1]

Each count[i] now represents starting position

Example: count[2] = 3 means value 3 starts at position 3

Step 4: Build Output

Process from right to left (for stability)

Place element at position count[arr[i] - min] - 1

Decrement count after placement

Understanding Count to Position Conversion

Before

(counts):

count[0] = 1 (value 1 appears 1 time)

count[1] = 2 (value 2 appears 2 times)

count[2] = 2 (value 3 appears 2 times)

count[3] = 1 (value 4 appears 1 time)

count[7] = 1 (value 8 appears 1 time)

After

(positions):

count[0] = 1 (value 1 at position 0)

count[1] = 3 (value 2 at positions 1-2)

count[2] = 5 (value 3 at positions 3-4)

count[3] = 6 (value 4 at position 5)

count[7] = 7 (value 8 at position 6)

Time and Space Complexity

Time Complexity

: O(n + k)

n: number of elements

k: range of values (max - min + 1)

Counting: O(n)

Position calculation: O(k)

Building output: O(n)

Total: O(n + k)

Space Complexity

: O(n + k)

Output array: O(n)

Count array: O(k)

Total: O(n + k)

Stability

: Stable

Processing from right to left maintains relative order

Equal elements preserve their original order

When to Use Counting Sort

Best For

Small range of integer values

When k is not much larger than n

When stability is required

Non-negative integers (or with offset)

Not Recommended For

Large range (k >> n) - wastes space

Floating-point numbers

Strings or complex objects

When range is unknown or very large

Important Considerations

Range Calculation

range = max - min + 1

Handles negative numbers with offset (arr[i] - min)

Count array size equals range

Stability

Processing from right to left (i = n-1 to 0) ensures stability

Equal elements maintain relative order

Index Mapping

arr[i] - min: maps value to count array index

Handles any range starting from min

Example: values 100-107 → indices 0-7

return 0;

This ends the program successfully.

PreviousRadix Sort NextLinear Search