Skip to content

Instantly share code, notes, and snippets.

@jacquesattack
Created November 22, 2022 02:50
Show Gist options
  • Save jacquesattack/35eddb7f95e60e4a62616d7689a744de to your computer and use it in GitHub Desktop.
Save jacquesattack/35eddb7f95e60e4a62616d7689a744de to your computer and use it in GitHub Desktop.
Bucket sort of List[int] in python
"""
Bucket sort (of type List[int])
"""
from itertools import chain
from typing import List
def bucket_sort(somelist: List[int], n_buckets: int = None, approximate: bool = False):
if n_buckets is None:
n_buckets = int(len(somelist) ** 0.5)
buckets = [list() for _ in range(n_buckets)]
m = 1 + max(somelist)
for i, item in enumerate(somelist):
buckets[int(n_buckets * item / m)].append(item)
if not approximate:
for i, item in enumerate(buckets):
item.sort()
return list(chain(*buckets))
# examples
from random import randint, seed
seed(1234)
list_to_sort = [randint(1, 10) for _ in range(20)]
bucket_sort(list_to_sort)
bucket_sort(list_to_sort, approximate = True)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment