Okorosso

Untitled

May 16th, 2021
566
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. def counting_sort(arr, exp1):
  2.     n = len(arr)
  3.     output = [0] * n
  4.     count = [0] * 10
  5.  
  6.     for i in range(n):
  7.         index = (arr[i] / exp1)
  8.         count[int(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] / exp1)
  16.         output[count[int(index % 10)] - 1] = arr[i]
  17.         count[int(index % 10)] -= 1
  18.         i -= 1
  19.     for i in range(len(arr)):
  20.         arr[i] = output[i]
  21.     return arr
  22.  
  23.  
  24. def radix_sort(arr):
  25.     array = arr.copy()
  26.     max1 = max(array)
  27.     exp = 1
  28.  
  29.     while max1 / exp > 0:
  30.         array = counting_sort(array, exp)
  31.         exp *= 10
  32.     return array
  33.  
  34.  
  35. arr = [1, 2, 112, 18, 56, 985, 36, 521, 1024]
  36.  
  37. arr = radix_sort(arr)
  38. print(*arr)
  39.  
RAW Paste Data