Advertisement
nathanwailes

Radix sort

May 18th, 2024
692
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.59 KB | None | 0 0
  1. def counting_sort(arr, exp):
  2.     n = len(arr)
  3.     output = [0] * n
  4.     count = [0] * 10
  5.  
  6.     for i in range(n):
  7.         index = arr[i] // exp
  8.         count[index % 10] += 1
  9.  
  10.     for i in range(1, 10):
  11.         count[i] += count[i - 1]
  12.  
  13.     i = n - 1
  14.     while i >= 0:
  15.         index = arr[i] // exp
  16.         output[count[index % 10] - 1] = arr[i]
  17.         count[index % 10] -= 1
  18.         i -= 1
  19.  
  20.     for i in range(n):
  21.         arr[i] = output[i]
  22.  
  23. def radix_sort(arr):
  24.     max1 = max(arr)
  25.     exp = 1
  26.     while max1 // exp > 0:
  27.         counting_sort(arr, exp)
  28.         exp *= 10
  29.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement