Advanced Sorting Applications in Kotlin

Introduction to the Lesson

Welcome to this insightful session, where we aim to master the complexities of the illustrious applications of sorting algorithms . Today's voyage links two problems: "Find the K-th Ordinal Statistic in a List" and "Count the Number of Inversions in a List." These problems mirror practical scenarios, and the efficient techniques used to solve them present valuable demonstrations of the application of sorting algorithms. Solving these two problems, we'll see how Quick Sort and Merge Sort knowledge apply here and help provide efficient implementations for both questions. Let's dive into these captivating problems!

Problem 1: Find the K-th Ordinal Statistic in a List

Our first problem presents a list of integers and the number k . The challenge is finding the k -th smallest element in that given list. To further elucidate, k starts from 1, so for k = 1, you are seeking to find the smallest element; if k = 2, you're searching for the second smallest element, and so on. By the conclusion of this lesson, you'll be highly skilled at performing this task!

Problem 1: Naive Approaches

O(n^2)

Problem 1: Efficient Approach Explanation

Sorting steps in here to offer an efficient solution! The Quick Sort algorithm, a splendid application of divide and conquer, can solve this problem more efficiently. By selecting the right pivot for partitioning, the input list is divided into two: a left partition, which contains elements less than the pivot, and a right partition, which includes elements greater than the pivot. If the pivot's position after elements repartition is the same as k, we have the k -th smallest element. If k is less than the pivot's position, the task is carried forward on the left partition; otherwise, on the right partition.

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Kotlin

inputArray.sort()
return inputArray[k - 1]

Kotlin

fun partition(arr: MutableList<Int>, start: Int, end: Int): Int {
    val pivot = arr[start]
    var i = start

    for (j in (start + 1)..end) {
        if (arr[j] <= pivot) {
            i++
            arr[i] = arr[j].also { arr[j] = arr[i] }
        }
    }

    arr[i] = arr[start].also { arr[start] = arr[i] }

    return i
}

fun partition(arr: MutableList<Int>, start: Int, end: Int): Int {
    val pivot = arr[start]
    var i = start

    for (j in (start + 1)..end) {
        if (arr[j] <= pivot) {
            i++
            arr[i] = arr[j].also { arr[j] = arr[i] }
        }
    }

    arr[i] = arr[start].also { arr[start] = arr[i] }

    return i
}

Kotlin

fun findKthSmallest(numbers: IntArray, k: Int): Int {
    if (numbers.size < k) return Int.MIN_VALUE
    return kthSmallest(numbers.toMutableList(), 0, numbers.size - 1, k)
}

fun kthSmallest(arr: MutableList<Int>, start: Int, end: Int, k: Int): Int {
    if (k > 0 && k <= end - start + 1) {
        val pos = partition(arr, start, end)

        if (pos - start == k - 1) {
            return arr[pos]
        }

        return if (pos - start > k - 1) {
            kthSmallest(arr, start, pos - 1, k)
        } else {
            kthSmallest(arr, pos + 1, end, k - pos + start - 1)
        }
    }

    return Int.MAX_VALUE
}

fun main() {
    val numbers = intArrayOf(1, 7, 2, 4, 2, 1, 6)
    println(findKthSmallest(numbers, 5))  // It should print 4
}

fun findKthSmallest(numbers: IntArray, k: Int): Int {
    if (numbers.size < k) return Int.MIN_VALUE
    return kthSmallest(numbers.toMutableList(), 0, numbers.size - 1, k)
}

fun kthSmallest(arr: MutableList<Int>, start: Int, end: Int, k: Int): Int {
    if (k > 0 && k <= end - start + 1) {
        val pos = partition(arr, start, end)

        if (pos - start == k - 1) {
            return arr[pos]
        }

        return if (pos - start > k - 1) {
            kthSmallest(arr, start, pos - 1, k)
        } else {
            kthSmallest(arr, pos + 1, end, k - pos + start - 1)
        }
    }

    return Int.MAX_VALUE
}

fun main() {
    val numbers = intArrayOf(1, 7, 2, 4, 2, 1, 6)
    println(findKthSmallest(numbers, 5))  // It should print 4
}

