ハードウェアからのデータがあります。データは 32 バイトのブロックで提供され、数百万のブロックが存在する可能性があります。データ ブロックは、次のように 2 つの半分に分散されます (文字は 1 つのブロックです)。
A C E G I K M O B D F H J L N P
または番号が付けられている場合
0 2 4 6 8 10 12 14 1 3 5 7 9 11 13 15
最初に偶数インデックスのすべてのブロック、次に奇数ブロック。データを正しく並べ替える (アルファベット順) 特殊なアルゴリズムはありますか?
制約は主にスペースに関するものです。並べ替えるために別のバッファーを割り当てたくありません。あと 1 ブロックだけです。しかし、私は移動数を低く抑えたいとも考えています。簡単なクイックソートは O(NlogN) です。この特別な並べ替えの場合、O(N) でより高速なソリューションはありますか?
このデータは常に同じ順序であるため、従来の意味での並べ替えはまったく必要ありません。与えられた 2 つのデータ ポイントのどちらかが事前にわかっているため、比較する必要はありません。
代わりに、データの順列を直接生成できます。これを巡回形式に変換すると、並べ替えられたデータを順序付けられたデータに変換するために、どのスワップを行うべきかが正確にわかります。
データの例を次に示します。
0 2 4 6 8 10 12 14 1 3 5 7 9 11 13 15
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
ここで逆数を計算します (ここでは怠け者なので、この手順はスキップします。代わりに、上記で指定した順列が実際には既に逆数であると仮定します)。
巡回形式は次のとおりです。
(0)(1 8 4 2)(3 9 12 6)(5 10)(7 11 13 14)(15)
したがって、このように構造化されたシーケンスを並べ替えたい場合は、次のようにします。
# first cycle
# nothing to do
# second cycle
swap 1 8
swap 8 4
swap 4 2
# third cycle
swap 3 9
swap 9 12
swap 12 6
# so on for the other cycles
元の順列ではなく逆順列に対してこれを行った場合、証明された最小数のスワップで正しいシーケンスが得られます。
編集：
このような詳細については、たとえば、TAOCP の順列に関する章を参照してください。
つまり、次のようなパターンでデータが入力されます
a 0 a 2 a 4 ... a 14 a 1 a 3 a 5 ... a 15
そしてあなたはそれをにソートさせたい
b 0 b 1 b 2 ... b 15
いくつかの並べ替えを使用すると、順列は次のように記述できます。
a 0- > b 0
a 8- > b 1
a 1- > b 2
a 2- > b 4
a 4- > b 8
a 9- > b 3
a 3- > b 6
a 6- > b 12
a 12- > b 9
a 10- > b 5
a 5- > b 10
a 11- > b 7
a 7- > b 14
a 14- > b 13
a 13- > b 11
a 15- > b 15
したがって、一時的に1ブロックの追加スペースだけでソートする場合はt、O（1）で次のように実行できます。
t = a8; a8 = a4; a4 = a2; a2 = a1; a1 = t
t = a9; a9 = a12; a12= a6; a6 = a3; a9 = t
t = a10; a10 = a5; a5 = t
t = a11; a11 = a13; a13 = a14; a14 = a7; a7 = t
編集：
一般的なケース（N！= 16の場合）は、O（N）で解ける場合、実際には興味深い質問です。サイクルは常に満たす素数で始まり、インデックスにはi n + 1 = 2i n mod Nのp < N/2 && N mod p != 0ような繰り返しがあると思いますが、それを証明することはできません。この場合、O（N）アルゴリズムを導出するのは簡単です。
誤解しているかもしれませんが、順序が常に指定されたものと同じである場合は、最適なソリューションを「事前にプログラム」する（つまり、すべての比較を回避する）ことができます（スワップの数が最小になるソリューションになります）。 ABCDEFGHIJKLMNOPに与えられた文字列から移動します。これは、これほど小さいものについては、手作業で解決できます。LiKaoの回答を参照してください）。
セットに番号を付ける方が簡単です。
0 2 4 6 8 10 12 14 1 3 5 7 9 11 13 15
14から開始し、すべての偶数を移動して配置します（8スワップ）。あなたはこれを得るでしょう：
0 1 2 9 4 6 13 8 3 10 7 12 11 14 15
ここで、さらに3つのスワップが必要です（9と3、7と13、11と13を7から移動）。
合計11のスワップ。一般的な解決策ではありませんが、いくつかのヒントが得られる可能性があります。
意図した順列を、アドレス ビット `abcd <-> dabc' のシャッフルとして表示することもできます (abcd はインデックスの個々のビットです)。
#include <stdio.h>
#define ROTATE(v,n,i) (((v)>>(i)) | (((v) & ((1u <<(i))-1)) << ((n)-(i))))
/******************************************************/
int main (int argc, char **argv)
{
unsigned i,a,b;
for (i=0; i < 16; i++) {
a = ROTATE(i,4,1);
b = ROTATE(a,4,3);
fprintf(stdout,"i=%u a=%u b=%u\n", i, a, b);
}
return 0;
}
/******************************************************/
それは私が信じるカウントソートでした