Counting Sort in C - Linear Sorting Algorithm

Introduction to Counting Sort

Counting Sort is a non-comparison-based sorting algorithm that sorts integers by counting the occurrences of each unique element. Unlike comparison-based algorithms (like Quick Sort or Merge Sort), Counting Sort uses the actual values of the elements as indices into an array.

Key characteristics of Counting Sort:

• Linear time complexity: O(n + k) where k is the range of input
• Stable: Preserves the relative order of equal elements
• Not in-place: Requires extra memory for counting and output arrays
• Efficient for small integer ranges: Works best when the range of values is not too large

C Program for Counting Sort

#include <stdio.h>
#include <stdlib.h>

// Function to find the maximum element in an array
int findMax(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

// Function to find the minimum element in an array
int findMin(int arr[], int n) {
    int min = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] < min) {
            min = arr[i];
        }
    }
    return min;
}

// Counting Sort function
void countingSort(int arr[], int n) {
    // Find the range of values
    int min = findMin(arr, n);
    int max = findMax(arr, n);
    int range = max - min + 1;

    // Create count array and output array
    int *count = (int *)calloc(range, sizeof(int));
    int *output = (int *)malloc(n * sizeof(int));

    // Count occurrences of each element
    for (int i = 0; i < n; i++) {
        count[arr[i] - min]++;
    }

    // Modify count array to store cumulative counts
    for (int i = 1; i < range; i++) {
        count[i] += count[i - 1];
    }

    // Build the output array
    for (int i = n - 1; i >= 0; i--) {
        int index = arr[i] - min;
        output[count[index] - 1] = arr[i];
        count[index]--;
    }

    // Copy output array back to original array
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }

    // Free allocated memory
    free(count);
    free(output);
}

// Function to print the array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// Driver program to test the counting sort
int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1, 5, 7, 6, 9, 2, 4, 6, 8};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, n);

    countingSort(arr, n);

    printf("Sorted array:   ");
    printArray(arr, n);

    return 0;
}

Sample Output

Original array: 4 2 2 8 3 3 1 5 7 6 9 2 4 6 8
Sorted array:   1 2 2 2 3 3 4 4 5 6 6 7 8 8 9

Example with negative numbers:

Original array: -5 -2 8 0 3 -1 4 7 -3 6
Sorted array:   -5 -3 -2 -1 0 3 4 6 7 8

Program Explanation

Let's break down the code step by step:

1. Include Header Files: #include <stdio.h> and #include <stdlib.h> for input/output and memory allocation.
2. Find Min and Max:
   • findMax() and findMin() determine the range of values
   • This allows the algorithm to handle negative numbers and any integer range
3. Counting Sort Function:
   • Step 1: Find range = max - min + 1
   • Step 2: Create a count array of size 'range' initialized to 0
   • Step 3: Count occurrences: count[arr[i] - min]++
   • Step 4: Cumulative count: count[i] += count[i-1]
   • Step 5: Build output array by placing elements in sorted order
   • Step 6: Copy output back to original array
4. Memory Management: Uses calloc() and malloc() for dynamic memory allocation, and free() to prevent memory leaks.
5. PrintArray Function: Displays all elements of the array.
6. Main Function:
   • Creates an unsorted array
   • Displays the original array
   • Calls countingSort() to sort
   • Displays the sorted array

Step-by-Step Approach

Algorithm for Counting Sort

1. Find Range:
   • min = findMin(arr, n)
   • max = findMax(arr, n)
   • range = max - min + 1
2. Count Occurrences:
   • For each element arr[i], increment count[arr[i] - min]
3. Cumulative Count:
   • For i = 1 to range-1: count[i] += count[i-1]
4. Build Output:
   • For i = n-1 down to 0:
   • index = arr[i] - min
   • output[count[index] - 1] = arr[i]
   • count[index]--
5. Copy Back: Copy output array to original array

Time & Space Complexity

// For characters, convert to ASCII values
void countingSortChar(char arr[], int n) {
    // ASCII range: 0-255
    int range = 256;
    int *count = (int *)calloc(range, sizeof(int));
    char *output = (char *)malloc(n * sizeof(char));
    
    for (int i = 0; i < n; i++) {
        count[(int)arr[i]]++;
    }
    
    for (int i = 1; i < range; i++) {
        count[i] += count[i-1];
    }
    
    for (int i = n-1; i >= 0; i--) {
        int idx = (int)arr[i];
        output[count[idx] - 1] = arr[i];
        count[idx]--;
    }
    
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
    
    free(count);
    free(output);
}

// Grade sorting (0-100 range)
void sortGrades(int grades[], int n) {
    // Range: 0 to 100
    const int MAX_GRADE = 100;
    int count[MAX_GRADE + 1] = {0};
    int output[n];
    
    for (int i = 0; i < n; i++) {
        count[grades[i]]++;
    }
    
    for (int i = 1; i <= MAX_GRADE; i++) {
        count[i] += count[i-1];
    }
    
    for (int i = n-1; i >= 0; i--) {
        output[count[grades[i]] - 1] = grades[i];
        count[grades[i]]--;
    }
    
    for (int i = 0; i < n; i++) {
        grades[i] = output[i];
    }
}

Frequently Asked Questions

Previous Topic: -->> Heap Sort in C   ||   Next topic: -->> Radix Sort in C