0

次の整数の 2 次元配列があるとします。

1 3 3 1
1 0 2 2
2 0 3 1
1 1 1 0
2 1 1 3

ユーザーが配列自体と文字列を入力として与えることができる実装を作成しようとしていました。上記の例の文字列の例は03、ユーザーが 1 番目と 4 番目の列に基づいて配列を並べ替えたいことを意味します。

したがって、この場合、ソートの結果は次のようになります。

1 1 1 0
1 3 3 1
1 0 2 2
2 0 3 1
2 1 1 3

STL の関数内で使用されている比較関数についてはあまり知りませんでしたが、sort検索した結果、次の簡単な実装を作成しました。

というクラスを作りましたComparator.h

   class Comparator{

     private:
      std::string attr;

     public:
      Comparator(std::string attr) { this->attr = attr; }

      bool operator()(const int* first, const int* second){
       std::vector<int> left;
       std::vector<int> right;
       size_t i;
       for(i=0;i<attr.size();i++){
                left.push_back(first[attr.at(i) - '0']);
                right.push_back(second[attr.at(i) - '0']);
        }
        for(i=0;i<left.size();i++){
                if(left[i] < right[i]) return true;
                else if(left[i] > right[i]) return false;
        }
        return false;
      }

     };

文字列内の情報を知る必要があるため、この文字列がプライベート変数であるクラスが必要です。Iの内部operatorには と の 2 つのパラメーターがfirstありsecond、それぞれが行を参照します。この情報を持って、ベクトルを作成します。leftベクトルrightにleftはfirst、ソートに重要で文字列変数によって指定された行の番号のみがあり、rightベクトルにsecondは重要な行の番号のみがあります文字列変数で指定します。

次に、必要な比較を行い、true または false を返します。Sorting.cppユーザーは、クラス内でこの関数を呼び出すことにより、このクラスを使用できます。

void Sorting::applySort(int **data, std::string attr, int amountOfRows){

  std::sort(data, data+amountOfRows, Comparator(attr));

 }

使用例を次に示します。

int main(void){
    //create a data[][] variable and fill it with integers
    Sorting sort;

sort.applySort(data, "03", number_of_rows);
}

2 つの質問があります。

最初の質問

実装を改善できますか? leftベクトルやベクトルなどの追加の変数を使用しright、さらに for ループをいくつか使用して、並べ替え操作に余分なコストがかかります。

2 番目の質問

余分なコストのために、ソートの時間の複雑さはどの程度悪化しますか? STLsortはO(n*logn)、n並べ替えたい整数の数です。ここnには異なる意味nがあります。行の数であり、各行はm整数まで持つことができます。これはComparator、関数をオーバーライドし、operator追加の変数 (ベクトル) と for ループを使用することによって、クラス内で見つけることができます。

STL がどの程度正確に実装されているのかわからないsortため、いくつかの見積もりしかできません。私の最初の見積もりは、ソートに重要な列の数がO(n*m*log(n))どこにmあるかということですが、100％確実ではありません。

前もって感謝します

4

3 に答える 3

2

あなたは確かにあなたのコンパレータを改善することができます。列をコピーしてから比較する必要はありません。2つの呼び出しの代わりにpush_back、値を比較して、trueを返すか、falseを返すか、または値が小さいか大きいか等しいかに応じてループを続行します。

の複雑さの関連部分sortはO(n * log n)比較です（C++11。C++03ではそれほど良い保証はありません）。ここnで、はソートされる要素の数です。したがって、コンパレータがであるO(m)場合、推定値はn行を並べ替えることができます。以来attr.size() <= m、あなたは正しいです。

于 2013-03-16T14:12:21.833 に答える
1

最初の質問：左と右は必要ありません。要素を1つずつ追加してから、同じ順序でベクトルを反復処理します。したがって、値をベクトルにプッシュしてから反復する代わりに、次のように最初のサイクルで値を生成するときに値を使用するだけです。

    for(i=0;i<attr.size();i++){
            int left = first[attr.at(i) - '0'];
            int right = second[attr.at(i) - '0'];
            if(left < right) return true;
            else if(left > right) return false;
    }

2番目の質問：時間計算量を改善できますか？直接比較を使用するソートアルゴリズムではありません。一方、ここで解決する問題は、基数ソートにいくぶん似ています。したがって、O（n * m）でソートできるはずです。ここで、mはソート基準の数です。

于 2013-03-16T14:09:22.003 に答える
1

1）最初に、コンストラクターで文字列を整数配列に変換する必要があります。値の検証が列数より少ない場合。

（整数配列をパラメーターとして受け取る別のコンストラクターを使用することもできます。わずかな拡張機能として、負の値を使用して、その列の並べ替えの順序が逆になっていることを示すことができます。この場合、値は-N..-になります。 1、1..N）

2）中間の左右の配列は必要ありません。

于 2013-03-16T14:10:22.153 に答える