In this blog, we will create a program to find the difference between two sorted arrays in C++ programming language.

What is “Median of an array”?

If the array is sorted, the median is the middle element of the array if the number of elements in the array is odd, and when the number of elements in the array is even, it will be the average of the two middle elements.

Algorithm for the respective code

1. Load both data sets of length m and n.
2. Sort the data files using the quicksort algorithm.
3. Calculate the median, treating both fields as a single field.
4. The end.

C++ code for the respective program

#include<iostream>
 
using namespace std;
 
// Swapping two values.
void swap(int *a, int *b)
{
    int temp; 
    temp = *a;
    *a = *b;
    *b = temp;
}
 
// Partitioning the array on the basis of values at high as pivot value.
int Partition(int a[], int low, int high)
{
    int pivot, index, i;
    index = low;
    pivot = high;
 
    // Getting index of pivot.
    for(i=low; i < high; i++)
    {
        if(a[i] < a[pivot])
        {
            swap(&a[i], &a[index]);
            index++;
        }
    }
    // Swapping value at high and at the index obtained.
    swap(&a[pivot], &a[index]);
 
    return index;
}
 
// Implementing QuickSort algorithm.
int QuickSort(int a[], int low, int high)
{
    int pindex;
    if(low < high)
    {
        // Partitioning array using randomized pivot.
        pindex = Partition(a, low, high);
        // Recursively implementing QuickSort.
        QuickSort(a, low, pindex-1);
        QuickSort(a, pindex+1, high);
    }
    return 0;
}
 
int main()
{
    int n, m, bi, ai, i, k;
    double median;
    cout<<"Enter the number of element in the first data set: ";
    cin>>n;
 
    int a[n];
    // Take input of first sequence.
    for(i = 0; i < n; i++)
    {
        cout<<"Enter "<<i+1<<"th element: ";
        cin>>a[i];
    }
 
    cout<<"\nEnter the number of element in the second data set: ";
    cin>>m;
 
    int b[m];
    // Take input of second sequence.
    for(i = 0; i < m; i++)
    {
        cout<<"Enter "<<i+1<<"th element: ";
        cin>>b[i];
    }
 
    // Sort the data of both arrays.
    QuickSort(a, 0, n-1);
    QuickSort(b, 0, m-1);
 
    //Print the result.
    cout<<"\tThe Median from these data set is: ";
    ai = 0;
    bi = 0;
    // If the m+n is odd then one median will be there otherwise average of two will be taken as median.
    if((m+n)%2 == 1)
    {
        // K is the number of element present upto the median from the beginning of the data array.
        k =(n+m)/2+1;
        while(k > 0)
        {
            // Compare current element of array 'a' and 'b' and skip next the smaller one.
            if(a[ai] <= b[bi] && ai < n)
            {
                k--;
                // Print if we have skipped k element.
                if(k == 0)
                    cout<<a[ai];
                ai++;
            }
            else if(a[ai] > b[bi] && bi < m)
            {
                k--;
                // Print if we have skipped k element.
                if(k == 0)
                    cout<<b[bi];
                bi++;
            }
        }
    }
    else
    {	
        k = (n+m)/2+1;
        while(k > 0)
        {
            // Compare current element of array 'a' and 'b' and skip next the smaller one.
            if(a[ai] <= b[bi] && ai < n)
            {
                k--;
                // Add the last two numbers so as we can calculate average.
                if(k <= 1)
                    median += a[ai];
                ai++;
            }
            else if(a[ai] > b[bi] && bi < m)
            {
                k--;
                // Add the last two numbers so as we can calculate average.
                if(k <= 1)
                    median += b[bi];
                bi++;
            }
        }
        // Take average.
        cout<<median/2;
    }
}

Output of the above code

Explanation of the code

1. Take the input of the first data set as field “a” of length “n” and the second data set as “b” of length “m”.
2. Call the QuickSort() function to sort both sets of data.
3. Check that m+n is odd, then assign k as “(m+n)/2 + 1” and skip the first m+n smallest elements from both arrays to get the combined median.
4. Otherwise, if m+n is even, then assign k as ‘(m+n)/2 + 1’ and skip the first m+n-1 smallest elements from both arrays.
5. Take the average of the next two smallest elements as the combined average.
6. Print the median.
7. The end.