【アルゴリズム】C#で分布数え上げソートの実装する

  • 2012.08.29 Wednesday
  • 19:30
JUGEMテーマ:コンピュータ

----------------------------
【アルゴリズム】図で解説する「分散数え上げソート」
追記しました。
----------------------------

分布数え上げソート

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;
}

とりあえず実装しなおしてみた。


----------------------------
タイトルを「分散数え上げソート」から「分布数え上げソート」に変更しました。
参考にしていた書籍には分散という言葉が使われていましたが
一般的には「分布」という言葉で表現されているようです。

コメント
管理者の承認待ちコメントです。
  • -
  • 2018/06/15 9:03 AM
コメントする








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

calendar

S M T W T F S
 123456
78910111213
14151617181920
21222324252627
282930    
<< April 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