2

このプログラムは主に私の教授によって処理されました。彼が私に残したのは、ファイルからスキャンされている配列に対して選択ソートを実行する配列を作成することでした。

ほぼ完璧に動作する教科書の助けを借りてコードを書きました。ただし、数値 0 が入力ファイルにない場合、出力の最初の 5 つの数値 (昇順でソートされるはず) がすべて 0 になるという点で、出力は間違っています。配列内の最後の 5 つの数値 (最大の 5 つ) も存在しません。

出力には、入力ファイルからの番号も元のソートされていない順序でリストされ、エラーは表示されません。数字はすべてあります。

メソッドの私のコード:

private static void selectionSort( int arr[], int cnt)
    {

    int index;
    int minIndex;
    int minValue;

        for (cnt=0; cnt < (arr.length-1); cnt++)
        {
            minIndex = cnt;
            minValue = arr[cnt];
            for (index = cnt + 1; index< arr.length; index++)
            {
                if (arr[index] < minValue)
                {
                    minValue = arr[index];
                    minIndex = index;
                }
            }
            arr[minIndex] = arr[cnt];
            arr[cnt] = minValue;
        }
    }

これは出力です：

元のランド 2: 75 62 110 144 108 146 121 119 61 164 170 34 78 41 89 84 74 132 156 160 94 55 76 97 48

ソート済みランド 2: 0 0 0 0 0 34 41 48 55 61 62 74 75 76 78 84 89 94 97 108 110 119 121 132 144

これが起こる原因となる間違いはありますか？

4

1 に答える 1

1

これは、選択ソートとも呼ばれる「遅延置換ソート」の典型的な実装ではないようです。

重要なのは、内側のループが新しい最下位要素のスキャンを終了した後、新しい最下位要素が見つかったかどうかを確認し、見つかった場合はスワップを実行する必要があることです。あなたのアルゴリズムには、この重要なステップが欠けています。外側のループ インデックスにある項目が既に正常であり、交換する必要がない場合があります。

また、上記のように、並べ替えアルゴリズムが外部インデックスとそれに対応する値の両方を格納する理由は不明です。インデックスが必要なだけで、コレクション内の要素はどこにも行きません (これが同時に使用されていない限り、つまり、.... しかし、「ワックスの塊」全体)。

遅延置換ソート アルゴリズムの擬似コードを次に示します。

Begin DELAYEDSORT
 For ITEM=1 to maximum number of items in list-1
    LOWEST=ITEM
    For N=ITEM+1 to maximum number of items in list
       Is entry at position N lower than entry at position LOWEST?
          If so, LOWEST=N
    Next N
    Is ITEM different from LOWEST
       If so, swap entry at LOWEST with entry in ITEM
 Next ITEM
End DELAYEDSORT

選択ソートに関するいくつかの一方的なメモ:

  • O（n ^ 2）の時間複雑度で実行されます
  • バブルソートも O(n^2) の時間計算量で実行されますが、順序付けされていないコレクションでは、選択ソートは 50% も速くなる可能性があります
  • 要素数が非常に多いコレクションでは、選択ソートは非常にコストがかかります
  • スワップを実行するコストが高い場合、多数の要素がある場合でも、特定のコレクションでは選択ソートの方が高速になることがあります(選択ソートは、コレクションの順序付けに必要なスワップの数を最小限に抑えます)。
  • 選択ソートは、私がコーディングした最初のソート アルゴリズムです。バブルソートよりもはるかに理解しやすかったです (このアルゴリズムは、私がコレクションを並べ替える方法とよく一致していました)。
  • 選択ソートよりも時間の複雑さが悪いと私が認識している唯一のソートアルゴリズムは、O（n ^ 2.7）のオーダーの時間の複雑さを持つ、いわゆる「ストゥージソート」です。
于 2013-10-03T00:09:35.637 に答える