Как заставить алгоритм 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);
}
}

0

Решение

Эта строка не компилируется. 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] );
}

Я правильно вставляю предметы в свои ведра.

0

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]