Radix Sort implémenté en C++

Question

J'essaye d'améliorer mon C++ en créant un programme qui prendra une grande quantité de nombres entre 1 et 10^6. Les compartiments qui stockent les nombres dans chaque passage sont un tableau de noeuds (où noeud est une structure que j'ai créée contenant une valeur et un attribut de noeud suivant). Après avoir trié les nombres dans des compartiments selon la valeur la moins significative, j'ai la fin d'un point de seau au début d'un autre seau (de sorte que je puisse rapidement stocker les nombres sans perturber l'ordre). Mon code n'a pas d'erreurs (compilation ou exécution), mais j'ai frappé un mur concernant la façon dont je vais résoudre les 6 itérations restantes (puisque je connais la plage de nombres).

Le problème que j'ai, c'est qu'au début, les nombres ont été fournis à la fonction radixSort sous la forme d'un tableau int. Après la première itération du tri, les nombres sont maintenant stockés dans le tableau des structures. Est-il possible que je puisse retravailler mon code de sorte que je n'ai qu'une seule boucle pour les 7 itérations, ou aurai-je besoin d'une boucle qui sera exécutée une fois, et une autre qui sera exécutée 6 fois avant de renvoyer complètement le 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 surchargez gravement votre solution. Vous pouvez implémenter radix en utilisant le tableau unique reçu dans l'entrée, avec les compartiments dans chaque étape représentée par un tableau d'indices qui marquent l'index de départ de chaque compartiment 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 le chèque 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 doit être trié.

Answer 2

É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 second tableau à tous les zéros.

Effectuez un passage dans votre tableau d'entrée et utilisez la valeur pour incrémenter la valeur dans le second tableau.

Une fois que vous faites cela, la deuxième passe est facile. Parcourez le deuxième tableau et chaque élément vous indique combien de fois le numéro est apparu dans le tableau d'origine. Utilisez cette information pour repeupler votre tableau d'entrée.

Answer 3

Pour accélérer le processus avec une meilleure gestion de la mémoire, créez une matrice pour les comptages convertis en index en effectuant un seul passage sur la baie. Allouer un second tableau temporaire de la même taille que le tableau d'origine et trier les bases entre les deux tableaux jusqu'à ce que le tableau soit trié. Si un nombre impair de passes de tri radix est effectué, alors le tableau temporaire devra être recopié dans le tableau original à la fin.

Pour accélérer encore le processus, utilisez la base 256 au lieu de la base 10 pour le tri radix. Cela prend seulement 1 passe de balayage pour créer la matrice et 4 passes de tri radix pour 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); 
}