Письменное ведро сортировка в C ++
Вопрос
Книга, которую я имею, говорит об этом:
а) Поместите каждое значение одномерного массива в строку массива ведра на основе одной цифры значения. Например, 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 и т. Д. Я полностью потерян в том, как написать это сейчас.
Решение
Вот сортировка ведра, основанная на информации в вопросе 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;
}
}
}
Заметки Использование двухмерного массива для ведра тратит много места ... массив очередей/списков обычно имеет больше смысла.
Обычно я не программирую в C ++, и приведенный выше код был записан в веб -браузере, поэтому могут существовать ошибки синтаксиса.
Другие советы
Следующий код использует шестнадцатеричные цифры для сортировки ведра (для 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");
}
}
Переписывание кода Луи в 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();
}
}
}
}