Find K’th Smallest/Largest Element in Unsorted Array in Python
From the given array, we have to find the kth number of the smallest or greatest number from unsorted array in Python. The array is unsorted and have distinct elements.
For Example:
Input :
array = [1,4,7,6,3,9] k = 3
Output :
kth smallest number : 4
Input :
array = [7,4,2,8,6,1] k = 2
Output :
kth greatest number : 7
For finding a solution to the problem, we have to sort the array using sorting algorithms like merge sort, heap sort, etc. and return the element at k-1 index (for kth smallest number ) and (-k) index(for the kth greatest number ). The complexity of the sorting algorithm is O(N log N).
Method 1: Normal Sorting
# python program to find the kth smallest/largest number #function for finding the kth largest number def get_largest(array,k): #sort the unsorted array arr = array.sort() print(array[k-1]) #function for finding the k th smallest number: def get_smallest(array,k): #sort the unsorted array arr = array.sort() print(array[-k]) #driver code l = [1,4,9,3,6,8] get_largest(l,3) get_smallest(l,2)
Output:
4 8
Method 2: Heap Sorting
# Python program for getting a kth smallest/largest value from the unsorted array def heaping (array, n, k): # let the greatest element be at index k # so k will be the root element greatest = k #for left hand branching left = 2*k + 1 #for right hand branching right = 2*k + 2 #if left child of the root is greater than the root #then change root to left child if left < n and array[k] < array[left]: greatest = left #if right child of the root is greater than the root # change root to right child if right < n and array[greatest] < array[right]: greatest = right #if the value of root is less than the value at kth index # swap them if greatest != k : #swap between two element array[greatest],array[k] = array[k],array[greatest] #Sort the given array of size n def max_heap(array,n): #max heap for i in range(n, -1, -1): heaping(array, n, i) for num in range(n-1, -1, -1): #swap between two element array[num], array[0] = array[0], array[num] heaping(array,num, 0) # Driver code array = [ 12, 11, 13, 5, 6, 7] n = len(array) max_heap(array, n) k = 3 #for kth smallest child print(array[k-1]) #for kth greatest child print(array[-k])
Output:
7 11
Leave a Reply