Radix Trier implémenté en C ++

Question

Je suis en train d'améliorer mon C ++ en créant un programme qui prendra une grande quantité de nombres compris entre 1 et 10 ^ 6. Les godets qui stocker les nombres dans chaque passage est un réseau de noeuds (noeud où est créé un struct I contenant une valeur et un attribut de noeud suivant).

Après le tri des numéros dans les godets selon la moins grande valeur, je l'extrémité d'un point de seau pour le début d'un autre seau (pour que je puisse obtenir rapidement les nombres étant mémorisés sans perturber l'ordre). Mon code n'a pas d'erreurs (soit la compilation ou de l'exécution), mais je l'ai frappé un mur sur la façon dont je vais résoudre les 6 itérations restantes (car je sais que la gamme des nombres).

Le problème que je vais avoir est que d'abord les chiffres ont été fournis à la fonction sous la forme tri par base d'un tableau int. Après la première itération du tri, les numéros sont désormais stockés dans le tableau de struct. Est-il possible que je puisse retravailler mon code pour que j'ai juste une boucle pour les 7 itérations, ou ai-je besoin d'une boucle qui se déroulera une fois, et une autre boucle en dessous qui se déroulera 6 fois avant de retourner le complètement trié liste?

#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

Je pense que vous êtes sérieusement votre solution trop compliquer. Vous pouvez implémenter radix en utilisant le tableau unique reçu dans l'entrée, avec les seaux à chaque étape représentée par un tableau d'indices qui marquent l'indice de départ de chaque seau dans le tableau d'entrée.

En fait, vous pouvez même le faire récursive:

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

Bien sûr buckets[i+1] - buckets[i] provoquera un débordement de mémoire tampon lorsque i est 9, mais j'omis la vérification supplémentaire ou à cause de la lisibilité; Je crois que vous savez comment gérer cela.

Avec cela, il vous suffit d'appeler radixSort(testcases, sizeof(testcases) / sizeof(testcases[0]), 0) et votre tableau, triez.

Answer 2

Pour accélérer le processus avec une meilleure gestion de la mémoire, créer une matrice pour les chefs d'accusation qui sont converties en indices en faisant un seul passage sur le tableau. Allouer un second réseau temporaire de la même taille que la matrice d'origine, et le tri par base entre les deux ensembles jusqu'à ce que le tableau est trié. Si un nombre impair de tri radix passes est effectué, le tableau de température devra être recopiée sur le tableau original à la fin.

Pour accélérer encore le processus, utiliser la base 256 à la place de la base 10 pour le tri de base. Cela ne prend que 1 passe de balayage pour créer la matrice et 4 radix passe sorte à faire le tri. Exemple de code:

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

Étant donné que vos valeurs sont ints dans la plage de 0 ... 1000000

Vous pouvez créer un tableau int de la taille 1.000.001, et faire le tout en deux passes

Init le deuxième réseau à zéro.

Faire une passe dans votre tableau d'entrée, et utiliser la valeur comme indice pour incrémenter la valeur dans le second réseau.

Une fois que vous le faites alors la deuxième passe est facile. marcher à travers le second réseau, et chaque élément vous indique combien de fois que nombre est apparu dans le tableau original. Utilisez ces informations pour repeupler votre tableau d'entrée.