|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 鳩 ： [はと] 【名詞】 1. pigeon 2. dove ・ 巣 ： [す] 【名詞】 1. nest 2. rookery 3. breeding place 4. beehive 5. cobweb 6. den 7. haunt ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana)
鳩の巣ソート（はとのすソート、）はソートアルゴリズムの一種であり、要素数 (''n'') とソートキーの値の個数 (''N'') がほぼ同じ場合に適した手法である〔NIST's Dictionary of Algorithms and Data Structures: pigeonhole sort 〕。必要な時間計算量は Θ(''n'' + ''N'') である。 == 概要 == 鳩の巣ソートは次のように動作する。 # 初期状態で空の「鳩の巣」の配列を用意する。個々の鳩の巣にはソートキーの1つの値が対応している。それぞれの鳩の巣には、そのソートキーを持つ要素のリストを格納する。 # 入力配列を順に見ていき、それぞれの要素を対応する鳩の巣のリストに入れていく。 # 鳩の巣の配列を順に走査し、空でない鳩の巣にある要素を順次並べていく。 例えば、以下のような値の対を、それぞれの先頭の値をキーとしてソートする。 * (5, "hello") * (3, "pie") * (8, "apple") * (5, "king") キーの値は3から8なので、それぞれについて鳩の巣を設定し、各要素を鳩の巣に移動する。 * 3: (3, "pie") * 4: * 5: (5, "hello"), (5, "king") * 6: * 7: * 8: (8, "apple") 次に鳩の巣の配列を順次走査し、出現順に元の配列に戻していけばよい。 バケットソートに似ているが、バケットソートでは補助配列にはキーごとの要素数のみを格納し、要素そのものは格納しない。上の例では、次のようになる。 * 3: 1 * 4: 0 * 5: 2 * 6: 0 * 7: 0 * 8: 1 この情報を使うと、ソートキーの値を見ただけでソート後の位置を示すことができる。 ''N'' が ''n'' よりずっと大きい場合、より一般的なバケットソートの方が効率的である。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「鳩の巣ソート」の詳細全文を読む スポンサード リンク
|