2

ソート用にこのコードを作成しましたが、完全に正常に動作します。時間の複雑さを軽減する方法を知りたかったのです。

#include <iostream>

using namespace std;

void sort(int a[], int n)
{
    int min, temp;
    for(int i=0;i<n-1;i++)
    {
        min=i;
        for(int j=i+1;j<n;j++)
        {
            if(a[min]>a[j])
            {
                min=j;
            }
        }
        temp=a[i];
        a[i]=a[min];
        a[min]=temp;
    }
    for(int i=0;i<n;i++)
    {
        cout<<a[i]<<endl;
    }
}
int main()
    {
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    sort(arr,n);
    return 0;
}

他に変更する方法がない場合、アルゴリズムを変更する必要がありますか? もしそうなら、アルゴリズムを提案してください。

ありがとう。

4

3 に答える 3

6

遅いことが知られているある種の選択 sortを使用しているようです。IRL アプリケーションは通常、クイックソートまたはマージソートを使用します(後者はそれほど多くありません)。

同じことをすることをお勧めします（これは教育目的であると仮定します）。

それ以外の場合は、std::sortdefined inを使用し<algorithm>ます。

また、コードが標準ではないことに注意してください。

cin>>n;
int arr[n];

VLA は C++ ではサポートされていません。代わりにa を使用することをお勧めしますstd::vector。C++ を使用する場合は、C コードを記述しないでください。

于 2012-08-13T17:33:01.890 に答える
3

あなたのアルゴリズムは選択ソート、O(n^2)アルゴリズムです。入力サイズが で線形に増加する場合n、実行時間は の二次関数に比例しnます。任意の入力 (つまり、入力に関する予備知識なし) での比較ベースの並べ替えの最小時間計算量は ですO(n log n)。STL 関数std::sortは、この保証を提供します。

#include <algorithm>
#include <vector>

int main()
{
    int n;
    cin>>n;
    std::vector<int> arr;
    arr.resize(n);

    for(int i=0;i<n; ++i) // ++i rather than i++ is a good habit to get into
    {
        cin>>arr[i];
    }

    // O(N log N) complexity
    std::sort(arr.begin(), arr.end());

    return 0;
}

小さい入力の場合、選択ソート (または挿入ソート) が十分に高速な場合があります。これを C++11 の数ライナーとしてコーディングすることもできます (ラムダ式を使用します)。

#include <algorithm>
#include <iterator>

template<class ForwardIterator>
void selection_sort(ForwardIterator first, ForwardIterator last)
{
        std::for_each(first, last, [](ForwardIterator it) {         // your outer loop
                auto const selection = std::min_element(it, last);  // your inner loop
                std::iter_swap(selection, it);                      // your swap code
        });
}

// call on your vector
selection_sort(arr.begin(), arr.end());

このコードから、選択ソートがどのように機能するかも明らかです。配列の残りの部分で繰り返し最小要素を見つけ、それを所定の位置に入れ替えます。これはあなた自身のコードと同等であるはずですが、(STL を理解すれば) はるかに理解しやすいことに同意していただければ幸いです。

于 2012-08-13T17:35:28.183 に答える
0

選択ソートを使用して配列をソートしています。このアルゴリズム id の実行時間O(n^2)。実行時間が のソートには、マージソートまたはヒープソートを使用できますO(nlog(n))。他の優れたパフォーマンス特性を維持しながら、 QuickSort の最悪のケースを O(n log n)に押し下げる非常に巧妙なトリックを使用するIntro Sort
を使用 することもできます。

詳細については、並べ替えアルゴリズムに関する wiki ページを確認してください。

于 2012-08-13T17:35:50.410 に答える