Median finding
Problem Statement:
find median of elements in an array.
Algorithm 1: Naive algorithm
1. Sort array
2. Get the middle element
Code :
// O(nlogn) for sorting
// O(1) for getting median by sorting array
#include <bits/stdc++.h>
using namespace std;
float median(int a[], int n)
{
sort(a, a + n);
int m = n / 2;
if (n % 2 == 0)
{
return (float)(a[m - 1] + a[m]) / 2; // avg of m th and m+1 th elements but in 0 indexing they are m-1 and m th elements
}
else
{
return a[m]; // middle element which is (n-1)/2
}
}
int main()
{
int n, k;
cout << "Enter n: ";
cin >> n;
int a[n];
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
cout << "median = " << median(a, n) << "\n";
}
Complexity Analysis :
Time complexity : \(O(nlogn)\) (which is for sorting)
Algorithm 2 : using kth smallest element method ( without using median of medians ).
1. we just find kth smallest in the array for k = n/2
Code :
// using kth smallest element method
// here we just say median is n/2 th no matter wether n is even or odd
// 1 2 3 4 -> median = 2
// 1 2 3 -> median = 2
#include <bits/stdc++.h>
using namespace std;
int quick_partition(int a[], int start, int end)
{
int pivot = end;
int i = start;
int j = i;
/* for every element a[j] if a[j] <= a[pivot]
then swap it with position a[i] and increse both i and j by 1
else increase j by 1*/
while (j < end)
{
if (a[j] <= a[pivot])
{
swap(a[i], a[j]);
i++;
}
j++;
}
/* finally i will be the first position where a[i]>a[pivot]
so we swap these and pivot will be ith position*/
swap(a[i], a[pivot]);
return i;
}
int quick_select_kth(int a[], int start, int end, int k)
{
int pivot;
while (start <= end)
{
pivot = quick_partition(a, start, end);
int pivot_distance = pivot - start + 1;
// cout << "start = " << start << " end = " << end << " pivot = " << pivot << "\n";
if (pivot_distance == k)
{
return a[pivot];
}
else if (pivot_distance > k)
{
end = pivot - 1;
}
else
{
k -= pivot_distance;
start = pivot + 1;
}
}
return INT_MAX;
}
float median(int a[], int n)
{
return quick_select_kth(a, 0, n - 1, n / 2);
}
int main()
{
int n, k;
cout << "Enter n: ";
cin >> n;
int a[n];
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
cout << "median = " << median(a, n) << "\n";
}
Complexity Analysis :
best case : \(O(n)\)
worst case \(O(n^2)\)
So complexity lies between these two extremes based on the pivot selection.
Algorithm 3: using kth smallest element method ( using median of medians )
1. we find kth smallest in array using quick_select_kth algorithm where pivot is median of medians
2. call quick_select_kth with k = n/2
Code :
// using kth smallest element method with pivot as median of medians
// here we just say median is n/2 th no matter wether n is even or odd
// 1 2 3 4 -> median = 2
// 1 2 3 -> median = 2
#include <bits/stdc++.h>
using namespace std;
float median(int a[], int n);
int quick_select_kth(int a[], int start, int end, int k);
int quick_partition(int a[], int start, int end);
int find_median_of_medians(int a[], int start, int end);
int main()
{
int n, k;
cout << "Enter n: ";
cin >> n;
int a[n];
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
cout << "median = " << median(a, n) << "\n";
}
int find_median_of_medians(int a[], int start, int end)
{
int n = end - start + 1;
int median[(int)ceil((float)n / 5)];
int i = 0;
int *ptr = a + start;
for (; i < n / 5; i++)
{
sort(ptr, ptr + 5);
median[i] = *(ptr + 3);
ptr += 5;
}
if (i * 5 < n)
{
sort(ptr, ptr + n % 5);
median[i] = *(ptr + (n % 5) / 2);
i++;
}
int median_of_medians;
if (i == 1)
{
median_of_medians = median[i - 1];
}
else
{
median_of_medians = quick_select_kth(median, 0, i - 1, i / 2);
}
return median_of_medians;
}
int quick_partition(int a[], int start, int end)
{
// move median to end
int median_of_medians = find_median_of_medians(a, start, end);
int x = start;
for (; x <= end; x++)
{
if (a[x] == median_of_medians)
{
break;
}
}
swap(a[x], a[end]);
//////////////////////////////////////////////////
int pivot = end;
int i = start;
int j = i;
/* for every element a[j] if a[j] <= a[pivot]
then swap it with position a[i] and increse both i and j by 1
else increase j by 1*/
while (j < end)
{
if (a[j] <= a[pivot])
{
swap(a[i], a[j]);
i++;
}
j++;
}
/* finally i will be the first position where a[i]>a[pivot]
so we swap these and pivot will be ith position*/
swap(a[i], a[pivot]);
return i;
}
int quick_select_kth(int a[], int start, int end, int k)
{
int pivot;
while (start <= end)
{
pivot = quick_partition(a, start, end);
int pivot_distance = pivot - start + 1;
// cout << "start = " << start << " end = " << end << " pivot = " << pivot << "\n";
if (pivot_distance == k)
{
return a[pivot];
}
else if (pivot_distance > k)
{
end = pivot - 1;
}
else
{
k -= pivot_distance;
start = pivot + 1;
}
}
return INT_MAX;
}
float median(int a[], int n)
{
return quick_select_kth(a, 0, n - 1, n / 2);
}
Complexity Analysis :
Time complexity : \(O(n)\)