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

31 afișare0 comentariu

### Postări recente

Afișează-le pe toate

#### Maximum Length Chain of Pairs in C++

© 2018 by The Art Of Coding. by Oana Unciuleanu

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