スポンサーリンク
前回C++で実装したクイックソートで、二つの配列を同時にクイックソートする。
#include <iostream> #include <vector>
// 配列の分割を行う関数(ピボットの位置を変更しない) template<typename Container, class QElem> size_t partition(Container& arr, size_t low, size_t high) { size_t mid = low + (high - low) / 2; // 中央の要素をピボットとして選択 QElem pivot(arr, mid); // ピボットの値を取得 size_t i = low; size_t j = high; while (true) { // ピボットより小さい要素を左側に移動 while (QElem::Lesser(arr,i,pivot) ){ i++; } // ピボットより大きい要素を右側に移動 while (QElem::Greater(arr,j,pivot) ) { j--; } // 左右の走査が交差した場合に分割終了 if (i >= j) { return j; } // 交差していない場合、要素を交換 QElem::Swap(arr, i, j); i++; j--; } }
// クイックソートを行う関数 template<typename Container, class QElem> void quick_sort(Container& arr, size_t low, size_t high) { if (low < high) { size_t pi = partition<Container,QElem>(arr, low, high); if (pi > low) quick_sort<Container, QElem>(arr, low, pi);// ピボットの左側をソート quick_sort<Container, QElem>(arr, pi + 1, high);// ピボットの右側をソート } }
// 二つの配列を一つにまとめて渡すための構造体
struct Vector2Reference { std::vector<float>& value; std::vector<std::string>& label; Vector2Reference(std::vector<float>& v, std::vector<std::string>& l) : value(v), label(l) {} size_t size() const { return value.size(); } };
struct QsortElement { float value; // Pivotの値を保存するためのオブジェクト用のコンストラクタ QsortElement(const Vector2Reference& arr, size_t index) { value = arr.value[index]; } // 要素の交換関数 static void Swap(Vector2Reference& arr, size_t i, size_t j) { std::swap(arr.value[i], arr.value[j]); std::swap(arr.label[i], arr.label[j]); } // 比較関数 static bool Lesser(Vector2Reference& arr, size_t i, const QsortElement& qe) { return arr.value[i] < qe.value; } // 比較関数 static bool Greater(Vector2Reference& arr, size_t i, const QsortElement& qe) { return arr.value[i] > qe.value; } };
int main() { std::vector<float> value; std::vector<std::string> label; value.push_back(5.0f); label.push_back("e"); value.push_back(1.0f); label.push_back("a"); value.push_back(3.0f); label.push_back("c"); value.push_back(4.0f); label.push_back("d"); value.push_back(2.0f); label.push_back("b"); Vector2Reference arr2(value, label); std::cout << "ソート前の配列: " << std::endl; for (size_t i = 0; i < arr2.size(); i++) { std::cout << arr2.value[i] << " " << arr2.label[i] << std::endl; } quick_sort< Vector2Reference, QsortElement>(arr2, (size_t)0, arr2.size()-1); std::cout << "ソート後の配列: " << std::endl; for (size_t i = 0; i < arr2.size(); i++) { std::cout << arr2.value[i] << " " << arr2.label[i] << std::endl; } return 0; }