スポンサーリンク
C++でクイックソートを実装する。ただし、諸事情によりピボット保存、比較演算、スワップ関数を外部で実装し、テンプレートで渡す形式にする(QElem)。
#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 QsortElement { float value; // Pivotの値を保存するためのオブジェクト用のコンストラクタ QsortElement(const std::vector<float>& arr, size_t index) { value = arr[index]; } // 要素の交換関数 static void Swap(std::vector<float>& arr, size_t i, size_t j) { std::swap(arr[i], arr[j]); } // 比較関数 static bool Lesser(std::vector<float>& arr, size_t i, const QsortElement& qe) { return arr[i] < qe.value; } // 比較関数 static bool Greater(std::vector<float>& arr, size_t i, const QsortElement& qe) { return arr[i] > qe.value; } };
int main() { std::vector<float> arr = {5.2f, 1.8f, 3.2f, 4.3f, 2.7f}; std::cout << "ソート前の配列: " << std::endl; for (size_t i = 0; i < arr.size(); i++) { std::cout << arr[i] << " " << std::endl; } quick_sort< std::vector<float>, QsortElement>(arr, (size_t)0, arr.size()-1); std::cout << "ソート後の配列: " << std::endl; for (size_t i = 0; i < arr.size(); i++) { std::cout << arr[i] << " " << std::endl; } return 0; }