Сортировка по основанию, реализованная на C ++

Question

Я пытаюсь улучшить свой C ++, создав программу, которая будет принимать большое количество чисел от 1 до 10 ^ 6.Сегменты, в которых будут храниться числа на каждом проходе, представляют собой массив узлов (где node - это созданная мной структура, содержащая значение и атрибут next node).

После сортировки чисел по сегментам в соответствии с наименее значимым значением у меня конец одного сегмента указывает на начало другого сегмента (чтобы я мог быстро получить сохраняемые числа, не нарушая порядок).В моем коде нет ошибок (ни при компиляции, ни во время выполнения), но я столкнулся с проблемой относительно того, как я собираюсь решить оставшиеся 6 итераций (поскольку я знаю диапазон чисел).

Проблема, с которой я столкнулся, заключается в том, что изначально числа были переданы в функцию RadixSort в виде массива int.После первой итерации сортировки числа теперь сохраняются в массиве структур.Есть ли какой-нибудь способ, которым я мог бы переработать свой код так, чтобы у меня был только один цикл for для 7 итераций, или мне понадобится один цикл for, который будет выполняться один раз, и еще один цикл под ним, который будет выполняться 6 раз, прежде чем вернуть полностью отсортированный список?

#include <iostream>
#include <math.h>
using namespace std;

struct node
{
    int value;
    node *next; 
};

//The 10 buckets to store the intermediary results of every sort
node *bucket[10];
//This serves as the array of pointers to the front of every linked list
node *ptr[10];
//This serves as the array of pointer to the end of every linked list
node *end[10];
node *linkedpointer;
node *item;
node *temp;

void append(int value, int n)
{
    node *temp; 
    item=new node;
    item->value=value;
    item->next=NULL;
    end[n]=item;
    if(bucket[n]->next==NULL)
    {
        cout << "Bucket " << n << " is empty" <<endl;
        bucket[n]->next=item;
        ptr[n]=item;
    }
    else
    {
        cout << "Bucket " << n << " is not empty" <<endl;
        temp=bucket[n];
        while(temp->next!=NULL){
            temp=temp->next;
        }
        temp->next=item;
    }
}

bool isBucketEmpty(int n){
    if(bucket[n]->next!=NULL)
        return false;
    else
        return true;
}
//print the contents of all buckets in order
void printBucket(){
    temp=bucket[0]->next;
    int i=0;
    while(i<10){
        if(temp==NULL){
            i++;
            temp=bucket[i]->next;                       
        }
        else break;

    }
    linkedpointer=temp;
    while(temp!=NULL){
        cout << temp->value <<endl;
        temp=temp->next;
    }
}

void radixSort(int *list, int length){
    int i,j,k,l;
    int x;
    for(i=0;i<10;i++){
        bucket[i]=new node;
        ptr[i]=new node;
        ptr[i]->next=NULL;
        end[i]=new node;
    }
    linkedpointer=new node;

    //Perform radix sort
    for(i=0;i<1;i++){
        for(j=0;j<length;j++){          
            x=(int)(*(list+j)/pow(10,i))%10;            
            append(*(list+j),x);
            printBucket(x); 
        }//End of insertion loop
        k=0,l=1;

        //Linking loop: Link end of one linked list to the front of another
        for(j=0;j<9;j++){
            if(isBucketEmpty(k))
                k++;
            if(isBucketEmpty(l) && l!=9)
                l++;
            if(!isBucketEmpty(k) && !isBucketEmpty(l)){
                end[k]->next=ptr[l];
                k++;
                if(l!=9) l++;   
            }

        }//End of linking for loop

        cout << "Print results" <<endl;
        printBucket();

        for(j=0;j<10;j++)
            bucket[i]->next=NULL;                       
        cout << "End of iteration" <<endl;
    }//End of radix sort loop
}

