Как заставить алгоритм BucketSort работать?
Я пытаюсь создать алгоритм сортировки в C ++, но он совсем не работает. При каждом запуске в массив добавляется много новых чисел, часто очень больших, например, миллиардов. Кто-нибудь знает почему это? Вот код — (обратите внимание, что я передаю массив размером 100 со случайными числами от 0 до ~ 37000, и что функция сортировки вставки полностью функциональна и проверена несколько раз)
Было бы очень признательно, если бы кто-то мог указать, что не так.
void bucketSort(int* n, int k)
{
int c = int(floor(k/10)), s = *n, l = *n;
for(int i = 0; i < k; i++) {
if(s > *(n + i)) s = *(n + i);
else if(l < *(n + i)) l = *(n + i);
}
int bucket[c][k + 1];
for(int i = 0; i < c; i++) {
bucket[i][k] = 0;
}
for(int i = 0; i < k; i++) {
for(int j = 0; j < c; j++) {
if(*(n + i) >= (l - s)*j/c) {
continue;
} else {
bucket[j][bucket[j][k]++] = *(n + i);
break;
}
}
}
for(int i = 0; i < c; i++) {
insertionSort(&bucket[i][0], k);
}
}
Решение
Эта строка не компилируется. int bucket[c][k + 1];
Я думаю, что проблема с тобой в индексах ведра. Эта часть здесь
for(int j = 0; j < c; j++) {
if(*(n + i) >= (l - s)*j/c) {
continue;
} else {
bucket[j][bucket[j][k]++] = *(n + i);
break;
}
}
не делает эквивалент:
insert n[i] into bucket[ bucketIndexFor( n[i]) ]
Сначала он получает индекс на единицу. Из-за этого это также пропускает разрыв для чисел для последнего ведра. Также введена небольшая ошибка, потому что при расчете индекса используется диапазон [0,l-s] вместо [s,l], которые только одинаковы, если s равняется 0,
Когда я пишу bucketIndex как:
int bucketIndex( int n, int c, int s, int l )
{
for(int j = 1; j <= c; j++) {
if(n > s + (l-s)*j/c) {
continue;
} else {
return j-1;
}
}
return c-1;
}
и переписать основную часть вашего алгоритма так:
std::vector< std::vector<int> > bucket( c );
for(int i = 0; i < k; i++) {
bucket[ bucketIndex( n[i], c, s, l ) ].push_back( n[i] );
}
Я правильно вставляю предметы в свои ведра.
Другие решения
Других решений пока нет …