Median of an unsorted array using Quick Select Algorithm | Python3 program to find median of an array ; Returns the correct position of pivot element ; Picks a random pivot element between l and r and partitions arr [ l . . r ] around the randomly picked element using partition ( ) ; Utility function to find median ; if l < r ; Find the partition index ; If partition index = k , then we found the median of odd number element in arr [ ] ; If index = k - 1 , then we get a & b as middle element of arr [ ] ; If partitionIndex >= k then find the index in first half of the arr [ ] ; If partitionIndex <= k then find the index in second half of the arr [ ] ; Function to find Median ; If n is odd ; If n is even ; Print the Median of arr [ ] ; Driver code
import random NEW_LINE a , b = None , None ; NEW_LINE def Partition ( arr , l , r ) : NEW_LINE INDENT lst = arr [ r ] ; i = l ; j = l ; NEW_LINE while ( j < r ) : NEW_LINE INDENT if ( arr [ j ] < lst ) : NEW_LINE INDENT arr [ i ] , arr [ j ] = arr [ j ] , arr [ i ] ; NEW_LINE i += 1 ; NEW_LINE DEDENT j += 1 ; NEW_LINE DEDENT arr [ i ] , arr [ r ] = arr [ r ] , arr [ i ] ; NEW_LINE return i ; NEW_LINE DEDENT def randomPartition ( arr , l , r ) : NEW_LINE INDENT n = r - l + 1 ; NEW_LINE pivot = random . randrange ( 1 , 100 ) % n ; NEW_LINE arr [ l + pivot ] , arr [ r ] = arr [ r ] , arr [ l + pivot ] ; NEW_LINE return Partition ( arr , l , r ) ; NEW_LINE DEDENT def MedianUtil ( arr , l , r , k , a1 , b1 ) : NEW_LINE INDENT global a , b ; NEW_LINE if ( l <= r ) : NEW_LINE INDENT partitionIndex = randomPartition ( arr , l , r ) ; NEW_LINE if ( partitionIndex == k ) : NEW_LINE INDENT b = arr [ partitionIndex ] ; NEW_LINE if ( a1 != - 1 ) : NEW_LINE INDENT return ; NEW_LINE DEDENT DEDENT elif ( partitionIndex == k - 1 ) : NEW_LINE INDENT a = arr [ partitionIndex ] ; NEW_LINE if ( b1 != - 1 ) : NEW_LINE INDENT return ; NEW_LINE DEDENT DEDENT if ( partitionIndex >= k ) : NEW_LINE INDENT return MedianUtil ( arr , l , partitionIndex - 1 , k , a , b ) ; NEW_LINE DEDENT else : NEW_LINE INDENT return MedianUtil ( arr , partitionIndex + 1 , r , k , a , b ) ; NEW_LINE DEDENT DEDENT return ; NEW_LINE DEDENT def findMedian ( arr , n ) : NEW_LINE INDENT global a ; NEW_LINE global b ; NEW_LINE a = - 1 ; NEW_LINE b = - 1 ; NEW_LINE if ( n % 2 == 1 ) : NEW_LINE INDENT MedianUtil ( arr , 0 , n - 1 , n // 2 , a , b ) ; NEW_LINE ans = b ; NEW_LINE DEDENT else : NEW_LINE INDENT MedianUtil ( arr , 0 , n - 1 , n // 2 , a , b ) ; NEW_LINE ans = ( a + b ) // 2 ; NEW_LINE DEDENT print ( " Median ▁ = ▁ " , ans ) ; NEW_LINE DEDENT arr = [ 12 , 3 , 5 , 7 , 4 , 19 , 26 ] ; NEW_LINE n = len ( arr ) ; NEW_LINE findMedian ( arr , n ) ; NEW_LINE