Given an array arr[] of size N, use Radix Sort Algorithm to sort arr[] in ascending order.
Example 1:
Input :
N = 5
arr[] = {1, 9, 345, 2}
Output: 1 2 9 345
Example 2:
Input :
N = 10
arr[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}
Output: 1 2 3 4 5 6 7 8 9 10
Your Task:  
You dont need to read input or print anything. Complete the function radixSort() which takes arr[] and N as input parameters and sorts arr[] in-place. 
Expected Time Complexity: O(N * K) where K is the number of bits required to store each key.
Expected Auxiliary Space: O(N + K)
Constraints:
1 ≤ N ≤ 10^3

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Starter code: #User function Template for python3



def radixSort(arr, n):

    # code here

Solutions:
def radixSort(arr, n):
	return arr.sort()


def radixSort(arr, n):
	arr.sort()


def count_sort(arr, place):
	output = [0] * len(arr)
	count_arr = [0] * 10
	for i in arr:
		index = i // place
		count_arr[index % 10] = count_arr[index % 10] + 1
	for i in range(1, len(count_arr)):
		count_arr[i] = count_arr[i - 1] + count_arr[i]
	for i in range(len(arr) - 1, -1, -1):
		index = arr[i] // place
		output[count_arr[index % 10] - 1] = arr[i]
		count_arr[index % 10] -= 1
	for i in range(len(arr)):
		arr[i] = output[i]

def radixSort(arr, n):
	max_number = max(arr)
	place = 1
	while max_number // place >= 1:
		count_sort(arr, place)
		place = place * 10


def radixSort(arr, n):

	def countingsort(arr, check):
		freq = [0 for i in range(10)]
		out = [0 for i in range(len(arr))]
		for i in range(len(arr)):
			index = arr[i] // check
			freq[index % 10] += 1
		for i in range(1, len(freq)):
			freq[i] = freq[i] + freq[i - 1]
		for i in range(len(arr) - 1, -1, -1):
			ind = arr[i] // check
			fi = freq[ind % 10] - 1
			out[fi] = arr[i]
			freq[ind % 10] -= 1
		for i in range(len(arr)):
			arr[i] = out[i]
	check = 1
	maxe = max(arr)
	while maxe / check >= 1:
		countingsort(arr, check)
		check *= 10


def countingSort(arr, n, exp1):
	output = [0] * n
	count = [0] * 10
	for i in range(0, n):
		index = arr[i] // exp1
		count[index % 10] += 1
	for i in range(1, 10):
		count[i] += count[i - 1]
	i = n - 1
	while i >= 0:
		index = arr[i] // exp1
		output[count[index % 10] - 1] = arr[i]
		count[index % 10] -= 1
		i -= 1
	i = 0
	for i in range(0, len(arr)):
		arr[i] = output[i]

def radixSort(arr, n):
	max1 = max(arr)
	exp = 1
	while max1 / exp >= 1:
		countingSort(arr, n, exp)
		exp *= 10
	return arr


def countingSort(array, place):
	size = len(array)
	output = [0] * size
	count = [0] * 10
	for i in range(0, size):
		index = array[i] // place
		count[index % 10] += 1
	for i in range(1, 10):
		count[i] += count[i - 1]
	i = size - 1
	while i >= 0:
		index = array[i] // place
		output[count[index % 10] - 1] = array[i]
		count[index % 10] -= 1
		i -= 1
	for i in range(0, size):
		array[i] = output[i]

def radixSort(arr, n):
	maxi = max(arr)
	exp = 1
	while maxi // exp > 0:
		countingSort(arr, exp)
		exp = exp * 10


