Median of an unsorted array using Quick Select Algorithm | CPP program to find median of an array ; Utility function to swapping of element ; 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 program to test above methods
#include " bits / stdc + + . h " NEW_LINE using namespace std ; void swap ( int * a , int * b ) { int temp = * a ; * a = * b ; * b = temp ; } int Partition ( int arr [ ] , int l , int r ) { int lst = arr [ r ] , i = l , j = l ; while ( j < r ) { if ( arr [ j ] < lst ) { swap ( & arr [ i ] , & arr [ j ] ) ; i ++ ; } j ++ ; } swap ( & arr [ i ] , & arr [ r ] ) ; return i ; } int randomPartition ( int arr [ ] , int l , int r ) { int n = r - l + 1 ; int pivot = rand ( ) % n ; swap ( & arr [ l + pivot ] , & arr [ r ] ) ; return Partition ( arr , l , r ) ; } void MedianUtil ( int arr [ ] , int l , int r , int k , int & a , int & b ) { if ( l <= r ) { int partitionIndex = randomPartition ( arr , l , r ) ; if ( partitionIndex == k ) { b = arr [ partitionIndex ] ; if ( a != -1 ) return ; } else if ( partitionIndex == k - 1 ) { a = arr [ partitionIndex ] ; if ( b != -1 ) return ; } if ( partitionIndex >= k ) return MedianUtil ( arr , l , partitionIndex - 1 , k , a , b ) ; else return MedianUtil ( arr , partitionIndex + 1 , r , k , a , b ) ; } return ; } void findMedian ( int arr [ ] , int n ) { int ans , a = -1 , b = -1 ; if ( n % 2 == 1 ) { MedianUtil ( arr , 0 , n - 1 , n / 2 , a , b ) ; ans = b ; } else { MedianUtil ( arr , 0 , n - 1 , n / 2 , a , b ) ; ans = ( a + b ) / 2 ; } cout << " Median ▁ = ▁ " << ans ; } int main ( ) { int arr [ ] = { 12 , 3 , 5 , 7 , 4 , 19 , 26 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; findMedian ( arr , n ) ; return 0 ; }