Search code examples
sortingradix-sort8-bit

Radix sort(Descend) for 8-bit integers, getting sorted indices. How?


Using Radix sort(Descend) to get sorted Indices of a long array consists of 8-bit integers(uchar).

e.g.

uchar data[10] = {2,8,6,25,255,23,96,102,235,0}; // actual one has million values
size_t n = 10;

int index[n];   std::iota(std::begin(index), std::end(index), 0); // Initialise indices

radixSort(std::begin(index), n, &data[0]);  // TARGET FUNCTION
return index; // OUTPUT - Sorted index

Output:

{4, 8, 7, 6, 3, 5, 1, 2, 0, 9}

I tried below links but didn't succeed.

Sort integers in any base (radix)

Radix Sort

Radix Sort: Descending


Solution

  •     #include <opencv2/opencv.hpp>
    
        void SortRadixReturnIndexes2(unsigned char inputArray[], int length, int outputIndexArray[])
    {
        const int numberOfBins = 256;
        int count[numberOfBins];
        int startOfBin[numberOfBins];
    
        for (int i = 0; i < numberOfBins; i++)
            count[i] = 0;
        for (int current = 0; current < length; current++)    // Scan Key array and count the number of times each digit value appears - i.e. size of each bin
            count[inputArray[current]]++;
    
        startOfBin[0] = 0;
        for (int i = 1; i < numberOfBins; i++)
            startOfBin[i] = startOfBin[i - 1] + count[i - 1];
    
        for (int current = 0; current < length; current++)
        {
            uchar digit = inputArray[current];
            int index = startOfBin[digit]++;
            outputIndexArray[length - 1 - index] = current;          // current location is the current index within the input array
        }
    
    }
    
    #include <opencv2/opencv.hpp>
    #include <iostream>
    #include <algorithm>
    #include <numeric>
    
    using namespace cv;
    
    int main()
    {
        uchar data[8] = {170,45,75,90,2,24,255,66};
        const int size = 8;
    
        int idxNew[size];   std::iota(std::begin(idxNew), std::end(idxNew), 0); // Initialise indices
    //std::sort(std::begin(idxNew), std::end(idxNew), std::bind(compare2, _1, _2, depth)); // sorting depths
    SortRadixReturnIndexes2(data, size, idxNew);
        // After SortRadixReturnIndexes2 execution idxNew is the descend sorted indices and data is unchanged
        return 0;
    }