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

Question

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?

Won't arr[i]/exp always work out as zero? All of your arr elements are less than exp=10, and it's integer division. And I don't understand your build-output loop: when should it decide to move on to the next element in count? — Rup
– Rup, Commented Mar 20, 2014 at 1:47
Aw, I called it with countsort2(b,10,1) and it sorted all of it! How would I go about sorting numbers bigger than single digits? — user2796815
– user2796815, Commented Mar 20, 2014 at 1:51

Dexters · Accepted Answer · 2014-03-20 02:04:54Z

1

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

answered Mar 20, 2014 at 2:04

Dexters

2,5036 gold badges39 silver badges61 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

rcgldr · Accepted Answer · 2014-03-20 06:42:22Z

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

}

Collectives™ on Stack Overflow

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

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related