partitionを使い、quick selectアルゴリズムを書く。quick selectでは「配列がソートされたときに、n番目に来る値」を取得できる。これを利用して中央値を取得できる。n番目の要素を特定するのに必要な処理が完了したらクイックソートを中断することで実現するので、データの順番が入れ替わるが、全部ソートするほどの時間はかからない。
C++でpartitionするプログラムを変更して[pivot未満][pivot][pivotより大きい]の領域に分割する
#include <iostream> #include <vector> #include <algorithm> #include "partition_3area.hpp"
void quick_select(std::vector<PairTypeFloat>& arr,size_t low,size_t high, size_t target_index) { size_t nlow = low; size_t nhigh = high; size_t tmp_pivot_index = low + (nhigh - nlow) / 2; //なにかしらpivotを決める // pivotでパーティション PartitionFuncFloat cond(arr, tmp_pivot_index); std::array<int64_t, 3> ret= partition_3area(arr, nlow, nhigh, cond); nlow = ret[0]; // 左側開始位置 size_t newpivot = ret[1]; // 処理後のpivotの位置 nhigh = ret[2]; // 右側終了位置 // [nlow～newpivot-1][newpivot][newpivot+1～nhigh] に分割される // このとき、 if (newpivot == target_index) { // [nlow～newpivot-1][target_index][newpivot+1～nhigh] であれば、 // target_indexの要素番号のデータはtarget_index番目の要素になっている return ; } else if (target_index < newpivot) { // [target_indexを含む][newpivot][newpivot+1～nhigh] であれば、 // 左側を処理 quick_select(arr, nlow, newpivot, target_index); } else { // [nlow～newpivot-1][newpivot][target_indexを含む] であれば、 // 右側を処理 quick_select(arr, newpivot+1, nhigh, target_index); } }
int main() { std::vector<PairTypeFloat> arr; arr.push_back(std::make_pair(3.7, "a")); arr.push_back(std::make_pair(2.3, "b")); arr.push_back(std::make_pair(7.5, "c")); arr.push_back(std::make_pair(1.2, "d")); arr.push_back(std::make_pair(6.8, "e")); arr.push_back(std::make_pair(5.6, "f")); arr.push_back(std::make_pair(2.4, "g")); arr.push_back(std::make_pair(0.9, "h")); arr.push_back(std::make_pair(6.1, "i")); arr.push_back(std::make_pair(5.8, "j"));// arr.push_back(std::make_pair(4.5, "k")); arr.push_back(std::make_pair(8.2, "l")); arr.push_back(std::make_pair(9.1, "m")); arr.push_back(std::make_pair(1.7, "n")); arr.push_back(std::make_pair(5.3, "o")); arr.push_back(std::make_pair(7.7, "p")); arr.push_back(std::make_pair(3.8, "q")); arr.push_back(std::make_pair(4.2, "r")); std::cout << "処理前の配列: " << std::endl; for (size_t i = 0; i < arr.size(); i++) { std::cout << "[" << i << "] " << arr[i].first << " " << arr[i].second << std::endl; } size_t target_index = arr.size() / 2; std::cout << target_index << "番目の要素: " << arr[target_index].first << " " << arr[target_index].second << std::endl; quick_select(arr, 0, arr.size(), target_index);// 中央値を求める std::cout << "--------------------------------------------" << std::endl; std::cout << "処理後の配列: " << std::endl; for (size_t i = 0; i < arr.size(); i++) { std::cout << "[" << i << "] " << arr[i].first << " " << arr[i].second << std::endl; } std::cout << target_index << "番目の要素: " << arr[target_index].first << " " << arr[target_index].second << std::endl; std::cout << "--------------------------------------------" << std::endl; std::cout << "ソート結果: " << std::endl; arr.clear(); arr.push_back(std::make_pair(3.7, "a")); arr.push_back(std::make_pair(2.3, "b")); arr.push_back(std::make_pair(7.5, "c")); arr.push_back(std::make_pair(1.2, "d")); arr.push_back(std::make_pair(6.8, "e")); arr.push_back(std::make_pair(5.6, "f")); arr.push_back(std::make_pair(2.4, "g")); arr.push_back(std::make_pair(0.9, "h")); arr.push_back(std::make_pair(6.1, "i")); arr.push_back(std::make_pair(5.8, "j")); // arr.push_back(std::make_pair(4.5, "k")); arr.push_back(std::make_pair(8.2, "l")); arr.push_back(std::make_pair(9.1, "m")); arr.push_back(std::make_pair(1.7, "n")); arr.push_back(std::make_pair(5.3, "o")); arr.push_back(std::make_pair(7.7, "p")); arr.push_back(std::make_pair(3.8, "q")); arr.push_back(std::make_pair(4.2, "r")); std::sort(arr.begin(), arr.end(), [](const PairTypeFloat& a, const PairTypeFloat& b) {return a.first < b.first; }); for (size_t i = 0; i < arr.size(); i++) { std::cout << "[" << i << "] " << arr[i].first << " " << arr[i].second << std::endl; } }