Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
median_search.cpp File Reference

Implementation of Median search algorithm. @cases from here More...

#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
Include dependency graph for median_search.cpp:

Namespaces

 search
 Search algorithms.
 
 

Functions

int search::median_search::median_of_medians (const std::vector< int > &A, const int &idx)
 
void test ()
 
int main ()
 

Detailed Description

Implementation of Median search algorithm. @cases from here

Given an array A[1,...,n] of n numbers and an index i, where 1 ≤ i ≤ n, find the i-th smallest element of A. median_of_medians(A, i): #divide A into sublists of len 5 sublists = [A[j:j+5] for j in range(0, len(A), 5)] medians = [sorted(sublist)[len(sublist)/2] for sublist in sublists] if len(medians) <= 5: pivot = sorted(medians)[len(medians)/2] else: #the pivot is the median of the medians pivot = median_of_medians(medians, len(medians)/2) #partitioning step low = [j for j in A if j < pivot] high = [j for j in A if j > pivot] k = len(low) if i < k: return median_of_medians(low,i) elif i > k: return median_of_medians(high,i-k-1) else: #pivot = k return pivot

Note
this algorithm implements median search for only arrays which have distinct elements

Here are some example lists you can use to see how the algorithm works A = [1,2,3,4,5,1000,8,9,99] (Contain Unique Elements) B = [1,2,3,4,5,6] (Contains Unique Elements) print median_of_medians(A, 0) #should be 1 print median_of_medians(A,7) #should be 99 print median_of_medians(B,4) #should be 5

Author
Unknown author
Sushil Kumar

Function Documentation

◆ main()

int main ( void  )

Main function

129 {
130  test();
131  int n = 0;
132  std::cout << "Enter Size of Array: ";
133  std::cin >> n;
134  std::vector<int> a(n);
135  std::cout << "Enter Array: ";
136  for(int i = 0; i < n; i++){
137  std::cin >> a[i];
138  }
139  std::cout << "Median: "; // Median defination: https://en.wikipedia.org/wiki/Median
140  int x = search::median_search::median_of_medians(a, (n - 1) / 2);
141  if(n % 2 == 0){
143  std::cout << (float(x) + float(y))/2.0;
144  }
145  else{
146  std::cout << x;
147  }
148  std::cout << "\nTo find i-th smallest element ";
149  std::cout << "\nEnter i: ";
150  int idx = 0;
151  std::cin >> idx;
152  idx--;
153  std::cout << idx + 1<< "-th smallest element: " << search::median_search::median_of_medians(a, idx) << '\n';
154  return 0;
155 }
Here is the call graph for this function:

◆ median_of_medians()

int search::median_search::median_of_medians ( const std::vector< int > &  A,
const int &  idx 
)

This function search the element in an array for the given index.

Parameters
Aarray where numbers are saved
idxcurrent index in array
Returns
corresponding element which we want to search.
62  {
63  int pivot = 0; // initialized with zero
64  std::vector<int> a(A.begin(), A.end());
66  int r = a.size();
67  for(int i = 0; i < r; i += 5){
68  std::sort(a.begin() + i, a.begin() + std::min(r, i + 5));
69  int mid = (i + std::min(r, i + 5)) / 2;
70  m.push_back(a[mid]);
71  }
72  int sz = int(m.size());
73  if(sz <= 5){
74  std::sort(m.begin(), m.end());
75  pivot = m[(sz- 1) / 2];
76  }
77  else{
78  pivot = median_of_medians(m, idx);
79  }
80  std::vector<int> low;
81  std::vector<int> high;
82  for(int i = 0; i < r; i++){
83  if(a[i] < pivot){
84  low.push_back(a[i]);
85  }
86  else if(a[i] > pivot){
87  high.push_back(a[i]);
88  }
89  }
90  int k = int(low.size());
91  if(idx < k){
92  return median_of_medians(low, idx);
93  }
94  else if(idx > k){
95  return median_of_medians(high, idx-k-1);
96  }
97  else{
98  return pivot;
99  }
100 }
Here is the call graph for this function:

◆ test()

void test ( )

Function to test above algorithm

107  {
108  std::vector<int> A{25,21,98,100,76,22,43,60,89,87};
109  int i = 3;
110  assert(A[6] == search::median_search::median_of_medians(A, i)); // A[6] = 43, is the fourth smallest element.
111  std::cout << "test case:1 passed\n";
112 
113  std::vector<int> B{1,2,3,4,5,6};
114  int j = 4;
115  assert(B[4] == search::median_search::median_of_medians(B, j)); // B[4] = 5, is the fifth smallest element.
116  std::cout << "test case:2 passed\n";
117 
118  std::vector<int> C{1,2,3,4,5,1000,8,9,99};
119  int k = 3;
120  assert(C[3] == search::median_search::median_of_medians(C, k)); // C[3] = 4, is the fourth smallest element.
121  std::cout << "test case:3 passed\n";
122  std::cout << "--All tests passed--\n";
123 }
std::vector< int >
std::vector::size
T size(T... args)
std::sort
T sort(T... args)
std::vector::push_back
T push_back(T... args)
std::cout
search::median_search::median_of_medians
int median_of_medians(const std::vector< int > &A, const int &idx)
Definition: median_search.cpp:62
std::min
T min(T... args)
std::vector::begin
T begin(T... args)
test
void test()
Definition: median_search.cpp:107
std::vector::end
T end(T... args)
std::cin