Radix Ordenar implementado en C ++

Question

Estoy tratando de mejorar mi C ++ mediante la creación de un programa que tendrá una gran cantidad de números entre 1 y 10 ^ 6. Los cubos que almacenarán los números en cada pase es una matriz de nodos (donde nodo es un struct creé que contiene un valor y un siguiente atributo nodo).

Después de la clasificación de los números en los cubos de acuerdo con el valor menos significativo, tengo el final de un punto de cubo para el comienzo de otro cubo (de modo que pueda obtener rápidamente los números que se almacenan sin interrumpir la orden). Mi código no tiene errores (compilar o en tiempo de ejecución), pero he golpeado una pared con respecto a cómo voy a resolver los 6 iteraciones restantes (ya sé que el rango de números).

El problema que estoy teniendo es que inicialmente los números fueron suministrados a la función Ordenamiento Radix en forma de una matriz de int. Después de la primera iteración de la clasificación, los números se almacenan ahora en la matriz de estructuras. ¿Hay alguna manera de que podía volver a trabajar mi código de modo que tenga un solo bucle for para los 7 iteraciones, o necesitaré un bucle que se ejecutará una vez, y otra vuelta por debajo de ella que se ejecutará 6 veces antes de devolver el completamente ordenados 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

Creo que estás complicar seriamente su solución. Puede implementar radix utilizando la matriz sola recibido en la entrada, con los cubos en cada paso representado por una serie de índices que marcan el índice de inicio de cada cubo en la matriz de entrada.

De hecho, incluso se podría hacer 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 omite la comprobación adicional o bien de la legibilidad; Confío en que sabe cómo manejar eso.

Con esto, sólo hay que llamar radixSort(testcases, sizeof(testcases) / sizeof(testcases[0]), 0) y la matriz debe ordenarse.

Answer 2

Para acelerar el proceso con una mejor gestión de memoria, crear una matriz para los recuentos que se convierten en índices haciendo una sola pasada sobre la matriz. Asignar una segunda matriz temp del mismo tamaño que la matriz original, y Radix sort entre las dos matrices hasta que se ordena la matriz. Si pases se realiza un número impar de radix tipo, entonces tendrá que ser copiado de nuevo a la matriz original en el extremo de la matriz temp.

Para acelerar aún más el proceso, de uso base 256 en lugar de la base 10 para el radix tipo. Esto sólo toma 1 pasada de barrido para crear la matriz y 4 radix especie pasa a hacer el estilo. 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);
}

Answer 3

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 para todos ceros.

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

Una vez hecho eso, entonces el segundo paso es fácil. caminar a través de la segunda matriz, y cada elemento que indica el número de veces que se número apareció en la matriz original. Utilizar esa información para repoblar su matriz de entrada.