TypeScript Adventures in Sorting Algorithms: Quick Sort and Merge Sort Applications

TypeScript Adventures in Sorting Algorithms: Quick Sort and Merge Sort Applications | CodeSignal Learn

Introduction

Ready for an adventure in sorting algorithms ? We will solve two fun problems: "Find the K-th Ordinal Number in a List" and "Count the Number of Flips in a List" . These tasks portray situations where we need clever system design. Let's employ quick sort and merge sort to find efficient solutions. Buckle up!

Problem 1: Finding K-th Number in an Array

Imagine an array of numbers and a number k . Your mission is to discover the k -th smallest number in that array. k starts from 1, so when k = 1, we seek the smallest number; when k = 2, we want the second smallest, and onward.

Problem 1: Simple Solutions

O(n^2)

Problem 1: Quick Sort to the Rescue

Quick sort can provide an optimal solution. We’ll divide the array into two parts using a pivot: the left side contains numbers less than the pivot, while the right side has all greater numbers. If the pivot's position equals k, that's our answer! If not, we repeat the process on the necessary partition.

Problem 1: Building the Solution – Partition

It's coding time! Let’s make a function for partitioning in TypeScript. TypeScript function partition(arr: number[], low: number, high: number): number {const pivot = arr[low]; // Select pivot let i = low; // Index of smaller element for (let j = low + 1; j <= high; j++) {if (arr[j] <= pivot) {i++; [arr[i], arr[j]] = [arr[j], arr[i]]; // Swap elements}} [arr[i], arr[low]] = [arr[low], arr[i]]; // Swap pivot return i; // Return pivot index}

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

The first solution might involve scanning and shrinking the array by removing the smallest number until you reach the k-th smallest. But this method, while straightforward, has a time complexity of $O(n^2)$ due to continuous array rewriting.

An efficient plan might be to sort the array and then directly select the k-th number:

TypeScript

function findKthNumber(inputArray: number[], k: number): number {
  inputArray.sort((a, b) => a - b); // Sort array ascending
  return inputArray[k - 1]; // Return k-th element
}

This method has a better time complexity — $O(n \log n)$ . But can we do even better? Quick sort thinks so.

Problem 1: Building the Solution – Main Logic

Now we use our partition function in the main logic. If the pivot's position equals k, return the pivot. Otherwise, check the appropriate partition! TypeScriptfunction findKthSmallest(numbers: number[], k: number): number { if (!numbers || numbers.length < k) return Number.MIN_SAFE_INTEGER; return kthSmallest(numbers, 0, numbers.length - 1, k); } function kthSmallest(arr: number[], start: number, end: number, k: number): number { if (k > 0 && k <= end - start + 1) { const pos = partition(arr, start, end); // Get partition index if (pos - start === k - 1) { return arr[pos]; // K-th element found } if (pos - start > k - 1) { return kthSmallest(arr, start, pos - 1, k); // Search left part } return kthSmallest(arr, pos + 1, end, k - pos + start - 1); // Search right part } return Number.MAX_SAFE_INTEGER; } console.log(findKthSmallest([1, 7, 2, 4, 2, 1, 6], 5)); // Prints 4function findKthSmallest(numbers: number[], k: number): number { if (!numbers || numbers.length < k) return Number.MIN_SAFE_INTEGER; return kthSmallest(numbers, 0, numbers.length - 1, k); } function kthSmallest(arr: number[], start: number, end: number, k: number): number { if (k > 0 && k <= end - start + 1) { const pos = partition(arr, start, end); // Get partition index if (pos - start === k - 1) { return arr[pos]; // K-th element found } if (pos - start > k - 1) { return kthSmallest(arr, start, pos - 1, k); // Search left part } return kthSmallest(arr, pos + 1, end, k - pos + start - 1); // Search right part } return Number.MAX_SAFE_INTEGER; } console.log(findKthSmallest([1, 7, 2, 4, 2, 1, 6], 5)); // Prints 4 Number.MIN_SAFE_INTEGER is returned by findKthSmallest if the input array numbers is empty or has fewer elements than k. This could represent a case where the k smallest value doesn't exist. Number.MAX_SAFE_INTEGER is used in the kthSmallest function if k is either less than 1 or greater than the length of the portion of the array being considered. This could mean that there's an error in the k parameter passed, or the array doesn't have enough elements. These extreme values are used because they are unlikely to be a valid result in any normal situation, making it easy to spot when something has gone wrong. It's a convention to return values that clearly indicate error situations, aiding in debugging and error handling.

