Écrit seau de tri en c++

Un livre que j'ai dit ceci:

a) Placez chaque valeur du tableau à une dimension dans une ligne de la seau tableau basé sur la valeur du chiffre des unités. Par exemple, 97 est placé dans la ligne 7, 3 est placé dans la ligne 3, et 100 est placé dans la ligne 0. Ceci est appelé une "distribution de passe."

b) de la Boucle à travers le seau tableau ligne par ligne, et de copier les valeurs sur le tableau d'origine. Ceci est appelé un "rassemblement passer." Le nouvel ordre des valeurs précédentes dans le tableau à une dimension est de 100, 3 et 97.

c) Répétez ce processus pour chaque chiffre position.

J'ai beaucoup de mal à essayer de comprendre et de mettre en œuvre cette. Pour l'instant j'ai:

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

Je pense que, dans le but de les trier par des unités, des dizaines, des centaines, etc, je peux utiliser ceci:

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

où x = 1, 10, 100, 1000, etc. Je suis totalement perdu sur la façon d'écrire maintenant.

int get_digit(int number, int digit) { return number/int((std::pow(10.0,digit))%10;}
Qui devrait fonctionner correctement, en supposant que x == 1, 10, 100, ....
Vous pouvez utiliser sortilège de chiffres, pas de chiffres décimaux: Changement de 4*n bits et ANDing avec 0xf semble beaucoup plus naturel que d'utiliser un modulo de calcul.
Rieck et un appel à la pow...

OriginalL'auteur Jonathan Dewein | 2012-02-16

  1. 3

    Voici un seau de tri basé sur les infos dans les OP question.

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

    Notes à l'Aide d'un tableau 2d pour le seau gaspille beaucoup d'espace... un tableau de files d'attente/listes habituellement plus de sens.

    Je ne suis pas normalement programme en C++ et le code ci-dessus a été écrit dans le navigateur web, de sorte que les erreurs de syntaxe peuvent exister.

    vous pouvez maintenant utiliser les ideone.com pour la programmation à l'intérieur du navigateur web
    Je suppose que vous ne pouvez pas faire int bucket[10][max+1]; parce que la taille d'un tableau sur la pile doit être connu au moment de la compilation.

    OriginalL'auteur Louis Ricci

  2. 1

    Le code suivant utilise chiffres hexadécimaux pour un seau de tri (pour BITS_PER_BUCKET=4). Bien sûr, il est destiné à être instructif, pas productif.

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

    OriginalL'auteur Eugen Rieck

  3. 1

    une réécriture de Louis du code en C++11 STL files d'attente.

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

    OriginalL'auteur hesham safi