FilesExpand file tree

 master

/

radix_sort.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

53 lines (43 loc) · 1.28 KB

 master

/

radix_sort.py

Copy path

Top

File metadata and controls

• Code
• Blame

53 lines (43 loc) · 1.28 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

# Following is the implementation of Radix Sort.

def radix_sort(arr, radix=10):

"""

:param arr: Iterable of elements to sort.

:param radix: Base of input numbers

:return: Sorted list of input.

Time complexity: O(d * (n + b))

where, n is the size of input list.

b is base of representation.

d is number of digits in largest number in that base.

Space complexity: O(n + k)

where, k is the range of input.

"""

max_length = False

tmp, digit = -1, 1

while not max_length:

max_length = True

# declare and initialize buckets

buckets = [[] for _ in range(radix)]

# split arr between lists

for i in arr:

tmp = i // digit

buckets[tmp % radix].append(i)

if max_length and tmp > 0:

max_length = False

# empty lists into arr array

a = 0

for b in range(radix):

buck = buckets[b]

for i in buck:

arr[a] = i

a += 1

# move to next digit

digit *= radix

return arr

def main():

"""

Driver function to test radix sort.

"""

test = [170, 45, 75, 90, 802, 24, 2, 66]

print('Sorted array:', radix_sort(test))

if __name__ == '__main__':

main()