Algorithms are the riches of any programming language. The major objective of any algorithm is being efficient and optimized. For any logical scenarios, the prime and foremost is designing an algorithm. In this article, we shall we be discussing one such scenario to determine the k-th maximum / minimum number. The problem This is also one of the interview questions asked. Given 'n' random numbers. Determine the k-th ranked number from the set. Now here, the problem definition is pretty generic as the ranking could be ascending or descending order. This is because the logic would be same for this algorithm irrespective of to find max or min. An example problem could be " Find the 6th smallest number from a set of 10 random numbers " Jot down the algorithms you can think of before moving on to the next section. The Solutions There could be a number of solutions to the above stated problem. In this article, we shall be discussing a few and finally will be implementing one in C. First of all, if, suppose the value of k is very small or really big very close to the number of elements in the set, we have a quicker and efficient solution. As in for example, we need to determine second smallest number in a set of 50 numbers. Note, the value of k is ‘2’, which is pretty small. Now here, what we can simply do is: Put all the elements in an array. This is our main array. Take an extra storage of array of size 2. Lets term it as short-min-array. Traverse the array in a loop. Place the first two elements of the main array in the short-min-array. Now these are the smallest numbers being traversed so far. Keep traversing the array in a loop, and comparing each with the two numbers in the short-min-array. Within the loop, on each comparison, replace the larger of the short-min-array with any smaller number from the traversed main array. Run the loop until you reach the last element of the main array. Now, in the end, the short-min-array would have the smallest two numbers from the main array. The larger of the two in the short-min-array would be the second smallest number, hence the answer. This was pretty efficient as we just had to traverse the array just once with some little extra space of memory to get our answer. However, it would work only if were to find max/min, second or third max/min number. Secondly, the simple raw solution could be: Store all the elements in an array Sort the array Get the element at k-th index of the array, which would be our answer. For sorting you can use any of the standard sorting algorithm. However, this approach would not be that efficient. As in, if we have a big set of elements, then it would be a big overhead to sort all the elements, whatsoever be the complexity of the sorting algorithm. The next approach that we would be discussing is the most efficient for most of the cases in this article. The approach is based determining our answer element such that all the elements on its left are lesser than it, and all the elements on the right side are greater than it(vice versa in case the order is descending). Note, here we don’t care if all other elements are sorted or not. What we care is our concerned number to be in the correct position somehow. In case readers are aware of quick sorting algorithm, they would immediately come to know that this approach is based the same concept of quick sort. So here is the algorithm explained : Step 1 : Put all the elements in an array and the rank 'k' in a variable. Step 2 : Choose one pivot element, could be any random element of the array. Step 3 : Swap the pivot element with the last element of the number to keep it out of the array. Step 4 : Now, use one iterator moving forward to traverse from first element of the array. Lets call this iterator as 'left' as it starts from left. Step 5 : Traverse using the left iterator, comparing each with the pivot element until we get an element larger than the pivot element. Step 6 : Next, use another iterator (called right) to traverse from the last element of the array, until we get to an element lesser than the pivot element. Step 7 : Now if the right is greater than left, swap the two elements determined in step 5 and step 6. Step 8 : Run the loop including steps 5 through 7, until left is lesser than right. (Keep in mind, we are computing the correct position of pivot element in the array). Step 9 : When out of this loop, swap the pivot element with the right element. With this, the pivot element is at its right position. Step 10: Now compare the pivot with our k-value. If both are same, that means we've got our answer. Step 11: In case k is lesser than pivot, then run the whole algorithm for left sub-array i.e. the array of elements to the left of pivot (excluding pivot). Step 12: In case k is greater than pivot, then run the whole algorithm for the right sub-array. i.e. the array of elements to the right of pivot (excluding pivot). Step 13: Keep running till we get out k value as our pivot. Step 14: Once we get pivot as k, we got our Answer! This algorithm would be the most efficient as we are not taking the headache of sorting the array, instead focused on just the pivot value determined as k. However, there could be several variations in the implementation of this algorithm. The variations could be the way, the pivot element is chosen. There could be best or worse case scenarios in this respect. An Implementation in C Here I have a sample implementation of the last discussed solution approach in C. Please go through the program to understand the intricacies of the algorithm. Before we start, here are a few assumptions of the program: This implementation determines the k-th minimum number in a set of numbers. The rightmost element is directly chosen as the pivot element. The random elements are hard-coded in the program for simplicity. The program takes k as input. Here are the elements taken by the program: Code: 3, 6, 2, 8, 4, 7, 1, 5 The Complete Program: Code: /* The pivot is taken always as the rightmost number of the sub-array */ #include <stdio.h> #include <stdlib.h> #define MAX 8 int getKth( int array[], int first, int last, int k) { int temp; int resIndex = -1; int left, right, pivot; //The pivot is taken always as the rightmost number of the sub-array pivot = last; left = first; right = last - 1; if (first == last) //just one element left return first; while ( left < right) { while (array[left] < array[pivot]) left += 1; while (array[right] >= array[pivot]) right -= 1; if (left < right) { //swap values at index left and right temp = array[left]; array[left] = array[right]; array[right] = temp; } } //swap pivot and right temp = array[pivot]; array[pivot] = array[left]; array[left] = temp; pivot = left; if ( k == pivot) { printf("Found the kth element\n"); return pivot; } else { if (k < pivot) { resIndex = getKth (array, first, (pivot - 1), k); } else { resIndex = getKth (array, (pivot + 1), last, k); } } return resIndex; } int main() { int array[MAX] = {3, 6, 2, 8, 4, 7, 1, 5}; int k; int index = -1; printf("Enter the value of k\n"); scanf("%d", &k); if (k > MAX || k <= 0) { printf("Invalid k-value, Ranking starts from 1 to %d\n", MAX); } else { index = getKth(array, 0, (MAX - 1), (k - 1));//index for k-th elem would be k-1 printf("The %d -th element in array is %d\n", k, array[index]); } return 0; } An example output of the program: Code: rupali@home-OptiPlex-745:~/programs/quicksort$ ./quicksort Enter the value of k 6 Found the kth element The 6 -th element in array is 6 Conclusion This article discusses a few approaches to determine the k-th element in a set of numbers along with an implementation which is always required for a clearer and better understanding. However, we are all ears for any better and efficient approach our readers have in mind. So keep thinking.