def radixSort(arr, n):

	def countsort(arr, exp):
		index = [0 for i in range(10)]
		n = len(arr)
		output = [0 for i in range(n)]
		for i in range(n):
			idx = arr[i] // exp
			index[idx % 10] += 1
		for i in range(1, 10):
			index[i] += index[i - 1]
		for i in range(n - 1, -1, -1):
			idx = arr[i] // exp
			output[index[idx % 10] - 1] = arr[i]
			index[idx % 10] -= 1
		for i in range(n):
			arr[i] = output[i]
	maxi = max(arr)
	exp = 1
	while maxi // exp >= 1:
		countsort(arr, exp)
		exp *= 10
	return arr


def radixSort(arr, n):
	maximum = max(arr)
	N = 1
	while maximum // N > 0:
		Countingsort(arr, N)
		N = N * 10

def Countingsort(arr, P):
	n = len(arr)
	res = [0] * n
	c = [0] * 10
	for i in range(0, n):
		temp = arr[i] // P
		c[temp % 10] += 1
	for i in range(1, 10):
		c[i] = c[i] + c[i - 1]
	i = n - 1
	while i >= 0:
		temp = arr[i] // P
		res[c[temp % 10] - 1] = arr[i]
		c[temp % 10] -= 1
		i = i - 1
	for i in range(0, n):
		arr[i] = res[i]


def radixSort(arr, n):
	maxelement = max(arr)
	place = 1
	while maxelement // place > 0:
		countingsort(arr, place)
		place *= 10
	return arr

def countingsort(arr, place):
	n = len(arr)
	output = [0] * n
	count = [0] * 10
	for i in range(n):
		index = arr[i] // place
		count[index % 10] += 1
	for i in range(1, 10):
		count[i] += count[i - 1]
	i = n - 1
	while i >= 0:
		index = arr[i] // place
		output[count[index % 10] - 1] = arr[i]
		count[index % 10] -= 1
		i -= 1
	for i in range(n):
		arr[i] = output[i]
	return arr


def radixSort(arr, n):
	maxm = max(arr)
	N = 1
	while maxm // N > 0:
		CountingSort(arr, N)
		N = N * 10

def CountingSort(arr, P):
	c = [0] * 10
	res = [0] * n
	for i in range(0, n):
		temp = arr[i] // P
		c[temp % 10] = c[temp % 10] + 1
	for i in range(1, 10):
		c[i] = c[i] + c[i - 1]
	i = n - 1
	while i >= 0:
		temp = arr[i] // P
		res[c[temp % 10] - 1] = arr[i]
		c[temp % 10] = c[temp % 10] - 1
		i = i - 1
	for i in range(0, n):
		arr[i] = res[i]


def radixSort(arr, n):
	arr[:] = sorted(arr)
	return


def countSort(arr, exp):
	n = len(arr)
	output = n * [0]
	count = 10 * [0]
	for i in range(n):
		index = arr[i] // exp
		count[index % 10] += 1
	for i in range(1, 10):
		count[i] += count[i - 1]
	i = n - 1
	while i >= 0:
		index = arr[i] // exp
		output[count[index % 10] - 1] = arr[i]
		count[index % 10] -= 1
		i -= 1
	for i in range(n):
		arr[i] = output[i]

def radixSort(arr, n):
	m = max(arr)
	exp = 1
	while m / exp >= 1:
		countSort(arr, exp)
		exp *= 10


def countingSort(arr, n, exp):
	count = [0] * 10
	output = [0] * n
	for i in range(0, n):
		index = arr[i] // exp % 10
		count[index] += 1
	for i in range(1, 10):
		count[i] += count[i - 1]
	i = n - 1
	while i >= 0:
		index = arr[i] // exp % 10
		output[count[index] - 1] = arr[i]
		count[index] -= 1
		i -= 1
	for (index, element) in enumerate(output):
		arr[index] = element

def radixSort(arr, n):
	maxi = max(arr)
	exp = 1
	while maxi // exp >= 1:
		countingSort(arr, n, exp)
		exp *= 10


