I am having trouble implementing the bucket sort algorithm.
The problem I am having is on line 15. I get a run-time error stating that the vector subscript is out of range.
void bucketSort(std::vector<int> S) {
if (S.size() < 1)
return;
std::vector<std::vector<int>> B;
int max = S[0];
for (int i = 1; i < S.size(); i++) {
if (S[i] > max)
max = S[i];
}
for (int i = 0; i < S.size(); i++ ) {
int index = S[i] * B.size() / (max + 1);
B[index].push_back(S[i]);
}
std::for_each(B.begin(), B.end(), [](std::vector<int>& e) {
std::sort(e.begin(),e.end());
});
int index = 0;
for (int i = 0; i < S.size(); i++)
for (int j = 0; j < B[i].size(); j++)
S[index++] = B[i][j];
}
Here is the algorithm I am trying to implement if it is any help
BucketSort(numbers, numbersSize, bucketCount) {
if (numbersSize < 1)
return
buckets = Create list of bucketCount buckets
// Find the maximum value
maxValue = numbers[0]
for (i = 1; i < numbersSize; i++) {
if (numbers[i] > maxValue)
maxValue = numbers[i]
}
// Put each number in a bucket
for each (number in numbers) {
index = floor(number * bucketCount / (maxValue + 1))
Append number to buckets[index]
}
// Sort each bucket
for each (bucket in buckets)
Sort(bucket)
// Combine all buckets back into numbers list
result = Concatenate all buckets together
Copy result to numbers
}
I am completely lost as to how I am supposed to add values into the buckets, I am not even sure if I am declaring it correctly. Also, I am not sure what the floor() function is and I was getting a syntax error so I just removed it altogether, not sure if I will run into problems with that later...
The vector I am inserting is a vector of 100 random int values. Here is how I am declaring it in main() just in case the problem lies there
1 2 3 4 5
std::vector<int> vectList;
for (int i = 0; i < 100; i++)
vectList.push_back(rand() % 999 + 1);
bucketSort(vectList);
Any help or suggestion will be greatly appreciated!
Awesome, it seems to have fixed the problem I was having. I am not entirely sure how many buckets it should have for best performance, so I just added a parameter where they can choose how many buckets, I chose 10.
Also, thanks for that suggestion! I was looking at other algorithms and saw it written that way, so I just stuck to it.
Now that my initial problem seems to have been fixed, I am now running into a problem on the for loop on line 24. I set a break point and the problem lies on the last iteration. Same error message I was receiving in my initial problem. I tried to return / break once it reaches the last iteration but that doesn't seem to work. Any suggestions as to what's going wrong?