Clase de raíz implementada en C++

Question

Estoy tratando de mejorar mi C++ creando un programa que tomará una gran cantidad de números entre 1 y 10^6. Los depósitos que almacenarán los números en cada pasada son una matriz de nodos (donde el nodo es una estructura que he creado que contiene un valor y un próximo atributo de nodo).

Después de clasificar los números en cubos de acuerdo con el valor menos significativo, tengo el final de un punto de depósito al comienzo de otro cubo (para poder obtener rápidamente los números sin interrumpir el orden). Mi código no tiene errores (ya sea compilación o tiempo de ejecución), pero me he topado con una pared con respecto a cómo voy a resolver las 6 iteraciones restantes (ya que conozco el rango de números).

El problema que estoy teniendo es que inicialmente los números se suministraron a la función radixSort en forma de una matriz int. Después de la primera iteración de la clasificación, los números ahora se almacenan en la matriz de estructuras. ¿Hay alguna forma de que pueda volver a trabajar mi código para que tenga solo un ciclo for para las 7 iteraciones, o necesitaré uno para el ciclo que se ejecutará una vez, y otro ciclo debajo de él que se ejecutará 6 veces antes de devolverlo completamente ordenado? ¿lista?

#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

Pienso que usted es complicar seriamente su solución. Puede implementar radix utilizando la única matriz recibida en la entrada, con los intervalos en cada paso representados por una matriz de índices que marcan el índice de inicio de cada segmento en la matriz de entrada.

De hecho, incluso se podría hacerlo de forma recursiva:

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

Por supuesto buckets[i+1] - buckets[i] causarán un desbordamiento de búfer cuando i es 9, pero se omite la comprobación adicional o bien de la legibilidad; Confío en que sepas cómo manejar eso.

Con eso, solo tiene que llamar al radixSort(testcases, sizeof(testcases)/sizeof(testcases[0]), 0) y su matriz debe ser ordenada.

Answer 2

Debido a que sus valores son enteros en el rango de 0 ... 1000000

Puede crear una matriz int del tamaño de 1.000.001, y hacerlo todo en dos pasadas

Init la segunda matriz de todos los ceros

Haga un pase a través de su matriz de entrada, y use el valor como un subíndice para incrementar el valor en la segunda matriz.

Una vez que haces eso, entonces el segundo pase es fácil. caminar a través de la segunda matriz, y cada elemento le dice cuántas veces ese número apareció en la matriz original. Use esa información para volver a llenar su matriz de entrada.

Answer 3

Para acelerar el proceso con una mejor gestión de memoria, cree una matriz para los recuentos que se convierten en índices haciendo una sola pasada sobre la matriz. Asigne una segunda matriz temporal del mismo tamaño que la matriz original, y radix ordene entre las dos matrices hasta que la matriz esté ordenada. Si se realiza un número impar de pasadas de clasificación de radix, la matriz temporal tendrá que ser copiada de nuevo a la matriz original al final.

Para acelerar aún más el proceso, utilice la base 256 en lugar de la base 10 para la ordenación de radix. Esto solo requiere 1 pase de exploración para crear la matriz y 4 pasos de clasificación de raíz para hacer el ordenamiento.Código de ejemplo:

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