【アルゴリズム】図で解説する「分散数え上げソート」

  • 2012.09.02 Sunday
  • 12:06
JUGEMテーマ:コンピュータ
 
分布数え上げソート

分布数え上げソートは、ソート元の配列の末尾の値から、以下の処理を繰り返す事で、ソートされた配列をえるこがでいます。以下の処理とは、

カウンタテーブルを用意する。
ソート後の配列の入れ物を用意する。
配列に格納された値に対して、カウンタテーブルにソート後のインデックスを問い合わせ、ソート後の配列に値を格納します。

1.カウンタテーブルを用意する。
「カウンタテーブルを用意する」に関しての詳細を説明します。カウンタテーブルは、値に対して、ソート後のIndexを教える仕組みです。カウンタテーブルは、配列で実装します。手順は以下の通りです。

1.1.ソート元の配列の最小値から最大値までが格納可能な配列(カウンタテーブル)を用意する。
最小値MINが配列要素の0の位置になり、最大値MAXが配列要素のMAX - MIN - 1となるような配列を用意します。

分布数え上げソート
今回の例では、最小値が0で最大値が5なので、カウンタテーブルは6つの要素を6個の要素を持つ配列を生成することになります。また、C#では値型の配列の要素の初期値は指定しないと0になるので初期化する必要はありませんが、後の処理のため要素を0にしておく必要があります。

1.2.ソート前の配列の値をカウンタテーブルに数え上げます。

分布数え上げソート
今回の例では、
0は2個あるので、カウンタテーブルの0番目の要素の値は2
1は1個あるので、カウンタテーブルの1番目の要素の値は1
2は0個あるので、カウンタテーブルの2番目の要素の値は0
3は3個あるので、カウンタテーブルの3番目の要素の値は3
4は0個あるので、カウンタテーブルの4番目の要素の値は0
5は2個あるので、カウンタテーブルの5番目の要素の値は2

1.3.カウンタテーブルを累積個数にする。
N番目の要素の値を、0からN番目の値の合計に変換します。累積させることにより、たとえばソート前の3という値は、ソート後の3〜5のインデックスに配置されるということが分かるようになります。

分布数え上げソート
カウンタテーブルの0番目の要素は、0未満の要素がないので、累積個数は2個
カウンタテーブルの1番目の要素は、2 + 1 で、累積個数は3個
カウンタテーブルの2番目の要素は、2 + 1 + 0 で、累積個数は3個
カウンタテーブルの3番目の要素は、2 + 1 + 0 + 3 で、累積個数は6個
カウンタテーブルの4番目の要素は、2 + 1 + 0 + 3 + 0 で、累積個数は6個
カウンタテーブルの5番目の要素は、2 + 1 + 0 + 3 + 0 + 2 で、累積個数は8個

ということで、カウンタテーブルの作成は完了です。

2.ソート後の配列の入れ物を用意する。
2.1.ソート前の配列の末尾からカウンタテーブルに配置先を問い合わせて再配置していきます。
さらに、カウンタテーブルは、問い合わされたインデックスの値をデクリメントします。

末尾から処理を行うのは、安定ソートを実現するためです。先頭からおこなった場合、重複キーが存在した場合、重複キー内で順序が逆順になってしまいます。










ソート元の配列の要素の値が、カウンタテーブルのインデックスに対応し、対応したカウンタテーブルの要素の値がソート後の配列のインデックス、つまり格納先になります。

これで、最終的には以下のようになります。



「分散数え上げソート」のお絵かき終わり!

C#で実装すると下記のようになります。


