Web教材一覧>
アルゴリズム
(BOK大区分:1 基礎理論、中区分:2 アルゴリズムとプログラミング、中区分:2 アルゴリズム)
通常のソートは、元の配列要素を変更する処理ですが、ここでは配列自体はそのままにしておき、それに関連した新しい配列に順序に関する情報を与える方法について学習します。
アルゴリズム、順位づけ、インデクス、ポインタ
ここでは、配列aはそのままに(要素を動かさずに)しておき、別の配列bに、順序に関する値を入れる操作をまとめました。
配列aの順位を配列bに入れる操作、すなわち、要素a[i] が小さい順にk番目であるとき、b[i]=k とする操作です。
ケース1
i 1 2 3 4 5
a[i] 30 20 50 10 40
b[i] 3 2 5 1 4
aに同じ値があるときは、それを同順位とし、次の要素の順位は、同順位を考慮したものにします。
ケース2
i 1 2 3 4 5
a[i] 10 20 40 10 40
b[i] 1 3 4 1 4
アルゴリズム
配列要素のなかに a[i] よりも小さい要素がk個あれば、a[i] の順位、すなわち b[i] の値は k+1 になります。それで、a[i] と a[j] を比較して、a[i]<a[j] であれば b[j] に1を加え、a[i]>a[j] であれば b[i] に1を加えればよいことがわかります。a[i]=a[j] のときは、どちらにも1を加えないことにより、同順位になります。
なお、最小の順位を(0ではなく)1にするため、bの要素の初期値を1にしておきます。
プログラム
ア for (i=1; i<=n; i++) { ─┐
イ b[i] = 1; ├bの初期値を1にする
ウ } ─┘
エ for (i=2; i<=n; i++) {
オ for (j=1; j<=i-1; j++) {
カ if ( a[j] < a[i] ) b[i]++; ─┐大きいほうの順位を下げる
キ if ( a[j] > a[i] ) b[j]++; ─┘=のときは何もしない
ク }
ケ }
トレース
ケース1
i j a[i] a[j] 比較 b[1] b[2] b[3] b[4] b[5]
1 1 1 1 1
2 1 20 30 < 2
3 1 50 30 > 2
2 50 20 > 3
4 1 10 30 < 2
2 10 20 < 3
3 10 50 < 4
5 1 40 30 > 2
2 40 20 > 3
3 40 50 < 5
4 40 10 < 4
結果 2 3 5 1 4
ケース2
i j a[i] a[j] 比較 b[1] b[2] b[3] b[4] b[5]
1 1 1 1 1
2 1 20 10 > 2
3 1 40 10 > 2
2 40 20 > 3
4 1 10 10 =
2 10 20 < 3
3 10 40 < 4
5 1 40 10 > 2
2 40 20 > 3
3 40 40 =
4 40 10 > 4
結果 1 3 4 1 4
配列bの要素 b[k] に、k番目に小さい値をもつ配列aの要素番号(添字)を入れる操作です。
下の表で、b[1]=4は、配列aで1番小さい値をもつ要素の添字が4、すなわち a[4] であることを示しています。同様に、b[2]=2は、2番目に小さい要素の添字が2、すなわち a[2] であることを示しています。
すなわち、k番目に小さい要素は、a[b[k]] になります。
ケース1
1 2 3 4 5
a[i] 30 20 50 10 40
b[k] 4 2 1 5 3
アルゴリズム
例えば、a[1]=30 は、小さいほうから3番目ですが、それを求めるには、a[1] 以下の要素の個数は、自分を含めて3個なので、b[3]=1 となります。一般化すれば、全要素(自分を含めて)のうち、a[i] 以下の要素がk個のとき、a[i] はk番目になるので、b[k]=i となります。
しかし、これでは配列aに同じ値があるとき、同じkになってしまうので、配列bに定義されない要素が発生します。それを防ぐために「同じ値があるときは、要素番号が小さいほうが順位が上」というルールを追加します。すなわち、同値の場合は添字の大小比較をすることにします。
プログラム
ア for (i=1; i<=n; i++) {
イ k = 0;
ウ for (j=1; j<=n; j++) {
エ if ( ( a[j] < a[i] )
オ || ( a[j] == a[i] ) && ( j <= i ) ) {
カ k++;
キ }
ク }
ケ b[k] = i;
コ }
ポインタとは、次にくる要素の要素番号を示すものです。
i 1 2 3 4 5
a[i] 30 20 50 10 40
p[i] 5 1 0 2 3
全要素のうち最小の要素は a[4] で、次に小さいのは a[2] ですから、 p[4] =2 になります。a[2] の次は a[1] ですから、 p[2] =1 になります。このpのことをポインタといいます。最後になる p[3] は、次がないので0とします。
アルゴリズム
効率の良いアルゴリズムには2本木を用いたピープソートがありますが、ここでは「非効率だが単純」なアルゴリズムを考えます。
a[2] について考えます。a[1] の前になる(a[1] の次が a[2] である)ことから、p[2] =1になります。一般化すれば、a[i] が a[1] ~ a[i-1] のうちの最小値 a[imin] よりも小さいならば、p[i] は最小値をもつ要素の番号 imin になります。
a[3] について考えます。これまでの最大値である a[1] よりも大きいので、p[1] を3にします。一般化すれば、a[j] が a[1] ~ a[j-1] のうちの最大値a[imax] よりも大きいならば、p[imax] がjになります。
a[j] が a[1] ~ a[j-1] のうちの最小値でも最大値でもないケースとして a[5] があります。これまでに、次のようになっているとします。
i 1 2 3 4
a[i] 30 20 50 10
p[i] 3 1 0 2
a[5] は a[1] と a[3] の間になるので、p[1] を5にして、p[5] を3にすればよいことになります。一般化すれば、a[i] の直前の要素の添字をkとすれば、p[i] = p[k] として、p[k] =i とすることになります。
ここで、「a[5] は a[1] と a[3] の間になる」ことをどのように探すのかが問題になります。これが効率に大きく関係するのですが、ここでは「最小値をもつ要素からポインタを次々にたどる」ことにします。
なお、ここでは単純にするために、同値の要素はないと仮定しておきます。
プログラム
ア for (i=1; i<=n; i++) {
イ p[i] = 0;
ウ }
エ imin = 1;
オ imax = 1;
カ for (i=2; i<=n; i++) {
キ if ( a[i] < a[imin] ) { ── ケースA(<最小値)
ク p[i] = imin;
ケ imin = i;
コ }
サ else if ( a[i] > a[imax] ) { ── ケースB(>最大値)
シ p[imax] = i;
ス imax = i;
セ }
ソ else { ── ケースC(中間)
タ j = imin; ┐
チ while ( a[j] < a[i] ) { │
ツ k = j; ├ a[j] > a[i] となる
ツ j = p[j]; │ 直前のkを探す
テ } ┘
ト p[i] = p[k];
ナ p[k] = i;
ニ }
ヌ }
トレース
----直前の状況---- iの変化 ---------その結果-----------
imin a[imin] imax a[imax] i a[i] ケース p[1] p[2] p[3] p[4] p[5] imin imax
1 30 1 30 2 20 A 1 2
2 20 1 30 3 50 B 3 3
2 20 3 50 4 10 A 2 4
4 10 3 50 5 40 C(注) 5 3
結果 5 1 0 2 3
(注)ここまでの状況 i=5, a[5]=40, imin=4
j a[j] チの比較 k j
4 10 < 4 2
2 20 < 2 1
1 30 < 1 3
3 50 > ループ終了→このときのkは1
ト: p[5] = p[1] (=3)
ナ: p[1] = 5