# BucketSort implementation is not completely correct

**URL:** <https://forum.codewithmosh.com/t/bucketsort-implementation-is-not-completely-correct/14301>\
**Category:** Data Structures\
**Created:** [August 11, 2022, 11:27am UTC](https://forum.codewithmosh.com/t/bucketsort-implementation-is-not-completely-correct/14301 "2022-08-11T11:27:34Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![satthecoder](https://sea2.discourse-cdn.com/flex020/user_avatar/forum.codewithmosh.com/satthecoder/32/5890_2.png) [@satthecoder](https://forum.codewithmosh.com/u/satthecoder)\
**Post date:** [August 11, 2022, 11:27am UTC](https://forum.codewithmosh.com/t/bucketsort-implementation-is-not-completely-correct/14301/1 "2022-08-11T11:27:34Z")

</div>

I’ve tested the code in the video, but when you add larger numbers like 888 to the array and test your bucketSort class, there might be out of scope error. Because 888/3 = 296 and you don’t have any bucket at index 296 of buckets list.

---

<div class="post-metadata">

**Author:** ![jmrunkle](https://sea2.discourse-cdn.com/flex020/user_avatar/forum.codewithmosh.com/jmrunkle/32/3765_2.png) [@jmrunkle](https://forum.codewithmosh.com/u/jmrunkle)\
**Post date:** [August 11, 2022, 2:57pm UTC](https://forum.codewithmosh.com/t/bucketsort-implementation-is-not-completely-correct/14301/2 "2022-08-11T14:57:41Z")

</div>

Agreed. If you check Wikipedia about the Bucket Sort algorithm it accounts for the max value stored when determining the bucket index. For k buckets with a max value of M, the bucket for the value at index i should be floor(k\*value[i]/M):

> **[Bucket sort](https://en.m.wikipedia.org/wiki/Bucket_sort)**
>
> Bucket sort, or bin sort, is a sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. It is a distribution sort, a generalization of pigeonhole sort that allows multiple keys per bucket, and is a cousin of radix sort in the most-to-least significant digit flavor. Bucket sort can be implemented with comparisons and t...

So your example would be floor(3\*888/888) = floor(3) = 2 (assuming 888 were the max value).

Note: this requires one iteration through the whole array at the start to get the max value.

---

<div class="post-metadata">

**Author:** ![satthecoder](https://sea2.discourse-cdn.com/flex020/user_avatar/forum.codewithmosh.com/satthecoder/32/5890_2.png) [@satthecoder](https://forum.codewithmosh.com/u/satthecoder)\
**Post date:** [August 11, 2022, 7:18pm UTC](https://forum.codewithmosh.com/t/bucketsort-implementation-is-not-completely-correct/14301/3 "2022-08-11T19:18:38Z")

</div>

But I think this one is also not accurate.  
If we have an array of {3, 1, 5, 7, 4, 5, 4, 888},  
according to this formula “floor(k\*value[i]/M)” there will be only two buckets, which makes this algorithm very slow.

So, I used the old formula which is in the video course, but I used std::map for the buckets.  
Here is my code:

static void BucketSort(std::vector &v, int numberOfBuckets){  
std::map\<int, std::list\> buckets;  
for (auto item : v){  
buckets[item / numberOfBuckets].push\_back(item);  
}

```
int i = 0;
for (auto &[key, bucket] : buckets){
	bucket.sort();
	for(auto item : bucket)
		v[i++] = item;
}

```

}

If you think my code can be considered accurate, please let me know.

---

<div class="post-metadata">

**Author:** ![jmrunkle](https://sea2.discourse-cdn.com/flex020/user_avatar/forum.codewithmosh.com/jmrunkle/32/3765_2.png) [@jmrunkle](https://forum.codewithmosh.com/u/jmrunkle)\
**Post date:** [August 11, 2022, 8:05pm UTC](https://forum.codewithmosh.com/t/bucketsort-implementation-is-not-completely-correct/14301/4 "2022-08-11T20:05:04Z")

</div>

> [@satthecoder](#):
>
> But I think this one is also not accurate.  
> If we have an array of {3, 1, 5, 7, 4, 5, 4, 888},  
> according to this formula “floor(k\*value[i]/M)” there will be only two buckets, which makes this algorithm very slow.

Not accurate is probably the wrong description. It would use 3 buckets and nothing would go into the middle bucket. First bucket would contain everything other than 888 and the third bucket would contain just 888. This just proves that the Bucket Sort algorithm is susceptible to very bad distributions causing poor performance (pretty much all sorting algorithms have degenerate cases).

> [@satthecoder](#):
>
> If you think my code can be considered accurate, please let me know.

I am not certain of the iteration order guarantees on maps on whatever derivative of C you are using. You must iterate from the first index to the last in order to get the sort order correct. If you have to get the keys, then sort those, you are kinda getting into a circular problem (I must sort these keys in order to sort these items). If the order of the keys is guaranteed to be smallest to largest that could work though. Otherwise I do not think it actually does the sort correctly.

---

<div class="post-metadata">

**Author:** ![jmrunkle](https://sea2.discourse-cdn.com/flex020/user_avatar/forum.codewithmosh.com/jmrunkle/32/3765_2.png) [@jmrunkle](https://forum.codewithmosh.com/u/jmrunkle)\
**Post date:** [August 11, 2022, 8:41pm UTC](https://forum.codewithmosh.com/t/bucketsort-implementation-is-not-completely-correct/14301/5 "2022-08-11T20:41:32Z")

</div>

According to [this StackOverflow answer](https://stackoverflow.com/questions/7648756/is-the-order-of-iterating-through-stdmap-known-and-guaranteed-by-the-standard) std::map should have a guaranteed iteration order through the keys from start to end. So your algorithm should work if that is true.

I should also mention that if you use simply dividing by the “number of buckets” that you are not actually guaranteeing that number of buckets at all (since you can have more than that number of buckets). Using the example numbers you provided, here are the bucket numbers you get for the inputs:

- 3 =\> 3/3 = 1
- 1 =\> 1/3 = 0
- 5 =\> 5/3 = 1
- 7 =\> 7/3 = 2
- 4 =\> 4/3 = 1
- 5, 4 (see above)
- 888 =\> 888/3 = 296

Note: that would be 4 buckets (not 3): 0, 1, 2, and 296.

* * *

Since we need to identify the largest value anyways in the classic BucketSort, I am curious that a better variation is to keep track of some histogram information on orders of magnitude (maybe powers of 2 for example). Then you could use the histogram information to tell you how to create buckets that are approximately the same size.

Applying that to our example of {3, 1, 5, 7, 4, 5, 4, 888} we would create a histogram like this:

```nohighlight
{ 
  Range[0 to 0]: 0, // no items in this range
  Range[1 to 1]: 1, // just one 1 in this range
  Range[2 to 2]: 0, // no items in this range
  Range[3 to 4]: 3, // 3, 4, and 4 are in this range
  Range[5 to 8]: 3, // 5, 7, and 5 are in this range
  Range[9 to 16]: 0, // no items in this range
  ...
  Range[513 to 1024]: 1, // 888 is in this range
}

```

Since we have 8 items total, we want to get 2 to 3 items in each bucket, so we should pick approximate breakpoints that would get us there. We can get exactly 4 items in the first bucket by choosing 0 to 4 as our first bucket, but since we want to get closer to 2.5, we should try to get 1.5 items from that bucket which means aiming for the middle (since there are 3 items total) which means using 0 to 3 as our first bucket. That leaves approximately 1.5 items in that bucket and we want (approximately) another 1 item from the next bucket that has items. It has 3 so we could get approximately 4.5 items if we chose the next bucket to be from 4 to 8. Trying to get only 1 of the 3 items means we want to pick about 1/3 through the range which means we should really cut it off at 6. So our second bucket becomes from 4 to 6. That leaves our third bucket covering 7 to 888.

Putting our values into those buckets, let us see how the breakdown turned out:

- bucket[0] (range 0 to 3) = [3, 1]
- bucket[1] (range 4 to 6) = [5, 4, 5, 4]
- bucket[2] (range 7 to 888) = [7, 888]

While we did get one bucket larger than 3 items, that really was not such a bad breakdown (especially compared to the main one where everything ended up in the same bucket except 888).

Anyway, thanks for pointing out this issue since many students would not have discovered the issue.

@Mosh - it may actually be worth updating that particular set of videos since the algorithm is actually wrong.

---

<div class="post-metadata">

**Author:** ![satthecoder](https://sea2.discourse-cdn.com/flex020/user_avatar/forum.codewithmosh.com/satthecoder/32/5890_2.png) [@satthecoder](https://forum.codewithmosh.com/u/satthecoder)\
**Post date:** [August 15, 2022, 2:40pm UTC](https://forum.codewithmosh.com/t/bucketsort-implementation-is-not-completely-correct/14301/6 "2022-08-15T14:40:10Z")

</div>

It does the sort correctly

---

<div class="post-metadata">

**Author:** ![jmrunkle](https://sea2.discourse-cdn.com/flex020/user_avatar/forum.codewithmosh.com/jmrunkle/32/3765_2.png) [@jmrunkle](https://forum.codewithmosh.com/u/jmrunkle)\
**Post date:** [August 15, 2022, 3:09pm UTC](https://forum.codewithmosh.com/t/bucketsort-implementation-is-not-completely-correct/14301/7 "2022-08-15T15:09:34Z")

</div>

OK, but it is still not a bucket sort since it is not using a fixed number of buckets. Dividing by k (number of buckets) is not enough to guarantee k buckets. You have to multiply by k and divide by M (max value). Otherwise you can have an arbitrary number of buckets. Cheers!

---

<div class="post-metadata">

**Author:** ![kat](https://avatars.discourse-cdn.com/v4/letter/k/b19c9b/32.png) [@kat](https://forum.codewithmosh.com/u/kat)\
**Post date:** [July 27, 2024, 7:11pm UTC](https://forum.codewithmosh.com/t/bucketsort-implementation-is-not-completely-correct/14301/8 "2024-07-27T19:11:27Z")

</div>

@Mosh thank you so much for this entire site, you are amazing!  
But Bucket Sort implementation is not working, even with such a simple input as this:

int numbers = new int{15, 6, 3, 1, 22, 10, 13};  
BucketSort sorter = new BucketSort();  
sorter.sort(numbers, 3);