# Counting Sort confusion. Not sorting array (c++)

I was researching counting sort and decided to try an algorithm i found online. Though, it doesn't seem to actually sort my array.

void countSort2(int arr[], int n, int exp) { int *output = new int[n]; // output array int i, count[10] = {0}; // Store count of occurrences in count[] for (i = 0; i < n; i++) count[ (arr[i]/exp)%10 ]++; // Change count[i] so that count[i] now contains actual position of // this digit in output[] for (i = 1; i < 10; i++) count[i] += count[i - 1]; // Build the output array for (i = n - 1; i >= 0; i--) { output[count[ (arr[i]/exp)%10 ] - 1] = arr[i]; count[ (arr[i]/exp)%10 ]--; } // Copy the output array to arr[], so that arr[] now // contains sorted numbers according to curent digit for (i = 0; i < n; i++) arr[i] = output[i]; } int main() { int b[10] = {4,3,2,1,6,7,8,9,7,6}; countSort2(b,10,10); int i = 0; while(i<10) { cout<<b[i]<<endl; i++; }

When the array is printed out, I get: "4,3,2,1,6,7,8,9,7,6". Am I calling the function wrong?

## Answers

This is how you call the method [1]..

10 is the number of elements...

int main() { int b[10] = {14,23,22,11,66,67,58,49,17,16}; countSort2(b,10,1); countSort2(b,10,10); int i = 0; while(i<10) { cout<<b[i]<<endl; i++; } return 0; }

This is a radix sort that sorts an array by a decimal digit. The sort is done from least significant digit to most significant digit. This means a series of calls with exp = 1, 10, 100, 1000, 10000, ... .

Here is an example of a radix sort that sorts an array of 64 bit unsigned integers by the bytes in the integers, from least significant to most significant. In this example, the temporary array is passed as a parameter to RadixSort():

typedef unsigned __int64 UI64; typedef unsigned __int64 * PUI64; PUI64 RadixSort(PUI64 pData, PUI64 pTemp, size_t count) { size_t mIndex[8][256] = {0}; // index matrix PUI64 pDst, pSrc, pTmp; size_t i,j,m,n; UI64 u; for(i = 0; i < count; i++){ // generate histograms u = pData[i]; for(j = 0; j < 8; j++){ mIndex[j][(size_t)(u & 0xff)]++; u >>= 8; } } for(j = 0; j < 8; j++){ // convert to indices n = 0; for(i = 0; i < 256; i++){ m = mIndex[j][i]; mIndex[j][i] = n; n += m; } } pDst = pTemp; // radix sort pSrc = pData; for(j = 0; j < 8; j++){ for(i = 0; i < count; i++){ u = pSrc[i]; m = (size_t)(u >> (j<<3)) & 0xff; pDst[mIndex[j][m]++] = u; } pTmp = pSrc; pSrc = pDst; pDst = pTmp; } return(pSrc);

}