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!
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!
A primary instinctive solution could involve iteratively identifying and discarding the smallest element from the list until you reach the k
-th smallest element. While it sounds straightforward, this approach, unfortunately, incurs high time complexity due to the repetitive scans of the list to locate the smallest element. This solution has an complexity.
Another straightforward solution is to sort the input array and return the k
-th element:
Ruby1input_array.sort! 2return input_array[k - 1]
This approach has complexity and is as simple as two lines of code. However, there are more efficient approaches than this, as there is an solution to this problem, using Quick Sort
techniques we covered earlier in this course.
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.
Here is how we can implement the partition process in Ruby:
Ruby1def partition(arr, start, end_idx) 2 pivot = arr[start] 3 i = start 4 5 (start + 1).upto(end_idx) do |j| 6 if arr[j] <= pivot 7 i += 1 8 arr[i], arr[j] = arr[j], arr[i] 9 end 10 end 11 12 arr[i], arr[start] = arr[start], arr[i] 13 i 14end
Then, we define the find_kth_smallest
algorithm, essentially working as a quicksort, but chasing a different goal:
Ruby1def find_kth_smallest(numbers, k) 2 # If the numbers array is nil or has fewer elements than k, return nil 3 return nil if numbers.nil? || numbers.length < k 4 5 # Start the recursive search for the k-th smallest element 6 kth_smallest(numbers, 0, numbers.length - 1, k) 7end 8 9def kth_smallest(arr, start, end_idx, k) 10 # Check if the k is within the valid range 11 if k > 0 && k <= end_idx - start + 1 12 # Partition the array and get pivot position 13 pos = partition(arr, start, end_idx) 14 15 # If pivot position is the same as k-1, return the element at that position 16 if pos - start == k - 1 17 return arr[pos] 18 end 19 20 # If pivot position is more than k-1, search in the left partition 21 if pos - start > k - 1 22 return kth_smallest(arr, start, pos - 1, k) 23 end 24 25 # Otherwise, continue search in the right partition 26 return kth_smallest(arr, pos + 1, end_idx, k - pos + start - 1) 27 end 28 nil 29end 30 31numbers = [1, 7, 2, 4, 2, 1, 6] 32puts 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.
Our second problem entails a list of integers; your task is to deduce the number of inversions in the list.
An inversion is a pair of elements where the larger element appears before the smaller one. In other words, if we have two indices i
and j
, where i < j
and the element at position i
is greater than the element at position j
(numbers[i] > numbers[j]
), we have an inversion.
For example, for numbers = {4, 2, 1, 3}
, there are four inversions: (4, 2)
, (4, 1)
, (4, 3)
, and (2, 1)
.
In our quest for efficiency, the Merge Sort
algorithm comes into play. At its core, Merge Sort
is a divide-and-conquer-based sorting algorithm, providing an optimal efficiency of . However, we can cleverly modify this algorithm to count the number of inversions in the array while sorting it. This additional functionality doesn't impact the time complexity; therefore, it remains .
In Ruby, we can use a simple array to encapsulate the result instead of a class:
Ruby1def count_inversions(arr) 2 if arr.length <= 1 3 return [arr, 0] 4 end 5 6 middle = arr.length / 2 7 left_sorted, left_inversions = count_inversions(arr[0...middle]) 8 right_sorted, right_inversions = count_inversions(arr[middle..-1]) 9 merged_sorted, split_inversions = merge_and_count_inversions(left_sorted, right_sorted) 10 11 [merged_sorted, left_inversions + right_inversions + split_inversions] 12end
Implement the Merge Sort with inversion counting:
Ruby1def merge_and_count_inversions(left, right) 2 merged = [] # Array to hold the merged sorted elements 3 inversions = 0 # Counter for counting inversions 4 i = 0 # Index for iterating through the left array 5 j = 0 # Index for iterating through the right array 6 7 # Merge the two arrays while counting inversions 8 while i < left.length && j < right.length 9 # If the current element of left is less than or equal to right, append it 10 if left[i] <= right[j] 11 merged << left[i] 12 i += 1 13 else 14 # Element from right is less, contributing to inversions 15 merged << right[j] 16 j += 1 17 inversions += left.length - i # Count inversions 18 end 19 end 20 21 # Append any remaining elements from left array 22 merged.concat(left[i..-1]) if i < left.length 23 24 # Append any remaining elements from right array 25 merged.concat(right[j..-1]) if j < right.length 26 27 [merged, inversions] # Return the merged array and count of inversions 28end 29 30numbers = [4, 2, 1, 3] 31_, inversions = count_inversions(numbers) 32puts 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.
During today's lesson, we thoroughly inspected the advanced applications of Quick Sort
and Merge Sort
algorithms through the dissection of two exciting problems. We went from recognizing the issues, proposing naive methods, progressing towards efficient approaches, and executing the Ruby solutions.
You're now ready to flex those coding muscles! We have covered a substantial amount of theory and strongly advocate that real-world application solidifies the lessons learned. Be prepared for the forthcoming exercises, where you'll apply the logic imbibed in this session to similar problems. Let's get hands-on!
