fork download 
  1. # Radixsort for positive integers. (1.01)
  2.  
  3. def iterations(a, b):
  4.     x = max(a)
  5.     r = 0
  6.     while x != 0:
  7.         x //= b
  8.         r += 1
  9.     return r
  10.  
  11. def radixsorted(a):
  12.     if not a:
  13.         return []
  14.     n = len(a)
  15.     a = a.copy()
  16.     b = [None] * n
  17.     k = 16 # Number of buckets (not limited to powers of two).
  18.     for i in range(iterations(a, k)):
  19.         d = k**i
  20.         g = lambda x: x // d % k # Extract key.
  21.         h = [0] * k
  22.         # Histogram.
  23.         for x in a:
  24.             h[g(x)] += 1
  25.         # Accumulate positions.
  26.         for j in range(1, k):
  27.             h[j] += h[j-1]
  28.         # Reorder.
  29.         for x in reversed(a):
  30.             j = g(x)
  31.             h[j] -= 1
  32.             b[h[j]] = x
  33.         a, b = b, a
  34.     return a
  35.  
  36. # Test.
  37.  
  38. from random import choices
  39.  
  40. n = 11
  41. for i in range(n):
  42.     m = 2**i-1
  43.     a = choices(range(m), k=m)
  44.     u = sorted(a)
  45.     v = radixsorted(a)
  46.     if u == v:
  47.         print('Pass:', m)
  48.     else:
  49.         print('Fail:', (m, u, v))
  50.  
  51. # Show.
  52.  
  53. n = 10
  54. a = choices(range(n), k=n)
  55. print(a)
  56. print(sorted(a))
  57. print(radixsorted(a))
Success #stdin #stdout 0.1s 14284KB
comments (?)
stdin 
Standard input is empty
stdout 
Pass: 0
Pass: 1
Pass: 3
Pass: 7
Pass: 15
Pass: 31
Pass: 63
Pass: 127
Pass: 255
Pass: 511
Pass: 1023
[6, 3, 7, 5, 5, 6, 0, 6, 7, 3]
[0, 3, 3, 5, 5, 6, 6, 6, 7, 7]
[0, 3, 3, 5, 5, 6, 6, 6, 7, 7]
https://ideone.com/FFVDXU
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!