Bucket sort: Why all values end up in the first bucket?

Question

import random
random.seed(0)

def bucket_sort(mylist):
    # initialize the buckets
    lst = []
    for i in range(10):
        lst.append([])
    print(lst)
    length = len(mylist)
            
    # place the values to be sorted in the buckets
    for i in range(len(mylist)):
        ind = int(mylist[i]/length)
        if mylist[i] < 100:
            lst[ind].append(mylist[i])
        
        else:
            ten = [100]
        print(lst)
    
    # sort each bucket 

    
    result = []
    # concatenate your bucket to the result
    return result

I have a list of 100 numbers and I wanted to split them into 10 buckets (0-9,10-19, etc.). But the numbers won't go into each bucket I assigned

Answer 1

As length is len(mylist), it will be 100 for your input. As the code only adds numbers to buckets when they are less than one hundred, the value of ind will always be 0. The division was of something less than 100 divided by 100...

A quick fix would be to set:

length = 10

Other remarks

It is strange to do ten = [100]. This list ten is never used, it makes little sense to do this repeatedly, and its value does not necessarily correspond to an actual value in the input.

The index of the bucket should really be determined by the range of the values in the input. If it is given that the input will have numbers between 0 and 99, then it is fine to divide by 10, but if the input could have numbers between (let's say) -5000 and 5000, then you need to calculate the bucket index differently. You need the distance between the greatest and least value in the input element, to derive the range of a single bucket.

Finally, there are still some things to do in your code:

• implement the part where it says to sort the buckets. You can use the same function recursively.

• concatenate the buckets

Here is a spoiler implementation:

def bucket_sort(mylist): if len(mylist) <= 1: return mylist # initialize the buckets buckets = [[] for _ in range(10)] # get min/max from input list offset = min(mylist) size = max(mylist) + 1 - offset # place the values to be sorted in the buckets for value in mylist: ind = int((value - offset) * 10 / size) buckets[ind].append(value) # sort each bucket using recursion for i, bucket in enumerate(buckets): buckets[i] = bucket_sort(bucket) # concatenate the buckets as the result return [value for bucket in buckets for value in bucket]