1

問題の説明

ちょうど今、私はC ++プログラミング言語を学んでいて、コードを書くことによってそれをすることにしました。min配列の最初の形式の値から値に項目を並べ替えるアルゴリズムを作成してmax、次のような整数の配列を取得しようとしています。

    int arrayToSort[] = {3,5,3,1,8,7,2,4};

そして、この配列をソートするアルゴリズムを書いてみてください。以下にソースコードを示します

アルゴリズムI

int arrayToSort[] = {3,5,3,1,8,7,2,4};
int arrayToSortSize = sizeof(arrayToSort)/sizeof(int);

for(int i=1; i<arrayToSortSize; ++i) {
    int* first = arrayToSort;
    int* end = arrayToSort + arrayToSortSize;

    for(first; first!=end-i; ++first) {
        if (*first > *(first+1)) {
            int temp = *first;
            *first = *(first+1);
            *(first+1) = temp;
        }   
    }
}

このアルゴリズムは正しく機能し、配列内のすべての要素を正しく並べ替えますが、このアルゴリズムがそのような並べ替えを行うのに正しい1, 2, 3, 3, 4, 5, 7, 8かどうかを知りたいのですが、この場合、これがすべての要素を並べ替える最短の方法ですか？

アルゴリズムII

ここでは同じアルゴリズムを実装していますが、今回はポインターの代わりに配列を使用しています。以下のソースコードをご覧ください。

int arrayToSortSize = sizeof(arrayToSort)/sizeof(int);

for(int i=1; i<arrayToSortSize; ++i) {
    int* first = arrayToSort;
    int* end = arrayToSort + arrayToSortSize;

    for(int j=0; j<arrayToSortSize-i; j++) {
        if (arrayToSort[j] > arrayToSort[j+1]) {
            int temp = arrayToSort[j];
            arrayToSort[j] = arrayToSort[j+1];
            arrayToSort[j+1] = temp;
        }   
    }
}

このアルゴリズムもうまく機能します。すべてのアイテムを正しくソートしますが、どのアルゴリズムを使用するのが良いか知りたいのですが、どちらが速いのでしょうか（そのうちの1つがそうである場合）？

質問

  • どのアルゴリズムを使用するのが良いですか？
  • どのアルゴリズムが速いですか？それとも同じ速度で動作しますか？
  • アルゴリズムIまたはアルゴリズムIIはより良い方法で実装できますか？
  • このアルゴリズムはどのように呼ばれますか？

サンプル画像の並べ替え

4

3 に答える 3

3

2つの「アルゴリズム」は、バブルソートと呼ばれる同じアルゴリズムの2つの実装です。

これは、並べ替えを行うための最も単純なアルゴリズムですが、パフォーマンスが低くなります（2次の複雑さ）。

ソートアルゴリズムをさらに深く掘り下げたい場合は、そのための優れた本があります。私は特にこれが好きです。

より高速に実行されるアルゴリズムを確認したいだけの場合は、quicksortまたはを参照してくださいmergesort。どちらにも長所と短所がありますが、通常はアプリケーションとデータのサイズに応じてどちらかを選択できます。

より一般的にstd::sortは、関連性があり可能な場合は、データのサイズに応じて、必要な特定のアルゴリズムを調整するのに最適な方法を選択します。パフォーマンスの問題がある（または学習目的である）ことがわかった場合にのみ、独自の実装を検討できますsort。しかし、パフォーマンスの悪いソート実装を作成するのは簡単なので（優れたアルゴリズムであっても）、自分が何をしているのかを本当に理解する必要があります。

編集（精度）：実際には、配列が十分に小さい場合（たとえば、20項目未満）は、を使用しinsertion sortます。それ以外の場合はquicksort、データについてこれ以上の仮説がない場合に使用してください。このカットオフの理由は、再帰呼び出しのコストが、クイックを使用するよりも少量のデータのオーバーヘッドを大きくする可能性があるためinsertion sortです。

于 2013-03-05T20:46:13.583 に答える
0

ない。

ほとんどの場合、配列とポインタの使用の違いはごくわずかです。

アルゴリズムIとIIはどちらも、いわゆるバブルソートです。場合によっては効果的な並べ替えですが、最速の並べ替えになることはめったにありません。

于 2013-03-05T20:46:20.793 に答える
0

どちらのアルゴリズムも大きい値を見つけ、次に2番目などを見つけます。したがって、N個の要素がある場合、ループの最初の実行でN-1要素が比較され、ループの2番目の行でN-2などが比較されます。

それはバブルソートと呼ばれていました。（N-1）N/2比較演算の近似を取ります。二分探索であるクイックソート（たとえば）を使用する場合、多数のNにとって重要なO（N log N）操作が必要になります 。wikiからのクイックソート

于 2013-03-05T20:47:06.107 に答える