0

I was looking at the bucket sort problem at geeks for geeks, in which they were storing multiple elements at the same index of vector.

My question is how is this possible that we can store multiple elements at the same index in vector.

The code is here

void bucketSort(float arr[], int n)
{
    // 1) Create n empty buckets
    vector<float> b[n];
  
    // 2) Put array elements 
    // in different buckets
    for (int i = 0; i < n; i++) {
        int bi = n * arr[i]; // Index in bucket
        b[bi].push_back(arr[i]);
    }
  
    // 3) Sort individual buckets
    for (int i = 0; i < n; i++)
        sort(b[i].begin(), b[i].end());
  
    // 4) Concatenate all buckets into arr[]
    int index = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < b[i].size(); j++)
            arr[index++] = b[i][j];
}
Md. Faisal Habib
  • 1,014
  • 1
  • 6
  • 14
Ali Hasan Khan
  • 23
  • 2
  • And once again an answer at Geeks For Geeks results in a question at Stack Overflow. Crom. Without Geeks For Geeks, Stack Overflow might be put out of business. – user4581301 Sep 13 '22 at 20:54

2 Answers2

0

vector<float> b[n] => it's a variable length array of vector. So when you're writing b[bi].push_back(), it means you're inserting an element at bi th vector, or you can say bith row.

In bucket sort, there can be multiple buckets. So this array of vectors represent all those buckets. That means, b[i] represents i th bucket.

So the answer to your question is, they're not storing multiple elements at the same index in vector. They're inserting the element arr[i] into bucket[n*array[i]], which itself is a vector.

Md. Faisal Habib
  • 1,014
  • 1
  • 6
  • 14
0

To answer your question right off the bat, they are NOT storing multiple elements in a single index of the vector. Here is what is happening:
vector<float> tells the compiler that each element of the vector is strictly a single float value. However, the b[n] part that follows is the notation you use to declare an array.
Ultimately, you end up with vector<float> b[n] which is basically an array but each element of the array is a vector. The vector itself stores only float values as you've instructed the compiler.
b[bi].push_back(arr[i]) is translated into:
To the vector stored in the biᵗʰ index of my array named b, append the float value which is arr[i]

Deb
  • 355
  • 2
  • 9
  • Addendum: `vector b[n];` isn't legal syntax in Standard C++. Details in [Why aren't variable-length arrays part of the C++ standard?](https://stackoverflow.com/q/1887097/4581301) – user4581301 Sep 13 '22 at 20:56