1

選択ソートアルゴリズムのこの実装があります。この実装を安定させるにはどうすればよいですか? 無理だと思います/

int selection_sort1 ( int ai_numbers[], const int ci_count )
{
    int counter = 0;
    int i, minIndex, j;

    for ( i = 0; i < ci_count; i++ )
    {
        minIndex = i;
        for ( j = i + 1; j < ci_count; j++ )
        {
            if ( ai_numbers[j] < ai_numbers[minIndex] )
            {
                minIndex = j;
            }
        }
        swap ( &ai_numbers[i], &ai_numbers[minIndex] );
        counter++;
    }


    return counter;
}
4

2 に答える 2

0

ウィキペディアから直接引用：

選択ソートは、安定ソートとして実装できます。手順2でスワップするのではなく、最小値が最初の位置に挿入された場合（つまり、間にあるすべてのアイテムが下に移動した場合）、アルゴリズムは安定しています。ただし、この変更には、リンクリストなどの効率的な挿入または削除をサポートするデータ構造が必要であるか、またはΘ（n2）書き込みの実行につながります。

つまり、基本的には安定したソートがあります。これは、常に最小値よりも小さい値を交換しているためです（値よりも小さい値または等しい値ではありません）。

于 2012-10-28T20:02:04.157 に答える
0

実装は安定していません。各反復で、配列内の位置iにある要素を取得し、残りの配列内の任意の位置に配置するため、元の順序が台無しになります。

安定したソートが必要な場合は、次のことを行う必要があります。

  • すでに行っているように、残りのリストから最小要素を選択します
  • i交換せずに所定の位置に挿入します。これは、残りの要素を右に移動して、i配置する3番目の要素用のスペースを作ることを意味します。

これにより、同じ値の要素が、並べ替えられた配列と元の配列で同じ順序で配置されるようになります。

（間違いを指摘してくれたGrooのコメントに感謝します）

于 2012-10-28T19:58:27.533 に答える