Scribd
Upload
3 views3 pages

Counting Sort Implementation in C

The document contains a C program that implements the Counting Sort algorithm. It dynamically allocates memory for counting and output arrays, counts the occurrences of each element, and sorts the input array. The program also includes a driver function to test the sorting functionality with a sample array.

Uploaded by

hemlata dipesh agrawal
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views3 pages

Counting Sort Implementation in C

The document contains a C program that implements the Counting Sort algorithm. It dynamically allocates memory for counting and output arrays, counts the occurrences of each element, and sorts the input array. The program also includes a driver function to test the sorting functionality with a sample array.

Uploaded by

hemlata dipesh agrawal
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

#include <stdio.

h>

#include <stdlib.h> // For malloc and free

// Function to perform Counting Sort

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


int *count = (int *)calloc(max + 1, sizeof(int)); // Dynamically allocate and initialize to 0

int *output = (int *)malloc(n * sizeof(int)); // Dynamically allocate output array

if (count == NULL || output == NULL) {

printf("Memory allocation failed.\n");

return;

// Store count of each element

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

count[arr[i]]++;
}

// Change count[i] so that count[i] now contains actual position of this character in
output array

for (int i = 1; i <= max; i++) {

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

}
// Build the output array

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

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

count[arr[i]]--;

// Copy the output array to arr, so that arr now contains sorted elements

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


arr[i] = output[i];

free(count); // Free allocated memory

free(output); // Free allocated memory

// Driver program to test the function

int main() {

int arr[] = {4, 2, 2, 8, 3, 3, 1};

int n = sizeof(arr) / sizeof(arr[0]);

// Find the maximum element in the array to determine the range for counting array

int max = arr[0];

for (int i = 1; i < n; i++) {


if (arr[i] > max) {

max = arr[i];

}
printf("Original array: ");

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

printf("%d ", arr[i]);

printf("\n");

countingSort(arr, n, max);

printf("Sorted array: ");

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

printf("%d ", arr[i]);

printf("\n");

return 0;

You might also like