Radix sort (Descend) для 8-битных целых, получая отсортированные индексы. Как? - PullRequest
Новая
       35

Radix sort (Descend) для 8-битных целых, получая отсортированные индексы. Как?

0 голосов
/ 17 марта 2019

Использование сортировки Radix (Descend) для получения отсортированных индексов длинного массива состоит из 8-битных целых чисел (uchar).

например, 

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

Вывод: 

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

Я попробовал ссылки ниже, но безуспешно.

Сортировка целых чисел в любой базе (основание)

Сортировка по радикалу

Сортировка по радиксу: по убыванию

1 Ответ

0 голосов
/ 21 марта 2019 
    #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;
}
...