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!
Picture 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 onwards.
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 due to continuous array rewriting.
