Radix Sort implementato in C ++

Question

Sto cercando di migliorare il mio C ++ con la creazione di un programma che avrà una grande quantità di numeri compresi tra 1 e 10 ^ 6. I secchi che memorizzerà i numeri in ogni passaggio è un array di nodi (dove nodo è una struct ho creato contenente un valore e un attributo nodo successivo).

Dopo la cernita dei numeri in secchi in base al valore meno significativo, ho la fine di un punto secchio per l'inizio di un altro secchio (in modo che io possa ottenere rapidamente i numeri che sono memorizzati senza interrompere l'ordine). Il mio codice non ha errori (sia compilazione o di esecuzione), ma ho colpito un muro per quanto riguarda come ho intenzione di risolvere i restanti 6 iterazioni (dal momento che so l'intervallo di numeri).

Il problema che sto avendo è che inizialmente i numeri sono stati forniti alla funzione radix sort sotto forma di una matrice int. Dopo la prima iterazione del smistamento, i numeri sono memorizzate nella matrice di strutture. C'è un modo che io possa rielaborare il mio codice in modo da avere un solo ciclo for per i 7 iterazioni, o avrò bisogno di uno per il ciclo che verrà eseguito una volta, e un altro ciclo di sotto di essa che verrà eseguito 6 volte prima di restituire il tutto ordinato elencare?

#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

Credo che tu stia gravemente overcomplicating la vostra soluzione. È possibile implementare radice usando l'singola matrice ricevuto in ingresso, con i secchi in ogni passaggio rappresentato da una serie di indici che segnano l'indice iniziale di ciascun segmento della matrice di input.

In realtà, si potrebbe anche farlo in modo ricorsivo:

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

Naturalmente buckets[i+1] - buckets[i] causerà un buffer overflow quando i è 9, ma ho omesso l'assegno extra o l'amor di leggibilità; Mi fido di te sa come gestire questo.

Con questo, basta chiamare radixSort(testcases, sizeof(testcases) / sizeof(testcases[0]), 0) e l'array deve essere ordinato.

Answer 2

Per accelerare il processo con una migliore gestione della memoria, creare una matrice per i conteggi che vengono convertiti in indici effettuando un unico passaggio sulla matrice. Allocare una seconda matrice temporanea la stessa dimensione dell'array originale e ordinamento digitale tra i due array fino matrice è ordinata. Se passa viene eseguito un numero dispari di ordinamento digitale, l'array temperatura dovrà essere copiato dietro alla matrice originale alla fine.

Per accelerare ulteriormente il processo, utilizzare basamento 256 invece di base 10 per l'ordinamento digitale. Questo richiede solo 1 pass scansione per creare la matrice e 4 ordinamento digitale passa per fare l'ordinamento. Esempio di codice:

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

Dal momento che i valori sono interi nel range di 0 ... 1.000.000

È possibile creare un array int di dimensione di 1.000.001, e fare il tutto in due passaggi

Init secondo array a tutti zeri.

Fare un passaggio attraverso l'array di input, e utilizzare il valore come pedice incrementare il valore del secondo array.

Una volta fatto che poi il secondo passaggio è facile. a piedi attraverso il secondo array, e ogni elemento indica il numero di volte che il numero è apparso nella matrice originale. Utilizzare tali informazioni per ripopolare la matrice di ingresso.