def countingsort(arr, exp):
	n = len(arr)
	output = [0] * n
	count = [0] * 10
	for i in range(0, n):
		index = arr[i] // exp
		count[index % 10] += 1
	for i in range(1, 10):
		count[i] += count[i - 1]
	i = n - 1
	while i >= 0:
		index = arr[i] // exp
		output[count[index % 10] - 1] = arr[i]
		count[index % 10] -= 1
		i -= 1
	for i in range(0, len(arr)):
		arr[i] = output[i]

def radixSort(arr, n):
	max1 = max(arr)
	exp = 1
	while max1 / exp >= 1:
		countingsort(arr, exp)
		exp *= 10


def countingSort(arr, exp, n):
	output = [0] * n
	count = [0] * 10
	for i in range(n):
		index = arr[i] // exp % 10
		count[index] += 1
	for i in range(1, 10):
		count[i] += count[i - 1]
	i = n - 1
	while i >= 0:
		index = arr[i] // exp % 10
		output[count[index] - 1] = arr[i]
		count[index] -= 1
		i -= 1
	for i in range(n):
		arr[i] = output[i]

def radixSort(arr, n):
	mx = max(arr)
	exp = 1
	while mx // exp >= 1:
		countingSort(arr, exp, n)
		exp *= 10


def radixSort(arr, n):
	a = sorted(arr)
	for i in range(n):
		arr[i] = a[i]
	return arr


def find(arr, n):
	maxi = 0
	for i in range(n):
		if arr[i] > maxi:
			maxi = arr[i]
	count = 0
	while maxi:
		count += 1
		maxi = maxi // 10
	return count

def radixSort(arr, n):
	d = find(arr, n)
	for i in range(d):
		sort = []
		for o in range(10):
			sort.append([])
		for j in arr:
			x = pow(10, i)
			x = j // x
			x = x % 10
			sort[x].append(j)
		m = 0
		for k in range(10):
			p = 0
			while p < len(sort[k]):
				arr[m] = sort[k][p]
				m += 1
				p += 1
		sort.clear()


