4

オブジェクト指向アプローチを使用して3つの異なる並べ替えアルゴリズムを実装する必要があり、これに対抗するための最良の方法を考えてきました。

基本的に、私はそれがこのように見えるべきだと思います：

->並べ替え（クラス、インターフェイス、ポリモーフィック）

継承：

->バブルソート

->挿入ソート

->クイックソート

それぞれの並べ替えのインターフェースが同じであれば、さまざまな並べ替え方法にアクセスしやすくなります。つまり、他の並べ替えアルゴリズムを追加するときに、それらを現在の設計とクラス構造に簡単に実装できます。

私の質問は次のとおりです。

  • これは使用するのに良いアプローチですか？

  • テンプレートを使用する余地はありますか？つまり、バブルを使用したい場合はバブルソートと呼ばれ、挿入を使用したい場合は挿入と呼ばれますか？

4

3 に答える 3

5

Sortインターフェースまたは抽象クラスである必要がありますが、バブル/挿入/クイックソートは実装/具象クラスである必要があります。

次のことについても学ぶ価値があります。

戦略パターン：

戦略パターン図 http://en.wikipedia.org/wiki/Strategy_pattern

と

状態パターン：

状態パターン図

http://en.wikipedia.org/wiki/State_pattern

テンプレートに関しては、あなたの場合はそれだけの価値はないと思います。

于 2012-10-30T14:30:14.613 に答える
3

提案されているように、インターフェース（純粋な仮想クラス）を使用します

インターフェース方法： 

class sort_algorithm_interface {
public:
    virtual void sort(std::vector<int>& input) const  = 0;
};

class BubbleSort : public sort_algorithm_interface {
public:
    virtual void sort(std::vector<int>& input) const {/* sort the input */}
};

class InsertionSort: public sort_algorithm_interface {
public:
    virtual void sort(std::vector<int>& input) const {/* sort the input */}
};

class QuickSort: public sort_algorithm_interface {
public:
    virtual void sort(std::vector<int>& input) const {/* sort the input */}
};

簡単に並べ替える場合は、次のようにします。

sort_algorithm_interface& s = QuickSort(input);
s.sort(input);

テンプレートメソッド：

class BubbleSort  {
public:
    void sort(std::vector<int>& input) const {/* sort the input */}
};

class InsertionSort {
public:
    void sort(std::vector<int>& input) const {/* sort the input */}
};

class QuickSort {
public:
    void sort(std::vector<int>& input) const {/* sort the input */}
};

template<typename Sort>
class MySort {
    void sort(std::vector<int>& input) {
        Sort s;
        s.sort(begin, end);
    }
}

これは次のように使用されます。

MySort<QuickSort> s;
s.sort(input);
于 2012-10-30T14:34:29.240 に答える
2

C ++でこれを行う正しい方法は、テンプレートを使用することです。

何かをソートすることはアルゴリズムであり、一般的に永続的な状態はほとんどまたはまったくありません。ソートはオブジェクトではなく、データ（オブジェクトの場合もあります）に対する関数です。

ライブラリには、次のstdシグネチャを持つソートがすでにあります。

template<typename I, typename C = std::less<typename std::iterator_traits<I>::value_type> >
void sort(I begin, I end, C comp = C());

イテレータbeginとendは、ソートされる値の範囲を示します。compは、値の範囲の2つの要素が渡されると、最初の要素が2番目の要素よりも小さいかどうかを示すファンクター（または関数）です。

これをで使用するには、次のstd::vectorようにします。

std::vector<int> myVector; // assume it has some data in it
sort( myVector.begin(), myVector.end() );

std :: sortは（通常は？）クイックソートです。しかし、インターフェースは、迅速なバブルおよび挿入ソートで機能します。

このアプローチの大きな利点は、ある種類が別の種類を使用できることです。例として、クイックソートは大きなデータセットでは高速ですが、多くの場合、小さなデータセットでは挿入ソートの単純さが優先されます（n ^ 2のオーバーヘッドがある場合でも定数係数が低くなります）。したがって、このようにソートを記述することにより、要素の数が少ない場合に、クイックソートの再帰呼び出しを代わりに挿入ソートにすることができます。

ここで、使用しているアルゴリズムの実行時置換が必要な場合は、使用しているイテレーター、さらにはどの比較子を特定する必要があります。これは、共通の関数シグネチャ（私が行うこと）、または純粋な仮想インターフェイスを備えた基本クラス（これはお勧めしません）のいずれかを使用して実行できます。ただし、実行時に選択されたコンパレータのオーバーヘッドは重要であることに注意してください。固定イテレータの選択、または関数へのポインタまたは仮想メソッド呼び出しからのオーバーヘッドは、アルゴリズムの再帰呼び出しで実行されない限り、妥当なサイズのコンテナではかなり安価になります。

于 2012-10-30T15:39:10.227 に答える