TheAlgorithms/C++
1.0.0
All the algorithms implemented in C++
Loading...
Searching...
No Matches
median_search.cpp
Go to the documentation of this file.
1
40
41
#include <iostream>
42
#include <algorithm>
43
#include <vector>
44
#include <cassert>
45
50
namespace
search
{
55
namespace
median_search
{
62
int
median_of_medians
(
const
std::vector<int>& A,
const
int
& idx) {
63
int
pivot = 0;
// initialized with zero
64
std::vector<int> a(A.begin(), A.end());
65
std::vector<int> m;
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
}
101
}
// namespace median_search
102
}
// namespace search
103
107
void
test
(){
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
}
124
128
int
main
()
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){
142
int
y =
search::median_search::median_of_medians
(a, n / 2);
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
}
156
search::median_search::median_of_medians
int median_of_medians(const std::vector< int > &A, const int &idx)
Definition
median_search.cpp:62
test
void test()
Definition
median_search.cpp:107
main
int main()
Definition
median_search.cpp:128
median_search
Functions for Median search algorithm.
search
for std::assert
Definition
binary_search.cpp:47
search
median_search.cpp
Generated by
1.13.2