int main(){
    int testcases,i,input;
    cin >> testcases;
    int list[testcases];
    int *ptr=&list[0];
    for(i=0;i<testcases;i++){
        cin>>list[i];
    }

    radixSort(ptr,testcases);
    return 0;
}

Answer 1

Я думаю, что вы сильно усложняете свое решение.Вы можете реализовать radix, используя единый массив, полученный на входных данных, при этом сегменты на каждом шаге представлены массивом индексов, которые отмечают начальный индекс каждого сегмента во входном массиве.

На самом деле, вы могли бы даже сделать это рекурсивно:

// Sort 'size' number of integers starting at 'input' according to the 'digit'th digit
// For the parameter 'digit', 0 denotes the least significant digit and increases as significance does
void radixSort(int* input, int size, int digit)
{
    if (size == 0)
        return;

    int[10] buckets;    // assuming decimal numbers

    // Sort the array in place while keeping track of bucket starting indices.
    // If bucket[i] is meant to be empty (no numbers with i at the specified digit),
    // then let bucket[i+1] = bucket[i]

    for (int i = 0; i < 10; ++i)
    {
        radixSort(input + buckets[i], buckets[i+1] - buckets[i], digit+1);
    }
}

Конечно buckets[i+1] - buckets[i] вызовет переполнение буфера, когда i равно 9, но я опустил дополнительную проверку ради удобства чтения;Я надеюсь, ты знаешь, как с этим справиться.

После этого вам просто нужно позвонить radixSort(testcases, sizeof(testcases) / sizeof(testcases[0]), 0) и ваш массив должен быть отсортирован.

Answer 2

Чтобы ускорить процесс за счет лучшего управления памятью, создайте матрицу для подсчетов, которые преобразуются в индексы путем выполнения одного прохода по массиву.Выделите второй временный массив того же размера, что и исходный массив, и производите сортировку по основанию между двумя массивами до тех пор, пока массив не будет отсортирован.Если выполняется нечетное число проходов сортировки по основанию, то в конце потребуется скопировать временный массив обратно в исходный массив.

Чтобы еще больше ускорить процесс, используйте базу 256 вместо базы 10 для сортировки по основанию.Для создания матрицы требуется всего 1 проход сканирования и 4 прохода сортировки по радиусу, чтобы выполнить сортировку.Пример кода:

typedef unsigned int uint32_t;

uint32_t * RadixSort(uint32_t * a, size_t count)
{
size_t mIndex[4][256] = {0};            // count / index matrix
uint32_t * b = new uint32_t [COUNT];    // allocate temp array
size_t i,j,m,n;
uint32_t u;
    for(i = 0; i < count; i++){         // generate histograms
        u = a[i];
        for(j = 0; j < 4; j++){
            mIndex[j][(size_t)(u & 0xff)]++;
            u >>= 8;
        }       
    }
    for(j = 0; j < 4; j++){             // convert to indices
        m = 0;
        for(i = 0; i < 256; i++){
            n = mIndex[j][i];
            mIndex[j][i] = m;
            m += n;
        }       
    }
    for(j = 0; j < 4; j++){             // radix sort
        for(i = 0; i < count; i++){     //  sort by current lsb
            u = a[i];
            m = (size_t)(u>>(j<<3))&0xff;
            b[mIndex[j][m]++] = u;
        }
        std::swap(a, b);                //  swap ptrs
    }
    delete[] b;
    return(a);
}

Answer 3

Поскольку ваши значения являются целыми числами в диапазоне 0 ...1,000,000

Вы можете создать массив int размером 1 000 001 и выполнить все это за два прохода

Инициализируйте второй массив со всеми нулями.

Выполните проход по вашему входному массиву и используйте значение в качестве нижнего индекса для увеличения значения во втором массиве.

Как только вы сделаете это, второй проход будет легким.пройти через второй массив, и каждый элемент говорит вам сколько раз говорил, что номер появился в исходном массиве.Используйте эту информацию для повторного заполнения вашего входного массива.