Python Tutorial

Python installation

• Radix sort is the generalized bin sort.
• Radix sort key idea is to bin sort all the array elements, first on f(k) (the least significant digit, then concentrate bins for the lowest value first, again bin sort on f(k-1) digit and so on.
• Make sure each array element is appended to the end of the list, not the beginning.

• Sort the array elements using counter range(0 to 9) based on least digit value.
• Repeat the sorting for next digits till maximum element number digits.

Radix sorting time complexity is O(N∗logb(N)). here N is the number of elements in the list, b is the base for representing numbers.

```#!/usr/bin/python

def counting_sort(list_vals, n, place):
integer_range = 10;
freq =[0 for i in range(0, integer_range)];
list_sorted = [0 for i in range(0, n)];

for i in range(0, n):
freq[(list_vals[i]/place)%integer_range] += 1;

for i in range(1, integer_range):
freq[i] += freq[i-1];

i = n-1;
while (i>=0):
list_sorted[freq[(list_vals[i]/place)%10]-1]=list_vals[i];
freq[(list_vals[i]/place)%10] -= 1;
i -= 1;

for j in range(0, n):
list_vals[j]=list_sorted[j];

n = len(list_vals);
max_element = max(list_vals);
mul=1;
while (max_element):
counting_sort(list_vals, n, mul);
mul *= 10;
max_element /= 10;

return list_vals;

if __name__ == "__main__":
list_vals = [3, 1, 2, 3, 6, 8, 5, 4];
print("Collection before sorting: %s" % str(list_vals));
print("Sorted list elements: %s" % str(radix_sort(list_vals)));
```
Output:
```\$ python radix_sort.py
Collection before sorting: [3, 1, 2, 3, 6, 8, 5, 4]
Sorted list elements: [1, 2, 3, 3, 4, 5, 6, 8]
```

Python Tutorial