アルゴリズム論（第３回）

(1)

アルゴリズム論

（第３回）

佐々木研（情報システム構築学講座）

講師山田敬三

[email protected]

(2)

バケットソート

(3)

バケットソート

• 入力列を 𝑘𝑘𝑘𝑘𝑘𝑘 𝑎𝑎_𝑖𝑖 の昇順に整列した列を返す．

(4)

バケットソートのアルゴリズム

各 0 ≤ 𝑥𝑥 ≤ 9 について，𝑃𝑃_𝑥𝑥 を用意する．

for 𝑖𝑖 ← 1 to 𝑛𝑛 do 𝑘𝑘 ← 𝑘𝑘𝑘𝑘𝑘𝑘 𝑎𝑎_𝑖𝑖

𝑎𝑎_𝑖𝑖 を 𝑃𝑃_𝑦𝑦 の末尾に追加する．

end

𝑃𝑃₀ から 𝑃𝑃₉ までを連接し，出力する．

(5)

実行例（ 𝑘𝑘𝑘𝑘𝑘𝑘 𝑎𝑎

_𝑖𝑖

は一の桁）

入力列：１２５，９００，１２３，８００，１４３，７００，６００，５０１ 𝑃𝑃₀：

𝑃𝑃₁： 𝑃𝑃₃： 𝑃𝑃₅：

出力列：９００，８００，７００，６００，５０１，１２３，１４３，１２５９００，８００，７００，６００

５０１

１２３，１４３１２５

(6)

基数ソート

(7)

基数ソート

• キーが整数のときに利用できる．

• キーの最大桁数を 𝑘𝑘 とする．（最大値が1234のとき，𝑘𝑘 = 4）

(8)

基数ソートのアルゴリズム

for 𝑗𝑗 ← 1 to 𝑘𝑘 do

列を下位から第 𝑗𝑗 桁目に関して整列する．

ただし，第 𝑗𝑗 桁目の値が同じ要素については，

それらの順番が整列の前後で変わらないようにする．

end

安定した整列アルゴリズム

(9)

実行例

入力列：１２５，９００，１２３，８００，１４３，７００，６００，５０１一の桁：９００，８００，７００，６００，５０１，１２３，１４３，１２５十の桁：９００，８００，７００，６００，５０１，１２３，１２５，１４３百の桁：１２３，１２５，１４３，５０１，６００，７００，８００，９００

(10)

クイックソート法

(11)

クイックソート法

考え方

• 与えられた問題を，繰り返しより小さな問題に分割して，

その小問題を解く（分割統治法）

• 例）解答用紙を整列する：まず十の位でソートして、できた各束を一の位でソートする．

(12)

クイックソート法

1. iを先頭要素番号、jを末尾要素番号とする 2. pivotを配列の任意の要素から設定

3. i>jとなるまで4.～6.を繰り返す

12 7 9

6 15 23 2 10 4 20

pivot

i j

(13)

クイックソート法

4. iを増加させ、a[i]≧pivotが見つかるま で走査

5. jを減少させ、a[j]≦pivotが見つかるま で走査

6. i≦jならばa[i]とa[j]を交換し、iを1増 加、jを1減少させて3.へ

i j

12 7 9

6 15 23 2 10 4 20

i 6

i 9

i 12

i 7

j 20 i

15

j 4 j 15 i

4 15

4

i 23

j 10 i

10

j 23

10 23

i,j 2 j 2

i 23

(14)

クイックソート法

• 分割された各部分に対して再び1.～6.の手順を繰り返す

• 分割した結果、対象となる要素数が1となったら終了

12 7 9

6 4 10 2 23 15 20

12

7 9

6 2 4 10 15 23 20

12

7 9

6 2 4 10 15 23 20

(15)

クイックソート法の計算量

• 平均

• 最大

(16)

ソート法まとめ

比較による

時間計算量

空間

計算量安定性単純選択ソート有 𝑂𝑂 𝑁𝑁² 𝑂𝑂 1 無単純挿入ソート有 𝑂𝑂 𝑁𝑁² 𝑂𝑂 1 有バブルソート有 𝑂𝑂 𝑁𝑁² 𝑂𝑂 1 有クイックソート有 𝑂𝑂 𝑁𝑁log 𝑁𝑁 𝑂𝑂 log 𝑁𝑁 無バケットソート無 𝑂𝑂 𝑁𝑁 𝑂𝑂 𝑁𝑁 有

(17)

問題

• 次の配列を単純選択法，単純挿入法，バブルソート，クイックソート

（最初の分割のみ，pivotは任意）で，それぞれ整列しなさい．

８，４，６，５，１，７，２

• 次の配列を基数ソートを用いて，整列しなさい．

８５１，３６７，７８３，４７８，１４３，１１７，１２７，５０９

アルゴリズム論 （第３回）