Advanced Applications of Sorting Algorithms in C#

Advanced Applications of Sorting Algorithms in C# | CodeSignal Learn

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

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 $O(n^2)$ complexity.

Another straightforward solution is just to sort the input array and return the k-th element:

Array.Sort(inputArray);
return inputArray[k - 1];

This approach has $O(n \log n)$ complexity and is as simple as two lines of code. However, there are more efficient approaches than this, as there is an $O(n)$ solution to this problem, using Quick Sort techniques we covered earlier in this course.

Problem 1: Solution Building – Partition

Our C# solution mirrors this efficient approach as follows. Firstly, we define the partition procedure, the same way we do it in the quick sort: C# static int Partition(int[] arr, int start, int end) {int pivot = arr[start]; int i = start; for (int j = start + 1; j <= end; j++) {if (arr[j] <= pivot) {i++; int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;}} int tempSwap = arr[i]; arr[i] = arr[start]; arr[start] = tempSwap; return i;} static int Partition(int[] arr, int start, int end) {int pivot = arr[start]; int i = start; for (int j = start + 1; j <= end; j++) {if (arr[j] <= pivot) {i++; int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;}} int tempSwap = arr[i]; arr[i] = arr[start]; arr[start] = tempSwap; return i;}

Problem 1: Solution Building – Main Logic

Then, we define the FindKthSmallest algorithm, essentially working as a quicksort, but chasing a different goal: C# using System; class Solution {public static int FindKthSmallest(int[] numbers, int k) {if (numbers == null || numbers.Length < k) return int.MinValue; return KthSmallest(numbers, 0, numbers.Length - 1, k);} static int KthSmallest(int[] arr, int start, int end, int k) {if (k > 0 && k <= end - start + 1) {int pos = Partition(arr, start, end); if (pos - start == k - 1) {return arr[pos];} if (pos - start > k - 1) {return KthSmallest(arr, start, pos - 1, k);} return KthSmallest(arr, pos + 1, end, k - pos + start - 1);} return int.MaxValue;} public static void Main(string[] args) {int[] numbers = { 1, 7, 2, 4, 2, 1, 6 }; Console.WriteLine(FindKthSmallest(numbers, 5)); // It should print 4}} using System; class Solution {public static int FindKthSmallest(int[] numbers, int k) {if (numbers == null || numbers.Length < k) return int.MinValue; return KthSmallest(numbers, 0, numbers.Length - 1, k);} static int KthSmallest(int[] arr, int start, int end, int k) {if (k > 0 && k <= end - start + 1) {int pos = Partition(arr, start, end); if (pos - start == k - 1) {return arr[pos];} if (pos - start > k - 1) {return KthSmallest(arr, start, pos - 1, k);} return KthSmallest(arr, pos + 1, end, k - pos + start - 1);} return int.MaxValue;} public static void Main(string[] args) {int[] numbers = { 1, 7, 2, 4, 2, 1, 6 }; Console.WriteLine(FindKthSmallest(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 – Supporting Class

Here is the C# solution based on the Merge Sort algorithm. First, let's define a supportive class to store our counter for each subarray: C# public class Result {public int[] sorted; public long inversions; public Result(int[] sorted, long inversions) {this.sorted = sorted; this.inversions = inversions;}} public class Result {public int[] sorted; public long inversions; public Result(int[] sorted, long inversions) {this.sorted = sorted; this.inversions = inversions;}}

Problem 2: Solution Building – Main Logic

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 $O(n \log n)$ . 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 $O(n \log n)$ . So, how does this work?

The process starts by dividing the array into two halves, similar to how Merge Sort operates. Then, we recursively sort both array halves and merge them back. Here comes the twist in the tale: while merging these sorted halves, we add additional counting logic to keep track of inversions.

As the halves are already sorted, if an element of the right half is smaller than that of the left half, it's inverted. This is because the element from the right half should have been after 'all' the remaining elements of the left half in a sorted array. Thus, we don't just have a single inversion here, we have as many inversions as there are remaining elements in the left half.

By counting these inversions at each merge and adding them up, we get the total number of inversions in the array.