Counting Sort algorithm is used to sort elements of an array, that are placed between a small range. The values can repeat them self. It first counts the number of occurrences of each value, and then calculates the starting index for each value.
// Counting Sort
#include <iostream>
using namespace std;
void countSort(int arrayOfNumbers[], int numberOfElements)
{
int sortedArray[numberOfElements];
int countOccurrences[numberOfElements];
int maxValue = arrayOfNumbers[0];
// Find the max value
for (int i = 1; i < numberOfElements; i++)
{
if (arrayOfNumbers[i] > maxValue)
maxValue = arrayOfNumbers[i];
}
// Set the array with zeros
for (int i = 0; i <= maxValue; ++i)
{
countOccurrences[i] = 0;
}
// Find the number of occurrences
for (int i = 0; i < numberOfElements; i++)
{
countOccurrences[arrayOfNumbers[i]]++;
}
// Add the sum of occurrences
for (int i = 1; i <= maxValue; i++)
{
countOccurrences[i] += countOccurrences[i - 1];
}
for (int i = numberOfElements - 1; i >= 0; i--)
{
sortedArray[countOccurrences[arrayOfNumbers[i]] - 1] = arrayOfNumbers[i];
countOccurrences[arrayOfNumbers[i]]--;
}
// Restore the elements in the original array
for (int i = 0; i < numberOfElements; i++)
{
arrayOfNumbers[i] = sortedArray[i];
}
}
void printElementsOfArray(int arrayOfNumbers[], int numberOfElements)
{
for (int i = 0; i < numberOfElements; i++)
{
cout << arrayOfNumbers[i] << " ";
}
cout << endl;
}
int main()
{
int arrayOfNumbers[] = {0, 5, 4, 2, 1, 5, 3, 2, 0, 1};
int numberOfElements = sizeof(arrayOfNumbers) / sizeof(arrayOfNumbers[0]);
countSort(arrayOfNumbers, numberOfElements);
cout<<"The sorted array is: \n";
printElementsOfArray(arrayOfNumbers, numberOfElements);
return 0;
}
Comments