wpf - 操作回数が最も少ないソートアルゴリズム

Question

操作数が最も少ないソートアルゴリズムは何ですか? WPF のピクセル シェーダー効果 v2.0 の一部として HLSL に実装する必要があるため、ピクセル シェーダーの制限を考慮すると、操作の数は非常に少なくて済みます。9 つの値、具体的には現在のピクセルとその近傍を並べ替える必要があります。

Answer 1

挿入ソートまたは基数ソートを使用したい。C++ の実装を次に示します。

基数ソート

void radix (int byte, long N, long *source, long *dest)
{
  long count[256];
  long index[256];
  memset (count, 0, sizeof (count));
  for ( int i=0; i<N; i++ )
    count[((source[i])>>(byte*8))&0xff]++;

  index[0]=0;
  for ( i=1; i<256; i++ )
    index[i]=index[i-1]+count[i-1];
  for ( i=0; i<N; i++ )
    dest[index[((source[i])>>(byte*8))&0xff]++] = source[i];
}

1 つのradix()列でしか機能しないため、4 回呼び出す必要があります。

挿入ソート

void insertSort(int a[], int length)
{    
    int i, j, value;
    for(i = 1; i < length; i++)
    {
        value = a[i];
        for (j = i - 1; j >= 0 && a[j] > value; j--)
            a[j + 1] = a[j];
        a[j + 1] = value;
    }
}

Answer 2

Knuth は、最適な並べ替えアルゴリズムを見つけるためにいくつかの作業を行いました。ただし、要素が 5 つしかない場合でも、比較回数が最小のアルゴリズムの実装は非常に複雑です。

最適なアルゴリズムを見つけようとする代わりに、実装が簡単でニーズに十分に適したアルゴリズムを見つけようとすることをお勧めします。標準の並べ替えアルゴリズムにアクセスできる場合は、最初にそれを使用してみてください。そうでない場合は、挿入ソートまたはマージソートを使用してシンプルに保ち、それで十分かどうかを確認できます。

挿入ソート:

• 簡単な実装
• (かなり) 小さいデータセットに対して効率的
• 適応型、つまり、すでに実質的にソートされているデータセットに対して効率的: 時間計算量は O(n + d) で、d は反転の数です
• 実際には、選択ソートやバブルソートなどの他のほとんどの単純な二次アルゴリズム、つまり O(n2) アルゴリズムよりも効率的です。最良のケース (ほぼソートされた入力) は O(n) です
• 安定、つまり、等しいキーを持つ要素の相対的な順序を変更しません
• インプレース、つまり、一定量の O(1) の追加メモリ空間のみが必要です
• オンライン、つまりリストを受け取ったときに並べ替えることができます。