C++ Programming Code Examples

C++ > Sorting Searching Code Examples

C++ Program to Find Median of Two Sorted Arrays



C++ Program to Find Median of Two Sorted Arrays

This is a C++ Program find the median of elements where elements are stored in 2 different arrays.

- We need to find combined median of two different data set.
- It includes sorting of both arrays using quick sort and then printing the median by simultaneously traversing both arrays.
- The time complexity will be O(n*log(n)+m*log(m)+m+n).

- Take input of both the data set of length m and n respectively.
- Sort the data sets using the quick-sort algorithm.
- Calculate the median, considering both arrays as a single array.
- Exit.

#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;
	}
}