Hello Guys, In this post I will be talking about an efficient way for finding Kth smallest Number in a given list of numbers. There are several methods for finding this number.
One such method is, by first sorting the array an then just access the K-th number. This will cost you O(n log(n)) time complexity.(I won't be talking about the brute force method which is approximately of order O(n*n) )
Another method is using the Divide And conquers paradigm. The key step in this method is using O(n) Partition method as we use in Quick Sort.
What do we basically do in this partitioning method??:->
We have a function Randomized_partition(A,start,end);
1. First, choose any random index of the given array to choose it as a pivot element around which partition is to be done.
2. Once the partition function works it places the pivot element in the correct position . i.e the elements greater than the pivot element are towards the right of it and the elements smaller than pivot element is towards the left of the pivot element.
3.We note down the index of the pivot element let it is p. Now we have three cases left with us :
a.) p = k-1 (that pivot index is equal to the kth smallest number index ) return this number.
b.) p <k-1, the desired answer is in the right partition.
c.) p> k-1, the desired answer is in the left partition.
We keep on repeating this process until we get the required answer
One such method is, by first sorting the array an then just access the K-th number. This will cost you O(n log(n)) time complexity.(I won't be talking about the brute force method which is approximately of order O(n*n) )
Another method is using the Divide And conquers paradigm. The key step in this method is using O(n) Partition method as we use in Quick Sort.
What do we basically do in this partitioning method??:->
We have a function Randomized_partition(A,start,end);
1. First, choose any random index of the given array to choose it as a pivot element around which partition is to be done.
2. Once the partition function works it places the pivot element in the correct position . i.e the elements greater than the pivot element are towards the right of it and the elements smaller than pivot element is towards the left of the pivot element.
3.We note down the index of the pivot element let it is p. Now we have three cases left with us :
a.) p = k-1 (that pivot index is equal to the kth smallest number index ) return this number.
b.) p <k-1, the desired answer is in the right partition.
c.) p> k-1, the desired answer is in the left partition.
We keep on repeating this process until we get the required answer
