Сортировка ведер с огромными случайными числами
Я знаю, что сортировка по Bucket имеет множество примеров повсюду, поэтому я попытался реализовать ее, чтобы она могла принимать огромные случайные числа без удачи
void Bucket_sort(int arr[], int max){
const int maxsize = max;
int bucket_list = new int [maxsize+1];
int length = sozeof(bucket_list) / sizeof(bucket[0]);
for(int i = 0; i <max;i++){
bucket_list[i] = 0; //fill with zeros
}
for (unsigned int i = 0; i <length; i++){
bucket_list[arr[i]]++;
}
int position = 0;
for (unsigned int i = 0 i < length; i++){
for(int k = 0; k<bucket_list[i];k++){
arr[position++] = i;
}
}
}
int main() {
int max = 50000
int arr[max];
for (int i = 0; i < max; i++){
arr[i] = rand() % 50000;
}
cout<<"Here are the numbers before Bucker Sort"<<endl;
for (int j = 0; j < max; j++){
cout<<arr[j];
}
Bucket_sort(arr,max);
for (int k = 0; k<max; k++){
cout<<arr[k];
}
}
кое-как, как я не могу заставить это работать, это только выставит тот же самый заказ (несортированный)
Я нашел те же вопросы, что и мои, но ни один из них не помог, вот один
https://stackoverflow.com/questions/20037176/c-bucket-sort-putting-integers-into-buckets
Решение
Эта строка:
bucket_list = 0; //fill with zeros
это меняет указатель, а не заполняет нулями. Вы должны использовать
bucket_list[i] = 0; //fill with zeros
Изменить: Есть гораздо больше проблем с компилятором вашего кода. Как только вы разобрались с этим, расчет length все еще не так. Вы не можете использовать sizeof трюк, потому что bucket_list не массив замещать
int length = sozeof(bucket_list) / sizeof(bucket[0]);
с
int length = maxsize
или просто не используйте длину вообще (у вас уже есть maxsize).
Другие решения
#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;
void Bucket_sort(int arr[], int max){
int maxsize = max;
int *bucket_list = new int[maxsize+1];
// int length = sozeof(bucket_list) / sizeof(bucket[0]);
int length = maxsize;
for(int i = 0; i <max;i++){
bucket_list[i] = 0; //fill with zeros
}
for (unsigned int i = 0; i <length; i++){
bucket_list[arr[i]]++;
}
int position = 0;
for (unsigned int i = 0 ; i < length ; i++){
for(int k = 0; k<bucket_list[i];k++){
arr[position++] = i;
}
}
}
int main() {
int max = 50;
int arr[max];
for (int i = 0; i < max; i++){
arr[i] = rand()%50;
}
cout<<"Here are the numbers before Bucker Sort"<<endl;
for (int j = 0; j < max; j++){
cout<<arr[j];
}
Bucket_sort(arr,max);
for (int k = 0; k<max; k++){
cout<<arr[k];
}
getch();
return 0;
}