BucketSort, error inputting into bucket of vectors

[Jorge626]

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

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!

[dutch]

B has 0 size. How many buckets should it have? You need to initialize it with that size (or resize it to that size before you index it).

S.size() < 1 should just be S.size() == 0

Your use of for_each is more simply written as an explicit loop:

    for( auto& b: B ) std::sort( b.begin(), b.end() );

[Jorge626]

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?

[dutch]

The outer loop bound should be the number of buckets in that loop, not the size of S.

	for (int i = 0, index = 0; i < num_buckets; i++)
		for (int j = 0; j < B[i].size(); j++)
			S[index++] = B[i][j];

[Jorge626]

It works! Awesome, thank you for all your help!