Kotlin

data class Result(val sorted: IntArray, val inversions: Long)

fun countInversions(arr: IntArray): Result {
    if (arr.size <= 1) return Result(arr, 0)
    val middle = arr.size / 2
    val left = countInversions(arr.copyOfRange(0, middle))
    val right = countInversions(arr.copyOfRange(middle, arr.size))
    val result = mergeAndCountInversions(left.sorted, right.sorted)
    return Result(result.sorted, left.inversions + right.inversions + result.inversions)
}

private fun mergeAndCountInversions(left: IntArray, right: IntArray): Result {
    val merged = IntArray(left.size + right.size)
    var i = 0
    var j = 0
    var inversions = 0L
    for (k in merged.indices) {
        if (i < left.size && (j >= right.size || left[i] <= right[j])) {
            merged[k] = left[i++]
        } else {
            merged[k] = right[j++]
            inversions += left.size - i
        }
    }
    return Result(merged, inversions)
}

data class Result(val sorted: IntArray, val inversions: Long)

fun countInversions(arr: IntArray): Result {
    if (arr.size <= 1) return Result(arr, 0)
    val middle = arr.size / 2
    val left = countInversions(arr.copyOfRange(0, middle))
    val right = countInversions(arr.copyOfRange(middle, arr.size))
    val result = mergeAndCountInversions(left.sorted, right.sorted)
    return Result(result.sorted, left.inversions + right.inversions + result.inversions)
}

private fun mergeAndCountInversions(left: IntArray, right: IntArray): Result {
    val merged = IntArray(left.size + right.size)
    var i = 0
    var j = 0
    var inversions = 0L
    for (k in merged.indices) {
        if (i < left.size && (j >= right.size || left[i] <= right[j])) {
            merged[k] = left[i++]
        } else {
            merged[k] = right[j++]
            inversions += left.size - i
        }
    }
    return Result(merged, inversions)
}

Kotlin

fun partition(arr: MutableList<Int>, start: Int, end: Int): Int {
    val pivot = arr[start]
    var i = start

    for (j in (start + 1)..end) {
        if (arr[j] <= pivot) {
            i++
            arr[i] = arr[j].also { arr[j] = arr[i] }
        }
    }

    arr[i] = arr[start].also { arr[start] = arr[i] }

    return i
}

Kotlin

fun findKthSmallest(numbers: IntArray, k: Int): Int {
    if (numbers.size < k) return Int.MIN_VALUE
    return kthSmallest(numbers.toMutableList(), 0, numbers.size - 1, k)
}

fun kthSmallest(arr: MutableList<Int>, start: Int, end: Int, k: Int): Int {
    if (k > 0 && k <= end - start + 1) {
        val pos = partition(arr, start, end)

        if (pos - start == k - 1) {
            return arr[pos]
        }

        return if (pos - start > k - 1) {
            kthSmallest(arr, start, pos - 1, k)
        } else {
            kthSmallest(arr, pos + 1, end, k - pos + start - 1)
        }
    }

    return Int.MAX_VALUE
}

fun main() {
    val numbers = intArrayOf(1, 7, 2, 4, 2, 1, 6)
    println(findKthSmallest(numbers, 5))  // It should print 4
}

Kotlin

data class Result(val sorted: IntArray, val inversions: Long)

fun countInversions(arr: IntArray): Result {
    if (arr.size <= 1) return Result(arr, 0)
    val middle = arr.size / 2
    val left = countInversions(arr.copyOfRange(0, middle))
    val right = countInversions(arr.copyOfRange(middle, arr.size))
    val result = mergeAndCountInversions(left.sorted, right.sorted)
    return Result(result.sorted, left.inversions + right.inversions + result.inversions)
}

private fun mergeAndCountInversions(left: IntArray, right: IntArray): Result {
    val merged = IntArray(left.size + right.size)
    var i = 0
    var j = 0
    var inversions = 0L
    for (k in merged.indices) {
        if (i < left.size && (j >= right.size || left[i] <= right[j])) {
            merged[k] = left[i++]
        } else {
            merged[k] = right[j++]
            inversions += left.size - i
        }
    }
    return Result(merged, inversions)
}