fork(1) download
copy 
  1. # Toy radixsort for positive integers that allows an arbitrary
  2. # number of buckets.
  3.  
  4. import math
  5.  
  6. def iterations(a, b):
  7.     return math.ceil(math.log(max(a)+1, b))
  8.  
  9. def radixsorted(a):
  10.     if not a:
  11.         return []
  12.     n = len(a)
  13.     a = a.copy()
  14.     b = [None] * n
  15.     k = 16 # Number of buckets (not limited to powers of two).
  16.     for i in range(iterations(a, k)):
  17.         d = k**i
  18.         g = lambda x: x // d % k # Extract key.
  19.         h = [0] * k
  20.         # Histogram.
  21.         for x in a:
  22.             h[g(x)] += 1
  23.         # Accumulate positions.
  24.         for j in range(1, k):
  25.             h[j] += h[j-1]
  26.         # Reorder.
  27.         for x in reversed(a):
  28.             j = g(x)
  29.             h[j] -= 1
  30.             b[h[j]] = x
  31.         a, b = b, a
  32.     return a
  33.  
  34. # Test.
  35.  
  36. from random import choices
  37.  
  38. n = 11
  39. for i in range(n):
  40.     m = 2**i-1
  41.     a = choices(range(m), k=m)
  42.     u = sorted(a)
  43.     v = radixsorted(a)
  44.     if u == v:
  45.         print('Pass:', m)
  46.     else:
  47.         print('Fail:', (m, u, v))
  48.  
  49. # Show.
  50.  
  51. n = 10
  52. a = choices(range(n), k=n)
  53. print(a)
  54. print(sorted(a))
  55. print(radixsorted(a))
Success #stdin #stdout 0.14s 14356KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Pass: 0
Pass: 1
Pass: 3
Pass: 7
Pass: 15
Pass: 31
Pass: 63
Pass: 127
Pass: 255
Pass: 511
Pass: 1023
[5, 9, 1, 2, 8, 6, 3, 6, 2, 3]
[1, 2, 2, 3, 3, 5, 6, 6, 8, 9]
[1, 2, 2, 3, 3, 5, 6, 6, 8, 9]
https://ideone.com/vS0sOR
language:
Python 3 (python  3.12)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!