Caută
  • oanaunciuleanu

Counting Sort Algorithm in C++



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;
}

© 2018 by The Art Of Coding. by Oana Unciuleanu

This site was designed with the
.com
website builder. Create your website today.
Start Now