Advanced Sorting Algorithms and Applications in Ruby

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 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 Select 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 1: Solution Building – Main Logic

Then, we define the find_kth_smallest algorithm, essentially working as a quicksort, but chasing a different goal:

Ruby

def find_kth_smallest(numbers, k)
  # If the numbers array is nil or has fewer elements than k, return nil
  return nil if numbers.nil? || numbers.length < k

  # Start the recursive search for the k-th smallest element
  kth_smallest(numbers, 0, numbers.length - 1, k)
end

def kth_smallest(arr, start, end_idx, k)
  # Check if the k is within the valid range
  if k > 0 && k <= end_idx - start + 1
    # Partition the array and get pivot position
    pos = partition(arr, start, end_idx)

    # If pivot position is the same as k-1, return the element at that position
    if pos - start == k - 1
      return arr[pos]
    end

    # If pivot position is more than k-1, search in the left partition
    if pos - start > k - 1
      return kth_smallest(arr, start, pos - 1, k)
    end

    # Otherwise, continue search in the right partition
    return kth_smallest(arr, pos + 1, end_idx, k - pos + start - 1)
  end
  nil
end

numbers = [1, 7, 2, 4, 2, 1, 6]
puts find_kth_smallest(numbers, 5)  # It should print 4

def find_kth_smallest(numbers, k)
  # If the numbers array is nil or has fewer elements than k, return nil
  return nil if numbers.nil? || numbers.length < k

  # Start the recursive search for the k-th smallest element
  kth_smallest(numbers, 0, numbers.length - 1, k)
end

def kth_smallest(arr, start, end_idx, k)
  # Check if the k is within the valid range
  if k > 0 && k <= end_idx - start + 1
    # Partition the array and get pivot position
    pos = partition(arr, start, end_idx)

    # If pivot position is the same as k-1, return the element at that position
    if pos - start == k - 1
      return arr[pos]
    end

    # If pivot position is more than k-1, search in the left partition
    if pos - start > k - 1
      return kth_smallest(arr, start, pos - 1, k)
    end

    # Otherwise, continue search in the right partition
    return kth_smallest(arr, pos + 1, end_idx, k - pos + start - 1)
  end
  nil
end

numbers = [1, 7, 2, 4, 2, 1, 6]
puts find_kth_smallest(numbers, 5)  # It should print 4

After we form the partitions, we compare the pivot's position to k. If the positions match, our pivot is the k-th smallest element. If our k is smaller, we look at the left partition; otherwise, the right one.

Problem 2: Solution Building – Main Logic

Implement the Merge Sort with inversion counting:

Ruby

def merge_and_count_inversions(left, right)
  merged = []  # Array to hold the merged sorted elements
  inversions = 0  # Counter for counting inversions
  i = 0  # Index for iterating through the left array
  j = 0  # Index for iterating through the right array

  # Merge the two arrays while counting inversions
  while i < left.length && j < right.length
    # If the current element of left is less than or equal to right, append it
    if left[i] <= right[j]
      merged << left[i]
      i += 1
    else
      # Element from right is less, contributing to inversions
      merged << right[j]
      j += 1
      inversions += left.length - i  # Count inversions
    end
  end

  # Append any remaining elements from left array
  merged.concat(left[i..-1]) if i < left.length
  
  # Append any remaining elements from right array
  merged.concat(right[j..-1]) if j < right.length

  [merged, inversions]  # Return the merged array and count of inversions
end

numbers = [4, 2, 1, 3]
_, inversions = count_inversions(numbers)
puts inversions  # It should print 4

def merge_and_count_inversions(left, right)
  merged = []  # Array to hold the merged sorted elements
  inversions = 0  # Counter for counting inversions
  i = 0  # Index for iterating through the left array
  j = 0  # Index for iterating through the right array

  # Merge the two arrays while counting inversions
  while i < left.length && j < right.length
    # If the current element of left is less than or equal to right, append it
    if left[i] <= right[j]
      merged << left[i]
      i += 1
    else
      # Element from right is less, contributing to inversions
      merged << right[j]
      j += 1
      inversions += left.length - i  # Count inversions
    end
  end

  # Append any remaining elements from left array
  merged.concat(left[i..-1]) if i < left.length
  
  # Append any remaining elements from right array
  merged.concat(right[j..-1]) if j < right.length

  [merged, inversions]  # Return the merged array and count of inversions
end

numbers = [4, 2, 1, 3]
_, inversions = count_inversions(numbers)
puts inversions  # It should print 4

While performing the merge in Merge Sort, we have added an additional counter to track inversions. If we encounter 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 Structure

Problem 2: Solution Building – Main Logic

Lesson Summary

Practice Exercises