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

Problem 2: Solution Building — Supporting Class

Here is the Kotlin solution based on the Merge Sort algorithm. First, let's define a data class to store our counter for each subarray:

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)
}

While performing the merge in Merge Sort, we have added an additional counter to track inversions. If we come across an element in the right array that is smaller than an element in the left, we increment the counter by the number of items remaining in the left array. These all form inversions as per our problem's definition.

Introduction to the Lesson

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

Problem 1: Naive Approaches

Problem 1: Efficient Approach Explanation

Join the 1M+ learners on CodeSignal

Problem 1: Solution Building — Partition

Problem 1: Solution Building — Main Logic

Problem 2: Count the Number of Inversions in a List

Problem 2: Efficient Approach Explanation

Problem 2: Solution Building — Supporting Class

Lesson Summary

Practice Exercises