Advanced Applications of Sorting Algorithms in Scala

Introduction to the Lesson

Welcome to this insightful session, where our aim is 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. By solving these two problems, we'll see how Quick Sort and Merge Sort knowledge applies here and helps 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 clarify, 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 are repartitioned 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 – Main Logic

Then, implement the merge sort that keeps track of the number of inversions:

Scala

def countInversions(arr: Array[Int]): Result = {
  if (arr.length <= 1) {
    Result(arr, 0)
  } else {
    val middle = arr.length / 2
    val left = countInversions(arr.slice(0, middle))
    val right = countInversions(arr.slice(middle, arr.length))
    val result = mergeAndCountInversions(left.sorted, right.sorted)
    Result(result.sorted, left.inversions + right.inversions + result.inversions)
  }
}

def mergeAndCountInversions(left: Array[Int], right: Array[Int]): Result = {
  val merged = new Array[Int](left.length + right.length)
  var i = 0; var j = 0; var inversions = 0L
  for (k <- merged.indices) {
    if (i < left.length && (j >= right.length || left(i) <= right(j))) {
      merged(k) = left(i)
      i += 1
    } else {
      merged(k) = right(j)
      j += 1
      inversions += left.length - i
    }
  }
  Result(merged, inversions)
}

def countInversions(arr: Array[Int]): Result = {
  if (arr.length <= 1) {
    Result(arr, 0)
  } else {
    val middle = arr.length / 2
    val left = countInversions(arr.slice(0, middle))
    val right = countInversions(arr.slice(middle, arr.length))
    val result = mergeAndCountInversions(left.sorted, right.sorted)
    Result(result.sorted, left.inversions + right.inversions + result.inversions)
  }
}

def mergeAndCountInversions(left: Array[Int], right: Array[Int]): Result = {
  val merged = new Array[Int](left.length + right.length)
  var i = 0; var j = 0; var inversions = 0L
  for (k <- merged.indices) {
    if (i < left.length && (j >= right.length || left(i) <= right(j))) {
      merged(k) = left(i)
      i += 1
    } else {
      merged(k) = right(j)
      j += 1
      inversions += left.length - i
    }
  }
  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

Problem 2: Solution Building – Main Logic

Lesson Summary

Practice Exercises