public static int[] Sort(int[] arrary)
{
    int max = arrary.Max();
    int min = arrary.Min();

    // 配列のインデックスがarraryの個々の値 - minに対応する配列を用意する。
    // 言語仕様により配列の要素が0になっていることを期待している。
    // ex) arraryが{-1,4,4,5}の場合は、{0,0,0,0,0,0,0}という配列を用意される。
    var countTable = new int[max - min + 1];

    // arraryの要素の値をcountTableの添え字と見立てて、countTableにarraryの値の分布を作成
    // ex) arraryが{-1,4,4,5}の場合は、{1,0,0,0,0,2,1}という配列になる。
    foreach (int value in arrary)
    {
        countTable[value - min]++;
    }

    // 分布を累積分布に変換する。
    // ex) arraryが{-1,4,4,5}の場合は、{1,0,0,0,0,2,1}から{1,1,1,1,1,3,4}という配列になる。
    for (int i = 0; i < countTable.Length - 1; i++)
    {
        countTable[i + 1] += countTable[i];
    }

    var result = new int[arrary.Length];
    for (int arraryIndex = arrary.Length - 1; arraryIndex >= 0; arraryIndex--)
    {
        // arrayの要素の値からcountTableを参考に、結果の配列の格納先の添え字を決定する。
        // 使用したcountTableの要素の値を、使用した目印をつけるため1デクリメントする。
        int countTableIndex = arrary[arraryIndex] - min;
        countTable[countTableIndex] -= 1;
        int resultIndex = countTable[countTableIndex];

        result[resultIndex] = arrary[arraryIndex];
    }
    return result;
}

コメント
コメントする








    
この記事のトラックバックURL
トラックバック

calendar

S M T W T F S
  12345
6789101112
13141516171819
20212223242526
2728293031  
<< January 2019 >>

あわせて読みたい

あわせて読みたいブログパーツ

selected entries

categories

archives

recent comment

  • 【キーボード】6年前のRealForceを復活させることはできる!?その3
    art55 (05/22)
  • 【キーボード】6年前のRealForceを復活させることはできる!?その3
    分解大好き (05/18)
  • 【.NET Framework 4.5】 IListがIReadOnlyListを継承してない理由。
    art55 (02/04)
  • 【.NET Framework 4.5】 IListがIReadOnlyListを継承してない理由。
    Gen (02/04)
  • 【キーボード】RealForce が壊れて帰ってきた。
    art55 (04/29)
  • 【.NET Framework 4.5】 IListがIReadOnlyListを継承してない理由。
    art55 (02/23)
  • 【.NET Framework 4.5】 IListがIReadOnlyListを継承してない理由。
    かるあ (02/22)
  • 【C#】Dictionaryの実装・データ構造・アルゴリズムを観察する。
    art55 (01/16)
  • 【C#】Dictionaryの実装・データ構造・アルゴリズムを観察する。
    karuakun (01/16)
  • 【NetOffice】【Excel】死なないExcelプロセスをKillする。
    art55 (12/05)

recent trackback

recommend

recommend

recommend

C#プログラマのための.NETアプリケーション最適化技法 (Programmer's SELECTION)
C#プログラマのための.NETアプリケーション最適化技法 (Programmer's SELECTION) (JUGEMレビュー »)
Sasha Goldshtein,Dima Zurbalev,Ido Flatow,サシャ・ゴルドシュタイン,ディマ・ズルバレフ,イド・フラトー

recommend

ろんりと集合
ろんりと集合 (JUGEMレビュー »)
中内 伸光
とてもわかりやすいです。

recommend

recommend

シャノン・ノイマン・ディジタル世界
シャノン・ノイマン・ディジタル世界 (JUGEMレビュー »)
市川 忠男
4章がリレーショナルデータベースな内容になってます。ページ数があまりありませんが、ポイントがものすごく的確にまとまっていて、感動します。

recommend

recommend

東プレ Realforce91UBK-S 静音キーボード 静電容量無接点方式 変荷重 ブラック NG01BS
東プレ Realforce91UBK-S 静音キーボード 静電容量無接点方式 変荷重 ブラック NG01BS (JUGEMレビュー »)

テンキーレス、静音のRealForce91UBK-S。スコスコ感がたまらなく気持ちいいです。家と会社で2台持ってます。

recommend

recommend

プログラミング.NET Framework 第4版 (プログラミングシリーズ)
プログラミング.NET Framework 第4版 (プログラミングシリーズ) (JUGEMレビュー »)
Jeffrey Richter
発売予定美 2013年10月10日。.NET Frameworkとお付き合いする人のバイブルですね。

recommend

recommend

キャット・シッターの君に。
キャット・シッターの君に。 (JUGEMレビュー »)
喜多嶋 隆
私のイラストレータデビュー本です。

recommend

Essential .NET ― 共通言語ランタイムの本質
Essential .NET ― 共通言語ランタイムの本質 (JUGEMレビュー »)
ドン・ボックス,クリス・セルズ,Don Box,Chris Sells,吉松 史彰

links

profile

search this site.

others

mobile

qrcode

powered

無料ブログ作成サービス JUGEM