0

これが挿入ソートの2つのバージョンで、1つは擬似コードから、もう1つは直接実装します。どのバージョンがより多くのステップとスペースを必要とするか知りたいです（少しのスペースでも複雑です）。

void insertion_sort(int a[], int n) {
    int key, i, j;
    for(i = 1; i < n; i++) {
        key = a[i];
        j = i - 1;
        while(j >= 0 && a[j] > key) {
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = key;
    }       
}

そしてこれ

insertion_sort(item s[], int n) {
  int i,j;
  for (i=1; i<n; i++) {
    j=i;
    while ((j>0) && (s[j] < s[j-1])) {
      swap(&s[j],&s[j-1]);
      j = j-1;
    }
  }
}

これがサンプルのソート配列a={5、2、4、6、1、3}です。私の意見では、2番目のバージョンは番号を1つずつ交換するため、より多くの手順を実行しますが、1番目のバージョンはwhileループでより多くの番号を交換してから、最小の番号を交換します。例：インデックス= 3までは、両方のバージョンが同じステップを実行しますが、インデックス= 4になると、つまり、番号1をスワップする場合、2番目は1番目よりも多くのステップを実行します。どう思いますか？

4

4 に答える 4

2

「歩数」は何の有用な尺度でもありません。

ステップはラインですか？声明？表現？アセンブラ命令？CPUマイクロオペレーション？

つまり、「ステップ」はアセンブラーに変換されてから最適化され、結果の命令には異なる（場合によっては可変の）実行時コストがかかる可能性があります。

あなたが尋ねるかもしれない賢明な質問：

1アルゴリズムの複雑さは何ですか？

Rafe KettlerのコメントとArpitの回答に示されているように、これは入力サイズが大きくなるにつれてアルゴリズムがどのようにスケーリングするかについてです。

2どのように機能しますか

どちらが速いか（一部の入力セットについて）を知りたい場合は、それを測定する必要があります。

どちらがより多くのスワップを実行するかを知りたいだけの場合swapは、呼び出されるたびにグローバルカウンターをインクリメントする関数を作成して、調べてみませんか？

于 2013-03-26T18:46:10.813 に答える
1

スワップの数は間違った用語です。割り当ての数を数える必要があります。swap（）は3つの割り当てに拡張されるため、通常、スペースを節約せずに2番目のバージョンでより多くの割り当てが発生します（2番目のバージョンではキーがない場合がありますが、swap（）は内部的に同様のものを持っています）。

于 2013-03-26T18:48:52.387 に答える
0

どちらのバージョンも2つのループを使用しています。とても複雑なO(n*n)時間。他のすべてのステートメントのconstant（1）時間を考慮します。

于 2013-03-26T18:26:21.900 に答える
0

行ごとに分析してみましょう。スワップの複雑さは3だと思います

a）計算の複雑さ:( 3+(n-1)*(1+1+((n-1)/2)*(1+1+1)*(1+1)+1)=1+(n-1)*(3n)=3n^2-3n+1 継続的な最悪のシナリオの平均であるように見えるため、n / 2を使用します）。

メモリ：3 int、+ 1（forループ）

b）計算の複雑さ：2+（n-1）（1 +（（n-1））/ 2（1 + 1 + 1）（3 + 1））= 2 +（n-1）*（6n-5 ）= 6n ^ 2-11n + 7

メモリ：2 int、+スワップのコスト（おそらく追加の1整数）

どちらの場合も同じであるため、入力メモリはカウントしません。それが役に立てば幸い。

于 2013-03-26T18:46:27.283 に答える