escritura cubo especie en C++

Question

Un libro que tengo dice esto:

a) colocar cada valor de la matriz unidimensional en una fila de la matriz de cubo basado en los dígitos del valor. Por ejemplo, 97 se coloca en la fila 7, 3 se coloca en la fila 3 y 100 se coloca en la fila 0. Esto se denomina "pase de distribución".

b) Haz un bucle en la matriz de cubetas fila por fila y copia los valores de nuevo a la matriz original. Esto se llama un "pase de recolección". El nuevo orden de los valores anteriores en la matriz unidimensional es 100, 3 y 97.

c) Repita este proceso para cada posición de dígito subsiguiente.

Tengo un montón de problemas tratando de comprender e implementar esto. Hasta ahora tengo:

void b_sort(int sarray[], int array_size) { 
    const int max = array_size; 
    for(int i = 0; i < max; ++i) 
     int array[i] = sarray[i]; 

    int bucket[10][max - 1]; 
} 

estoy pensando que con el fin de clasificarlos por unidades, decenas, centenas, etc., que pueden utilizar esta:

for(int i = 0; i < max; ++i) 
    insert = (array[i]/x) % 10; 
    bucket[insert]; 

donde x = 1, 10, 100, 1000, etc. Estoy totalmente perdido en cómo escribir esto ahora.

Answer 1

Aquí hay una clasificación de depósito basada en la información de la pregunta de OP.

void b_sort(int sarray[], int array_size) { 
    const int max = array_size; 
    // use bucket[x][max] to hold the current count 
    int bucket[10][max+1]; 
    // init bucket counters 
    for(var x=0;x<10;x++) bucket[x][max] = 0; 
    // main loop for each digit position 
    for(int digit = 1; digit <= 1000000000; digit *= 10) { 
     // array to bucket 
     for(int i = 0; i < max; i++) { 
      // get the digit 0-9 
      int dig = (sarray[i]/digit) % 10; 
      // add to bucket and increment count 
      bucket[dig][bucket[dig][max]++] = sarray[i]; 
     } 
     // bucket to array 
     int idx = 0; 
     for(var x = 0; x < 10; x++) { 
      for(var y = 0; y < bucket[x][max]; y++) { 
       sarray[idx++] = bucket[x][y]; 
      } 
      // reset the internal bucket counters 
      bucket[x][max] = 0; 
     } 
    } 
} 

Notas Usando una matriz 2D para el cubo desperdicia una gran cantidad de espacio ... un conjunto de colas/listas por lo general tiene más sentido.

Normalmente no programo en C++ y el código anterior se escribió dentro del navegador web, por lo que pueden existir errores de sintaxis.

Answer 2

El siguiente código utiliza dígitos hexadecimales para una clasificación de categoría (para BITS_PER_BUCKET=4). Por supuesto, está destinado a ser instructivo, no productivo.

#include <assert.h> 
#include <stdio.h> 

#define TEST_COUNT 100 
#define BITS_PER_BUCKET 4 
#define BUCKET_COUNT (1 << BITS_PER_BUCKET) 
#define BUCKET_MASK (BUCKET_COUNT-1) 
#define PASS_COUNT (8*sizeof(int)/BITS_PER_BUCKET) 

int main(int argc, char** argv) { 

    printf("Starting up ..."); 
    assert((PASS_COUNT*BITS_PER_BUCKET) == (8*sizeof(int))); 
    printf("... OK\n"); 

    printf("Creating repeatable very-pseudo random test data ..."); 
    int data[TEST_COUNT]; 
    int x=13; 
    int i; 
    for (i=0;i<TEST_COUNT;i++) { 
    x=(x*x+i*i) % (2*x+i); 
    data[i]=x; 
    } 
    printf("... OK\nData is "); 
    for (i=0;i<TEST_COUNT;i++) printf("%02x, ",data[i]); 
    printf("\n"); 

    printf("Creating bucket arrays ..."); 
    int buckets[BUCKET_COUNT][TEST_COUNT]; 
    int bucketlevel[BUCKET_COUNT]; 
    for (i=0;i<BUCKET_COUNT;i++) bucketlevel[i]=0; 
    printf("... OK\n"); 

    for (i=0;i<PASS_COUNT;i++) { 

    int j,k,l; 

    printf("Running distribution pass #%d/%d ...",i,PASS_COUNT); 
    l=0; 
    for (j=0;j<TEST_COUNT;j++) { 
     k=(data[j]>>(BITS_PER_BUCKET*i)) & BUCKET_MASK; 
     buckets[k][bucketlevel[k]++]=data[j]; 
     l|=k; 
    } 
    printf("... OK\n"); 

    if (!l) { 
     printf("Only zero digits found, sort completed early\n"); 
     break; 
    } 

    printf("Running gathering pass #%d/%d ...",i,PASS_COUNT); 
    l=0; 
    for (j=0;j<BUCKET_COUNT;j++) { 
     for (k=0;k<bucketlevel[j];k++) { 
     data[l++]=buckets[j][k]; 
     } 
     bucketlevel[j]=0; 
    } 
    printf("... OK\nData is "); 
    for (l=0;l<TEST_COUNT;l++) printf("%02x, ",data[l]); 
    printf("\n"); 

    } 
} 

Answer 3

una reescritura del código de Louis en C++ 11 con colas STL.

void bucket_sort(vector<int>& arr){ 
    queue<int> buckets[10]; 
    for(int digit = 1; digit <= 1e9; digit *= 10){ 
     for(int elem : arr){ 
      buckets[(elem/digit)%10].push(elem); 
     } 
     int idx = 0; 
     for(queue<int>& bucket : buckets){ 
      while(!bucket.empty()){ 
       arr[idx++] = bucket.front(); 
       bucket.pop(); 
      } 
     } 
    } 
}