def radixSort(arr, n):
	m = arr[0]

	def count(e, arr):
		a = [0] * 10
		ans = [0] * n
		for i in range(n):
			a[arr[i] // e % 10] += 1
		for i in range(1, 10):
			a[i] += a[i - 1]
		for i in range(n - 1, -1, -1):
			ans[a[arr[i] // e % 10] - 1] = arr[i]
			a[arr[i] // e % 10] -= 1
		for i in range(n):
			arr[i] = ans[i]
	for i in arr:
		if m < i:
			m = i
	e = 1
	while e <= m:
		count(e, arr)
		e *= 10
	return arr


def radixSort(arr, n):
	exp = 1
	mx = max(arr)
	while mx // exp >= 1:
		countSort(arr, exp)
		exp *= 10

def countSort(arr, exp):
	n = len(arr)
	cnt = [0] * 10
	out = [0] * n
	for val in arr:
		index = val // exp
		cnt[index % 10] += 1
	i = 1
	while i < 10:
		cnt[i] += cnt[i - 1]
		i += 1
	i = n - 1
	while i >= 0:
		index = arr[i] // exp
		out[cnt[index % 10] - 1] = arr[i]
		cnt[index % 10] -= 1
		i -= 1
	for i in range(n):
		arr[i] = out[i]


def radixSort(arr, n):
	k = sorted(arr)
	for i in range(len(k)):
		arr[i] = k[i]


def radixSort(arr, n):
	maxi = 0
	for i in range(n):
		l = 0
		l = len(str(arr[i]))
		if l > maxi:
			maxi = l
	temp = [0 for i in range(n)]
	for i in range(maxi):
		index = [0 for i in range(10)]
		for j in range(n):
			ind = arr[j] // 10 ** i % 10
			index[ind] += 1
		for j in range(1, 10):
			index[j] = index[j - 1] + index[j]
		for j in range(n - 1, -1, -1):
			ind = arr[j] // 10 ** i % 10
			temp[index[ind] - 1] = arr[j]
			index[ind] -= 1
		for i in range(len(temp)):
			arr[i] = temp[i]
	return arr


def radixSort(arr, n):
	numbers = list(range(10))
	max_number = max(arr)
	exp = 1
	while max_number // exp > 0:
		hash_d = {x: 0 for x in numbers}
		for i in arr:
			hash_d[i // exp % 10] += 1
		prev = hash_d[0]
		for i in numbers[1:]:
			hash_d[i] += prev
			prev = hash_d[i]
		for i in arr[::-1]:
			index = i // exp % 10
			arr[hash_d[index] - 1] = i
			hash_d[index] = hash_d[index] - 1
		exp *= 10
	return arr


def radixSort(arr, n):
	for i in range(1, n):
		key = arr[i]
		j = i - 1
		while j >= 0 and arr[j] > key:
			arr[j + 1] = arr[j]
			j = j - 1
		arr[j + 1] = key
	return arr


def countSort(a, n, k):
	l = [0] * 10
	b = []
	x = [0] * n
	for i in a:
		for j in range(k - 1):
			if i == 0:
				break
			i //= 10
		if i == 0:
			b.append(0)
			l[0] += 1
			continue
		i %= 10
		b.append(i)
		l[i] += 1
	for i in range(1, 10):
		l[i] += l[i - 1]
	for i in range(n - 1, -1, -1):
		l[b[i]] -= 1
		x[l[b[i]]] = a[i]
	for i in range(n):
		a[i] = x[i]

def radixSort(a, n):
	k = 0
	for i in a:
		k = max(k, len(str(i)))
	for i in range(k):
		countSort(a, n, i + 1)


def radixSort(arr, n):
	maxval = max(arr)
	max_digits = 1
	while True:
		maxval = maxval // 10
		if maxval == 0:
			break
		max_digits += 1
	for d in range(max_digits):
		H = {}
		for i in range(10):
			H[i] = []
		for num in arr:
			digit = num // 10 ** d % 10
			H[digit].append(num)
		b = []
		for i in range(10):
			if H[i]:
				b.extend(H[i])
		for i in range(n):
			arr[i] = b[i]


def radixSort(arr, n):

	def ss(arr, k):
		if k == 4:
			return
		d = {i: [] for i in range(10)}
		for n in arr:
			d[n // 10 ** k % 10].append(n)
		j = 0
		for i in range(10):
			for n in d[i]:
				arr[j] = n
				j += 1
		ss(arr, k + 1)
	ss(arr, 0)


def getMax(arr, n):
	mx = arr[0]
	for i in range(1, n):
		if arr[i] > mx:
			mx = arr[i]
	return mx

def countSort(arr, n, exp):
	output = [0] * n
	count = [0] * 10
	for i in range(n):
		count[arr[i] // exp % 10] += 1
	for i in range(1, 10):
		count[i] += count[i - 1]
	i = n - 1
	while i >= 0:
		output[count[arr[i] // exp % 10] - 1] = arr[i]
		count[arr[i] // exp % 10] -= 1
		i = i - 1
	for i in range(n):
		arr[i] = output[i]

def radixSort(arr, n):
	m = getMax(arr, n)
	exp = 1
	while m // exp > 0:
		countSort(arr, n, exp)
		exp = exp * 10


def radixSort(arr, n):
	for i in range(n):
		arr[i] = str(arr[i])
	maxLength = len(max(arr, key=len))
	for i in range(len(arr)):
		arr[i] = '0' * (maxLength - len(arr[i])) + arr[i]
	for digit in range(maxLength - 1, -1, -1):
		temp = [[] for i in range(10)]
		for i in range(n):
			cur_digit = int(arr[i][digit])
			temp[cur_digit].append(arr[i])
		k = 0
		for i in range(len(temp)):
			for j in range(len(temp[i])):
				arr[k] = temp[i][j]
				k += 1
	for i in range(len(arr)):
		arr[i] = int(arr[i])


def radixSort(arr, n):
	dict_s = {}
	for i in range(10):
		dict_s[str(i)] = []
	max_m = arr[0]
	for i in arr:
		max_m = max(i, max_m)
	count = str(max_m).__len__()
	temp = []
	for i in arr:
		c = count - str(i).__len__()
		a = '0' * c
		temp.append(a + str(i))
	for i in range(1, count + 1):
		new = []
		for j in temp:
			dict_s[j[-i]].append(j)
		for k in range(10):
			for l in dict_s[str(k)]:
				new.append(l)
			dict_s[str(k)] = []
		temp = new[:]
	ans = []
	for i in temp:
		ans.append(int(i))
	i = 0
	for j in ans:
		arr[i] = j
		i += 1
	return arr


def radixSort(arr, n):
	exp = 1
	mx = max(arr)
	while mx // exp > 0:
		countsort(arr, n, exp)
		exp *= 10

def countsort(arr, n, exp):
	co = [0] * 10
	ot = [0] * n
	for i in range(n):
		co[arr[i] // exp % 10] += 1
	for i in range(1, 10):
		co[i] = co[i] + co[i - 1]
	for i in range(n - 1, -1, -1):
		ot[co[arr[i] // exp % 10] - 1] = arr[i]
		co[arr[i] // exp % 10] -= 1
	for i in range(n):
		arr[i] = ot[i]
if __name__ == '__main__':
	t = int(input())
	while t > 0:
		n = int(input())
		arr = [int(x) for x in input().strip().split()]
		radixSort(arr, n)
		for ele in arr:
			print(ele, end=' ')
		print()
		t = t - 1


def radixSort(arr, n):
	arr.sort()
	return arr
if __name__ == '__main__':
	t = int(input())
	while t > 0:
		n = int(input())
		arr = [int(x) for x in input().strip().split()]
		radixSort(arr, n)
		for ele in arr:
			print(ele, end=' ')
		print()
		t = t - 1


def radixSort(arr, n):
	max1 = arr[0]
	for i in range(1, n):
		if arr[i] > max1:
			max1 = arr[i]
	exp = 1
	while max1 // exp > 0:
		count_sort(arr, n, exp)
		exp = exp * 10

def count_sort(arr, n, exp):
	count = [0] * 10
	for i in range(n):
		count[arr[i] // exp % 10] += 1
	for i in range(1, 10):
		count[i] = count[i] + count[i - 1]
	output = [0] * n
	for i in range(n - 1, -1, -1):
		output[count[arr[i] // exp % 10] - 1] = arr[i]
		count[arr[i] // exp % 10] -= 1
	for i in range(n):
		arr[i] = output[i]


def countsort(arr, n, place):
	anss = [0] * n
	count = [0] * 10
	for i in range(0, n):
		index = arr[i] // place
		count[index % 10] += 1
	for i in range(1, 10):
		count[i] += count[i - 1]
	i = n - 1
	while i >= 0:
		index = arr[i] // place
		anss[count[index % 10] - 1] = arr[i]
		count[index % 10] -= 1
		i -= 1
	arr[:] = anss[:]

def radixSort(arr, n):
	high = max(arr)
	place = 1
	while high // place > 0:
		countsort(arr, n, place)
		place *= 10


def countingSort(arr, place):
	N = len(arr)
	Output = [0] * N
	count = [0] * 10
	for i in range(N):
		index = arr[i] // place
		count[index % 10] += 1
	for i in range(1, 10):
		count[i] += count[i - 1]
	i = N - 1
	while i >= 0:
		index = arr[i] // place
		Output[count[index % 10] - 1] = arr[i]
		count[index % 10] -= 1
		i -= 1
	for i in range(N):
		arr[i] = Output[i]

def radixSort(arr, n):
	max_num = max(arr)
	divisor = 1
	while max_num // divisor > 0:
		countingSort(arr, divisor)
		divisor = divisor * 10