Counting Sort C

Counting Sort is an algorithm used to sort elements in an array based on their numeric values. It works by counting the occurrences of each unique element in the array and then using that information to determine the correct position of each element in the sorted output array.

The steps for performing Counting Sort in C are as follows:

1. Find the maximum element in the array.
2. Create a count array with a size equal to the maximum element plus one.
3. Initialize all elements of the count array to 0.
4. Traverse the input array and increment the count of each element in the count array.
5. Modify the count array by adding the count of the previous element to the current element.
6. Create an output array with the same size as the input array.
7. Traverse the input array from the last element to the first.
8. Find the index of each element in the count array and place the element in the corresponding index of the output array.
9. Decrement the count of the element in the count array.
10. The output array now contains the sorted elements.

Here is an example implementation of Counting Sort in C:

#include <stdio.h>

void countingSort(int array[], int size) {
  int max = array[0];
  for (int i = 1; i < size; i++) {
    if (array[i] > max)
      max = array[i];
  }

  int count[max + 1];
  for (int i = 0; i <= max; ++i)
    count[i] = 0;

  for (int i = 0; i < size; i++)
    count[array[i]]++;

  for (int i = 1; i <= max; i++)
    count[i] += count[i - 1];

  int output[size];
  for (int i = size - 1; i >= 0; i--) {
    output[count[array[i]] - 1] = array[i];
    count[array[i]]--;
  }

  for (int i = 0; i < size; i++)
    array[i] = output[i];
}

void printArray(int array[], int size) {
  for (int i = 0; i < size; i++)
    printf("%d ", array[i]);
  printf("\n");
}

int main() {
  int array[] = {4, 2, 2, 8, 3, 3, 1};
  int size = sizeof(array) / sizeof(array[0]);

  printf("Original array: ");
  printArray(array, size);

  countingSort(array, size);

  printf("Sorted array: ");
  printArray(array, size);

  return 0;
}

This implementation of Counting Sort sorts an array of integers in ascending order. It first finds the maximum element in the array, then creates a count array to store the count of each element. It then modifies the count array to store the position of each element in the sorted output array. Finally, it creates the output array and fills it with the sorted elements by traversing the input array in reverse order.