Find median of an array using Quick Select Algorithm in C++

In this post, we are going to learn about Find median of an array using a Quick Select Algorithm in C++. This post will help you to understand better the concept of a quick-select algorithm. After that, we will implement the code.

Quick Select Algorithm for an unsorted array.

Suppose we have an unsorted array with an array named arr[] with a length of size N, then the task is to find the median of this array.

If n is even it is an average of two middle elements when n is odd it is defined as the middle element.

See Example

Our Input: {2,3,4,10,15,16,11}

Output: 10 


Our Input: arr[] = {1, 2, 3, 4, 5, 6}
Output: 3

Here in the above input, there are even a number of elements so the median is taken as the average of  the elements which means (3+ 4)/2 = 3

Method

a. The array arr[] should be in increasing order, so sort it first.

b. Next, the median is arr[n/2] if arr[] is odd.

c. Average of arr[n/2] and arr[n/2+1] is median if arr[] is even. 

Quick Select Method

1. First, pick a pivot element randomly from arr[] then use the partition step from the quick sort algorithm. Th0se elements arranged on the right side. If it is greater than the pivot element and the elements smaller than it on its left.

2. Then after the above step, it is the median of the given array if the position of the chosen pivot is the middle of the array.

3. In other cases, do the step again for the subarray for this er have to star from the previous starting index and the chosen pivot as the ending index if the position is before the middle element.

4. Apart from this, do the step again for the subarray starting from the chosen pivot, and ending at the previous ending, index ith position is after the middle element.

After finding 2 middle elements and their average will be the median of the array in the case of an even number of elements.

  
#include "bits/stdc++.h" 
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 
    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 fMedian(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[] = { 1, 3, 5, 4, 9, 10, 6 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    fMedian(arr, n); 
    return 0; 
} 
Output:4

Also read: Program on Quicksort on Linked List in C++

One response to “Find median of an array using Quick Select Algorithm in C++”

  1. Hussein M.Rada says:

    1- a program to generate random number from 1-10 and display each separately
    2- program to initialize a vector to store the students grades and display their grade distribution.
    3- program to read several input from the user and count how many 10’s are entered.

Leave a Reply

Your email address will not be published. Required fields are marked *