Ordinamento Radix implementato in C++

Question

Sto cercando di migliorare il mio C++ creando un programma che richiederà una grande quantità di numeri tra 1 e 10^6. I bucket che memorizzeranno i numeri in ogni passaggio sono una serie di nodi (dove node è una struct che ho creato contenente un valore e un successivo attributo node).

Dopo aver ordinato i numeri in bucket in base al valore meno significativo, ho la fine di un punto bucket all'inizio di un altro bucket (in modo da poter ottenere rapidamente i numeri memorizzati senza interrompere l'ordine). Il mio codice non ha errori (né di compilazione né di runtime), ma ho colpito un muro riguardo a come sto andando a risolvere le restanti 6 iterazioni (poiché conosco l'intervallo di numeri).

Il problema che sto avendo è che inizialmente i numeri venivano forniti alla funzione radixSort sotto forma di un array int. Dopo la prima iterazione dell'ordinamento, i numeri vengono ora memorizzati nella matrice di strutture. C'è un modo per rielaborare il mio codice in modo da avere solo un ciclo for per le 7 iterazioni, o avrò bisogno di un ciclo for che verrà eseguito una volta, e un altro ciclo al di sotto di esso che verrà eseguito 6 volte prima di tornare completamente ordinato elenco?

#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

Penso che tu stia davvero complicando la tua soluzione. È possibile implementare radix utilizzando la matrice singola ricevuta nell'input, con i bucket in ogni fase rappresentati da una matrice di indici che contrassegna l'indice iniziale di ciascun segmento nell'array 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 overflow del buffer quando i è 9, ma ho omesso l'assegno extra o l'amor di leggibilità; Credo che tu sappia come gestirlo.

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

Answer 2

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 il secondo array tutti gli zeri.

Effettuare un passaggio attraverso l'array di input e utilizzare il valore come indice per incrementare il valore nel secondo array.

Una volta fatto, il secondo passaggio è facile. attraversa il secondo array e ogni elemento ti dice quante volte è apparso il numero nell'array originale. Utilizzare tali informazioni per ripopolare l'array di input .

Answer 3

Per accelerare il processo con una migliore gestione della memoria, creare una matrice per i conteggi che vengono convertiti in indici effettuando un singolo passaggio sull'array. Assegnare un secondo array temporaneo della stessa dimensione dell'array originale e ordinare i due array tra i due array finché l'array non viene ordinato. Se viene eseguito un numero dispari di passaggi di ordinamento radix, alla fine sarà necessario ricopiare l'array temporaneo nell'array originale.

Per accelerare ulteriormente il processo, utilizzare la base 256 anziché la base 10 per lo smistamento radix. Ciò richiede solo 1 passaggio di scansione per creare la matrice e 4 passaggi di ordinamento radix per eseguire 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); 
}