Skip to content

Instantly share code, notes, and snippets.

@fela
Last active March 11, 2022 11:43
Show Gist options
  • Save fela/79f5c8241288a3314c4f to your computer and use it in GitHub Desktop.
Save fela/79f5c8241288a3314c4f to your computer and use it in GitHub Desktop.
#!/usr/bin/env python3
RADIX = 10
# radix sort that works for non negative integers
def radix_sort_nonneg(lst):
last_iteration = False
radix_power = 1
while not last_iteration:
# split into buckets
buckets = [[] for _ in range(RADIX)]
last_iteration = True # unless we find it isn't
for el in lst:
# find the digit corresponding to radix_power
# example with radix_power = 1000; el = 123456
# el % (radix_power*RADIX) == 123456 % 10000 == 3456
# 3456 // radix_power == 3456 // 1000 == 3
digit = el % (radix_power*RADIX) // radix_power
buckets[digit].append(el)
if el >= radix_power*RADIX:
last_iteration = False
# flatten
lst = [el for bucket in buckets for el in bucket]
radix_power *= RADIX
return lst
def radix_sort(lst):
positive_ints = radix_sort_nonneg( x for x in lst if x >= 0)
negative_ints = radix_sort_nonneg(-x for x in lst if x < 0)
return [-x for x in reversed(negative_ints)] + positive_ints
print(radix_sort([1, 2, 3, -3, -10, 332, 123, 124, 122, 2, 321, 3, 0]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment