Radix Sort in Kotlin

Radix sort is a non-comparative sorting algorithm that sorts integers by grouping them based on their individual digits, or more generally, on their individual “radix” (base). The algorithm sorts the input integers from least significant digit (LSD) to most significant digit (MSD), with each pass sorting the integers based on the current digit position.

fun radixSort(arr: IntArray) {
    val maxNum = arr.maxOrNull() ?: return
    var exp = 1
    val output = IntArray(arr.size)

    while (maxNum / exp > 0) {
        val count = IntArray(10)

        for (i in arr.indices) {
            count[(arr[i] / exp) % 10]++
        }

        for (i in 1 until 10) {
            count[i] += count[i - 1]
        }

        for (i in arr.indices.reversed()) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i]
            count[(arr[i] / exp) % 10]--
        }

        for (i in arr.indices) {
            arr[i] = output[i]
        }

        exp *= 10
    }
}

The radixSort function takes an array of integers arr and sorts it in place using radix sort. The function first finds the maximum number in the array maxNum. It then iterates through each digit position exp from the least significant digit to the most significant digit, and performs a counting sort based on the digits at the current position.

The counting sort works by first counting the number of occurrences of each digit at the current position in the input array, and then calculating the prefix sum of the counts to determine the positions of each digit in the output array. Finally, the function iterates through the input array in reverse order, placing each integer in the correct position in the output array based on the count and prefix sum arrays. The function then copies the output array back into the input array and multiplies exp by 10 to move to the next digit position.

Radix sort has a time complexity of O(kn), where k is the number of digits in the maximum number, and n is the number of elements in the array. In practice, radix sort is often used for sorting large data sets of integers, as it is more efficient than comparison-based sorting algorithms such as quicksort or mergesort.

fun main() {
    val arr = intArrayOf(201, 115, 861, 512, 6)
	radixSort(arr)
    for(i in 0 until arr.size)
		println(arr[i])
}
fun radixSort(arr: IntArray) {
    val maxNum = arr.maxOrNull() ?: return
    var exp = 1
    val output = IntArray(arr.size)

    while (maxNum / exp > 0) {
        val count = IntArray(10)

        for (i in arr.indices) {
            count[(arr[i] / exp) % 10]++
        }

        for (i in 1 until 10) {
            count[i] += count[i - 1]
        }

        for (i in arr.indices.reversed()) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i]
            count[(arr[i] / exp) % 10]--
        }

        for (i in arr.indices) {
            arr[i] = output[i]
        }

        exp *= 10
    }
}