スポンサーリンク

二つの配列からなる値をクイックソート

前回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;
}
ソート前の配列:
5 e
1 a
3 c
4 d
2 b
ソート後の配列:
1 a
2 b
3 c
4 d
5 e

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

日本語が含まれない投稿は無視されますのでご注意ください。(スパム対策)


この記事のトラックバックURL: