Дать ведро сортировка в C++

Question

книги у меня есть говорит, что это:

а) Поместите каждое значение одномерного массива в строку массива ковшей на основе разряда единиц Значения в. Например, 97 помещается в строку 7, 3 помещается в строку 3, а 100 помещается в строку 0. Это называется «проходом распространения».

b) Прокрутите массив массива по строкам и скопируйте значения обратно в исходный массив. Это называется «сбором». Новый порядок предыдущих значений в одномерной матрице равен 100, 3 и 97.

c) Повторите этот процесс для каждого последующего положения цифр.

У меня много проблем, пытаясь понять и реализовать это. До сих пор у меня есть:

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

Я имею в виду, что для того, чтобы отсортировать их единицами, десятки, сотни, и т.д., я могу использовать это:

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

где х = 1, 10, 100, 1000 и т. Д. Я полностью потерял, как написать это сейчас.

Answer 1

Вот сортимент ковша, основанный на информации в вопросе ОП.

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

Примечание Использование 2d массива для ведра тратит много места ... массив очередей/списки обычно имеет больше смысла.

Обычно я не программирую на C++, и приведенный выше код был написан внутри веб-браузера, поэтому могут существовать синтаксические ошибки.

Answer 2

В следующем коде используются шестнадцатеричные цифры для сортировки ковша (для BITS_PER_BUCKET=4). Конечно, это должно быть поучительным, а не продуктивным.

#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

переписать код Луи в C++ 11 с очередями 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(); 
      } 
     } 
    } 
}