Skip to content

Instantly share code, notes, and snippets.

@JellyWX
Created April 8, 2019 21:28
Show Gist options
  • Save JellyWX/18ce6e339d0b38860feee9d87fa5a0a1 to your computer and use it in GitHub Desktop.
Save JellyWX/18ce6e339d0b38860feee9d87fa5a0a1 to your computer and use it in GitHub Desktop.
def bucket_sort(vector: list, bin_count: int):
bins = [[] for _ in range(bin_count)] # create a list of empty lists to the bin_count
# define the maximum, minimum and range of values within the data being sorted
M, m = max(vector), min(vector)
r = M - m
# group the items into bins
for item in vector:
bin_ = int(
round(
((item - m) / r) * (bin_count - 1)
)
)
bins[bin_].append(item)
out_list = []
# sort each bin inplace individually, then concatenate them
for b in bins:
b.sort()
out_list.extend(b)
return out_list
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment