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