Написание сортировки ведра на С++

В одной книге, которая у меня есть, говорится следующее:

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

б) Прокрутите массив корзины построчно и скопируйте значения обратно в исходный массив. Это называется «сборный пас». Новый порядок предыдущих значений в одномерном массиве — 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];

где x = 1, 10, 100, 1000 и т. д. Я совершенно не понимаю, как это написать сейчас.


c++ bucket sorting algorithm
person Jonathan Dewein    schedule 16.02.2012    source источник
comment
Это должно работать нормально, предполагая, что x == 1, 10, 100, ....   -  person 500 - Internal Server Error    schedule 16.02.2012
comment
Возможно, вы захотите использовать шестнадцатеричные, а не десятичные цифры: сдвиг на 4*n бит и операция И с 0xf кажутся намного более естественными, чем использование вычисления по модулю.   -  person Eugen Rieck    schedule 16.02.2012
comment
@Eugen Rieck и призыв к бою...   -  person crush    schedule 16.02.2012

Ответы (3)


arrow_upward
4
arrow_downward

Вот сортировка ведра на основе информации в вопросе ОП.

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

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

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

person Louis Ricci    schedule 16.02.2012
comment
Я полагаю, вы не можете сделать int bucket[10][max+1];, потому что размер массива в стеке должен быть известен во время компиляции. - person user1234567; 12.12.2014

arrow_upward
1
arrow_downward

В следующем коде для групповой сортировки используются шестнадцатеричные цифры (для 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");

  }
}
person Eugen Rieck    schedule 17.02.2012

arrow_upward
1
arrow_downward

переписывание кода Луи на 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();
            }
        }
    } 
}
person hesham safi    schedule 24.11.2016