Problem 2: Building the Solution – Helper Function

We begin with a mergeAndCount helper function in TypeScript: TypeScript function mergeAndCount(arr1: number[], arr2: number[]): [number[], number] {let i = 0; let j = 0; const merged: number[] = []; let inversions = 0; while (i < arr1.length || j < arr2.length) {if (i === arr1.length) {merged.push(arr2[j]); // Add remaining right j++;} else if (j === arr2.length) {merged.push(arr1[i]); // Add remaining left i++;} else if (arr1[i] <= arr2[j]) {merged.push(arr1[i]); // Add smaller left i++;} else {merged.push(arr2[j]); // Add smaller right j++; inversions += (arr1.length - i); // Count inversions}} return [merged, inversions];} function mergeAndCount(arr1: number[], arr2: number[]): [number[], number] {let i = 0; let j = 0; const merged: number[] = []; let inversions = 0; while (i < arr1.length || j < arr2.length) {if (i === arr1.length) {merged.push(arr2[j]); // Add remaining right j++;} else if (j === arr2.length) {merged.push(arr1[i]); // Add remaining left i++;} else if (arr1[i] <= arr2[j]) {merged.push(arr1[i]); // Add smaller left i++;} else {merged.push(arr2[j]); // Add smaller right j++; inversions += (arr1.length - i); // Count inversions}} return [merged, inversions];} The mergeAndCount function merges two sorted arrays, arr1 and arr2, while counting inversions, which occur when an element from arr2 is smaller than the remaining elements in arr1 . It returns the merged array and the inversion count.

Problem 2: Building the Solution – Main Function

Finally, we develop countInversions, aided by mergeAndCount : TypeScript function countInversions(arr: number[]): [number[], number] {if (arr.length === 1) return [arr, 0]; // Base case const middle = Math.floor(arr.length / 2); const [left, leftInversions] = countInversions(arr.slice(0, middle)); const [right, rightInversions] = countInversions(arr.slice(middle)); const [merged, mergeInversions] = mergeAndCount(left, right); return [merged, leftInversions + rightInversions + mergeInversions]; // Total inversions} console.log(countInversions([4, 2, 1, 3])); // Prints [ [ 1, 2, 3, 4 ], 4 ] function countInversions(arr: number[]): [number[], number] {if (arr.length === 1) return [arr, 0]; // Base case const middle = Math.floor(arr.length / 2); const [left, leftInversions] = countInversions(arr.slice(0, middle)); const [right, rightInversions] = countInversions(arr.slice(middle)); const [merged, mergeInversions] = mergeAndCount(left, right); return [merged, leftInversions + rightInversions + mergeInversions]; // Total inversions} console.log(countInversions([4, 2, 1, 3])); // Prints [ [ 1, 2, 3, 4 ], 4 ] The countInversions function recursively splits an array into halves, sorts them, and merges the sorted halves back while counting inversions using the mergeAndCount helper. It returns a tuple containing the sorted array and the total number of inversions, effectively combining the counting and sorting processes into one efficient operation.

Merge sort can efficiently solve this. It sorts an array in $O(n \log n)$ by splitting it, sorting the halves, and merging them. During this process, we can count the inversions.

When merging, a smaller number on the right than a number on the left reveals an inversion. And it's not just one: there are as many inversions as the remaining numbers on the left.