1-7 アルゴリズム
東京大学 数理・情報教育研究センター
2021年4月6日

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

概要•

データ・AI利活用に必要なアルゴリズムの基礎を学び、代表的なアルゴリズムである探索と並べ替えについて学習します。

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

2

本教材の目次
１．アルゴリズムとは

4

２．アルゴリズムの例

5

３．フローチャートとは

11

４．フローチャートの例

14

５．探索のアルゴリズム

20

６．リスト探索（線形探索、二分探索）

22

７．木探索（幅優先探索、深さ優先探索）

40

８．並べ替えのアルゴリズム

52

９．バブルソート

53

10．選択ソート

63

11 ．挿入ソート

69

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

3

アルゴリズムとは•アルゴリズムとは、「問題」を解くための手順を意味します。
• アルゴリズムを「問題」に対する解法と理解しても良いでしょう•

様々な「問題」が考えられます。例えば、次の様な「問題」を挙げることができます。
• 与えられた2つの数の和を求める（2つの数の足し算を行う）• データの集まりの中からあるデータを探し出す• 数を小さい順（昇順）に並べる• 文章の中から特定の文字列を抜き出す• 数が素数かどうか調べる

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

4

アルゴリズムの例•

アルゴリズムの例を考えます。例として、次の様な「問題」を考えます。

•

問題1：「10と5という2つの数が与えられたとき、その和を求める」•

この問題に対するアルゴリズムは例えば、次の様になります。
• アルゴリズム1：
手順1：10+5 を計算して、その計算結果をzに代入する
手順2：zを求めるべき結果として出力してアルゴリズムを終了する•

同じ問題でも様々なアルゴリズムが考えられます。例えば、この問題では次の様なアルゴリズムも同じ結果となります。
• アルゴリズム1改：
手順1：15 を出力してアルゴリズムを終了する

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

5

アルゴリズムの例•

もう少しアルゴリズムの例を見ていきます。

•

問題2：「2つの数が与えられたとき、その和を求める」•

この問題に対するアルゴリズムは例えば次の様になります。
• アルゴリズム2：

手順1：1つの目の数であるxを決める（数を入力して、xに代入する）

手順2：2つの目の数であるyを決める（数を入力して、yに代入する）
手順3：x+y を計算して、その計算結果をzに代入する
手順4：zを出力してアルゴリズムを終了する

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

6

アルゴリズムの例•

もう少しアルゴリズムの例を見ていきます。

•

問題3：「サイコロを5回振って、出た目の和（合計）を求める」•

この問題に対するアルゴリズムは例えば、次の様になります。
• アルゴリズム3：
手順1：サイコロを振って、出た目をzに代入する
手順2：サイコロを振って、出た目をzに加える
手順3：サイコロを振って、出た目をzに加える
手順4：サイコロを振って、出た目をzに加える
手順5：サイコロを振って、出た目をzに加える
手順6：zを出力してアルゴリズムを終了する

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

7

アルゴリズムの例•

アルゴリズム3が冗長に感じる場合、次の様なアルゴリズムも考えられます。
• アルゴリズム3改：
手順1：z=0とし、c=0とする（サイコロを振った数を変数cで数える）
手順2：サイコロを振って、出た目をzに加える
手順3：cの値を1増やす
手順4：cが5ならzを出力してアルゴリズムを終了する。そうでなければ、手順2に戻る

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

8

アルゴリズムの例•

問題4：「偶数の目が出るまでサイコロを振って、出た目の総和を出力する」•

この問題に対するアルゴリズムは例えば次の様になります。
• アルゴリズム4：
手順1：z=0とする（出た目をzに加えていく）
手順2：サイコロを振って、出た目をxに代入し、xをzに加える
手順3：xが偶数ならzを出力してアルゴリズムを終了する。そう
でなければ、手順2に戻る

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

9

アルゴリズムの例•

問題5：「1つの整数が与えられたとき、その数が2,3,6のいずれかの倍数か判定する」•

この問題に対するアルゴリズムは例えば次の様になります。
• アルゴリズム5：
手順1：整数を入力して、xに代入する
手順2：xが2で割り切れれば、手順3へ。そうでなければ手順4へ
手順3：xが3で割り切れれば、 「xは6の倍数」と出力して終了。
そうでなければ「xは2の倍数」と出力して終了
手順4：xが3で割り切れれば、「xは3の倍数」と出力して終了。
そうでなければ「xは2,3,6の倍数ではない」と出力して終了

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

10

フローチャートとは••アルゴリズムは、前頁までの様に言葉だけで記述しても構わないのですが、アルゴリズムの表現の1つとしてフローチャートと呼ばれる図（流れ図とも呼びます）を用いてアルゴリズムの手順を直感的に分かり易くするために可視化する方法があります。
フローチャートの定義は後で説明します。まず、前述のアルゴリズ
ムをフローチャートで表してみます。
開始

アルゴリズム1：
手順1：10+5 を計算して、その計算結果をzに代入する

zに10+5を代入

手順2：zを求めるべき結果として出力してアルゴリズムを終了
する

zを出力

終了
東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

11

フローチャートとは•フローチャートは、幾つかの記号を矢印で繋いだ図で表します。
• この教材ではJISの規格にそったフローチャートを紹介します。
• 記号の色はこの教材独自のもので一般的なものではありません。

•

アルゴリズムの手続きの種類毎に用いるべき記号が定められています。
• 様々な手続き（記号）が存在しますが、この教材では代表的なもののみ紹介し
ます。

•

記号の名前
開始

端子

zに10+5を代入

処理

zを出力

データ

終了

端子

各手続きを表す記号を矢印で繋いで、手続きの順番を表します。

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

12

フローチャートとは•基本的な記号を説明します。

•

端子：フローチャート、すなわち、アルゴリズムの開始と終了を主に表します。

••

処理：演算や変数への代入などあらゆる処理を表します。
データ：値（データ）の入出力を表します。右の例では、出力を表しています。

東京大学 数理・情報教育研究センター

記号の名前
開始

端子

zに10+5を代入

処理

zを出力

データ

終了

端子

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

13

フローチャートの例•

別のフローチャートの例です。
アルゴリズム2：
手順1：1つの目の数であるxを決める（数を入力して、xに代入する）
手順2：2つの目の数であるyを決める（数を入力して、yに代
入する）

記号の名前
開始

端子

xを入力

データ

yを入力

データ

zにx+yを代入

処理

zを出力

データ

終了

端子

手順3：x+y を計算して、その計算結果をzに代入する
手順4：zを出力してアルゴリズ
ムを終了する

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

14

フローチャートの例•

別のフローチャートの例です。
アルゴリズム3：開始

サイコロを振って、出た目をzに代入

手順1：サイコロを振って、出た目をzに代入する

サイコロを振って、出た目をzに加算

手順2：サイコロを振って、出た目をzに加える

サイコロを振って、出た目をzに加算

手順3：サイコロを振って、出た目をzに加える
手順4：サイコロを振って、出た目をzに加える

サイコロを振って、出た目をzに加算

サイコロを振って、出た目をzに加算

手順5：サイコロを振って、出た目をzに加える
手順6：zを出力してアルゴリズム
を終了する

zを出力
終了

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

15

フローチャートの例•

開始

別のフローチャートの例です。

zに0を代入、cに0を代入
アルゴリズム3改：
手順1：z=0とし、c=0とする

サイコロを振って、出た目をzに加算

手順2：サイコロを振って、出た目をzに加える
手順3：cの値を1増やす
手順4：cが5ならzを出力してアルゴリズムを終了する。そうでなければ、手順2に戻る

cの値を1増やす

No

c=5?

Yes
zを出力
終了

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

16

フローチャートとは
•
•

記号の名前
開始

端子

zに0を代入、cに0を代入

処理

サイコロを振って、出た目をzに加算

処理

cの値を1増やす

処理

新しい記号が出てきたので説明します。
判断：手続きの分岐を行うための端子です。条件を記述し、その条件が満たされる場合と満たされない場合とで分岐します。右の例の判断では、cが5であれば、zを出力する手続きへ進み、
そうでなければ、サイコロを振る手続きに戻ります東京大学 数理・情報教育研究センター

No

c=5?

Yes

判断

zを出力

データ

終了

端子

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

17

フローチャートの例•

開始

別のフローチャートの例です。

zに0を代入アルゴリズム4：
手順1：z=0とする

サイコロを振って、出た目をxに代入

手順2：サイコロを振って、出た目をxに代入し、xをzに加える
手順3：xが偶数ならzを出力してアルゴリズムを終了する。そうでなければ、手順2に戻る

xをzに加える

No

xは偶数?

Yes
zを出力
終了

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

18

フローチャートの例•

開始

別のフローチャートの例です。

x を入力
アルゴリズム5：
手順1：整数を入力して、xに代入
する

xは2で割り切れる？

xは3で割り切れる？

Yes

手順2：xが2で割り切れれば、手順3へ。そうでなければ手順4へ

No

手順3：xが3で割り切れれば、 「xは6の倍数」と出力して終了。そうでなければ「xは2の倍数」と出力して終了

xは3で割り切れる？

手順4：xが3で割り切れれば、「xは3の倍数」と出力して終了。そうでなければ「xは2,3,6の倍数ではない」と出力して終了

Yes

6の倍数と出力Yes

No

2の倍数と出力3の倍数と出力No

2,3,6の倍数ではないと出力終了
東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

19

代表的なアルゴリズム•

アルゴリズムについて説明した頁において、紹介した以下の2つの問題は代表的な問題であり、この問題を解くための様々なアルゴリズが考案されています。
• 探索（サーチ）：データの集まりの中から、あるデータを探し出す• 並べ替え（ソート）：数を小さい順（昇順）に並べる•

これからそれぞれの問題に対する代表的なアルゴリズムを紹介します。

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

20

探索のアルゴリズム•

探索（サーチ）は、データの集まりの中からあるデータを探し出す問題です。
• 例えば、数の集まりの中から特定の値（例えば、最小値、最大値、ある値以上の値など）を見つけたり、文字列の中から特定の文字列を見つけたりすることは探索の問題とみなせます。

• あとで説明する並べ替えのアルゴリズムでも探索が利用されています。（選択ソートで最小値を探したり、挿入ソートで数の適切な挿入位置を探したりします）•

本教材では、以下の代表的な探索アルゴリズムを説明します。
• リスト探索• 木探索東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

21

リスト探索••

リスト探索は、順序付けられたデータ（値）の中から目的の値を探す（探索を行う）問題です。
「順序付けられたデータ」はやや複雑な表現ですが、要するに「○番目のデータ」と呼ぶことができる形式で保管されているデータを考えるということです。この教材では「配列」と呼ばれるデータ構造に格納されていると考えます。
• この教材では下の図の様な、長方形を繋げた図で配列を表します。

8
•

6

10 0

5

本教材では、以下の代表的なリスト探索のアルゴリズムを説明します。
• 線形探索• 二分探索東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

22

配列について••探索について説明する前に配列の基本について説明します。
配列は値を順序付けて格納します。例の図では一番左を先頭（ 1番目）の値、一番右を最後（例では、5番目）の値として扱います。それぞれ「配列のi番目の数」という呼び方をすることにします。
• 以下の例では、配列の1番目の値は8、3番目の値は10です。

•

配列に格納している値の数を、「配列の要素数」と呼ぶことにします。
• 以下の例では、配列の要素数は5になります。

8

東京大学 数理・情報教育研究センター

6

10 0

5

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

23

線形探索
•

線形探索は、配列の先頭から順に目的の値を探すアルゴリズムです。

•

単純なアルゴリズムですが、配列に格納されている値が規則的に並んでいない場合は線形探索が最も有効なアルゴリズムとなります。
• 配列が短い場合、人間の目では目的の値が格納されている位置はすぐに分かりますが、アルゴリズムを考える（問題を解く）には
配列の長さがどうであろうと明確な手順に従って目的の値を探す必要があります。
• 逆に、規則的に並んでいる場合とは、例えば、値が昇順に並んでいる場合が該当します。
値が規則的に並んでいない

8

6

10 0

5

値が規則的に並んでいる

0

5

6

10

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

8

24

線形探索
•

以下の例で、目的の値を7とし、配列の中から7を探す場合を考えます。

•

まず1番目の値が7かどうか調べます。1番目の値は10ですので、7ではあ
りません。

10 5

•

9

13 7

12 2

9

3番目の値が7かどうか調べます。3番目の値は13ですので、7ではあり
ません。

10 5

•

12 2

2番目の値が7かどうか調べます。2番目の値は5ですので、7ではあり
ません。

10 5

•

13 7

13 7

12 2

9

4番目の値が7かどうか調べます。4番目の値は7ですので、7を発見したと報告してアルゴリズムを終了します。

10 5東京大学 数理・情報教育研究センター

13 7

12 2

9

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

25

線形探索
•

配列に含まれていない値を目的の値として探索した場合は、先頭から最後まで目的の値を探索した後に、その値が見つからなかったと報告
してアルゴリズムを終了します。
• 例えば、以下の配列の例では、8を探索した場合は、その様にして探索を終了します。

10 5東京大学 数理・情報教育研究センター

13 12 72

94-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

26

線形探索
•

線形探索のアルゴリズムは次の様になります。 （配列の要素数をnとします）
手順1：x を入力
手順2：i=1（探索する値を入力）（配列のi番目の値が目的の値xか調べたい）

手順3：配列のi番目の数とxを比較し、一致するならば、xを発見したと報告（出力）して終了する。そうでなければ手順4へ
手順4：iを1増加する
手順5：iがn+1より小さい場合、手順3へ戻る。そうでなければ手順6へ
手順6：xを発見できなかったと報告（出力）して終了する•

以降の頁では分岐における「そうでなければ手順○○へ」の一文は省略します。例えば、手順3において分岐があり、条件が成立しない場合は手順4を実行するものとします。

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

27

線形探索のフローチャート•

線形探索のフローチャートです。

開始
x を入力

手順1：x を入力

i に1を代入

手順2：i=1
手順3：配列のi番目の数とxを比較し、一致するならば、xを発見したと報告して終了する。そうでなければ手順4へi番目の数=x?

手順4：iを1増加する

i を1増加手順5：iがn+1より小さい場合、
手順3へ戻る。そうでなければ手
順6へ
手順6：xを発見できなかったと報
告して終了する

Yes

No

Yes

結果（発見）
を出力

i<n+1?

No

結果（未発見）を出力終了

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

28

計算量
•

アルゴリズムが動作を終了するのにかかる時間を、そのアルゴリズムの計算量と呼びます。

•

そして、アルゴリズムの性能の良し悪しはこの計算量によって評価します。
• つまり、一般に計算量が小さければ小さい程、良いアルゴリズムと言って構いません。

•

計算量はアルゴリズムを動かすのに使用しているコンピュータの性能に依存して決まるのは好ましくない為、実際にコンピュータで動かしてみたときにかかる時間ではなく、「アルゴリズムが終了するまでにどれくらいの数の手続きを実行したか」で評価します。
• 例えば、線形探索の場合は「手順1から6を何回実行したのか」で評価します。

•

そして、計算量は厳密に評価するのではなく、どのくらいの値に比例する時間がかかるのか、で評価を行います。

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

29

線形探索の計算量•

では、線形探索の計算量を評価してみましょう。配列の大きさをnとした場合、各手順の実行回数は以下の通りです。
• 手順1, 2, 6：1回
• 手順3, 4, 5：最大でn回•

つまり、合計すると最大で（つまり、一番時間がかかる最悪の場合）
3n+3回手順を実行します。

•

よって、線形探索の計算量は最悪の場合、配列の大きさである n に比例することが分かります。
• 「x に比例する大きさ」は O(x) （Oは大文字のオー）という記号で表し、「x のオーダー」、「オーダー x 」などと読みます。
• つまり、線形探索の最悪の計算量はO(n)である、ということもできます。

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

30

二分探索
•

•

二分探索は、線形探索と同様に配列から目的の値を探すアルゴリズム
ですが、探索の対象となる配列は値が昇順（もしくは降順）、すなわ
ち小さい順に並べてあります。
二分探索では探索する値が見つかるまで、探索対象とする配列の範囲を毎回半分になる様に探索を行います。そうすることで線形探索よりも効率的に（つまり、より小さい計算量で）探索を行います。

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

31

二分探索
•

以下の例で、目的の値を7とし、配列の中から7を探す場合を考えます。
先の述べた様に二分探索を行う場合は配列の中身は昇順に並べておく必要があります。

2
•

7

9

10 12 13

まず真ん中（4番目）の値が7かどうか調べます。4番目の値は9ですので7ではありません。

2
•

5

5

7

9

10 12 13

このとき、配列の値は昇順に並んでいますので、真ん中より後（5番目から7番目）の値は4番目の値 (9) より大きくなります。その為、7が配列に含まれているならば、真ん中よりも手前（1番目から3番目）ということになります。そこで以降は4番目から7番目は探索しなくても良く、1番目から3番目に7が含まれているかどうか調べれば良くなります。

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

32

二分探索
•

そこで、2番目に探索を行う場合、先程と同様に探索対象となる配列の真ん中の値が7かどうか調べます。ただし、1回目の探索によって今回は1番目から3番目のみが探索の対象とすれば良いのでした。そこで、今回は1番目から3番目までの真ん中（2番目）の値が7かどうか調べる
ことになります。2番目の値は5ですので7ではありません。

2
•

7

9

10 12 13

4番目から7番目は無視する

先程と同様に、配列の値は昇順に並んでいますので真ん中より手前（1番目）の値は2番目の値より必ず小さくなります。その為、7が配列に含まれているならば、2番目よりも後（3番目）ということになり
ます。

2
•

5

5

7

9

10 12 13

1,2番目、4番目から7番目は無視する

次に、3番目の値が7かどうか調べます。3番目の値は7ですので、 7を発見したと報告してアルゴリズムを終了します。

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

33

二分探索
•

先の例では、最後に目的の値が見つかりましたが、勿論途中で見つかる場合もありますし、最後まで見つからないで探索を終了する場合もあり得ます。
• 例えば、以下の配列の例では、8を目的の値として探索した場合は、8を最後まで発見できずに探索を終了しますし、12を探索した場合には2回目の探索で12を発見することになります。

2

東京大学 数理・情報教育研究センター

5

7

9

10 12 134-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

34

二分探索
•

二分探索のアルゴリズムは次の様になります。 （配列の要素数をnとします）
手順1：x を入力（探索する値を入力）

手順2：left=1, right=n（配列のleft番目からright番目が探索範囲）

手順3：left>rightならば、xを発見できなかったと報告（出力）して終了
する

手順4：mid=[(left+right)/2] （ただし、[x]はx以下の最大の整数。例えば、[5/2]なら2を表す）

手順5：配列のmid番目の値をMで表す。Mとxを比較し、一致するならば、xを発見したと報告（出力）して終了する
手順6：M<xならば、left=mid+1とする。M>xならば、right=mid-1とする（探索範囲を半分にする）
手順7：手順3に戻る
東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

35

二分探索のフローチャート•

二分探索のフローチャートです。

手順1：x を入力

開始

手順2：left=1, right=n

x を入力

手順3：left>rightならば、xを発見できなかったと報告（出力）して終了する

leftに1, rightに n を代入

Yes

手順4：mid=[(left+right)/2]
手順5：配列のmid番目の値をMで表す。Mとxを比較し、一致す
るならば、xを発見したと報告（
出力）して終了する。
手順6：M<xならば、
left=mid+1とする。M>xならば、right=mid-1とする

left > right?

No

left=mid+1
right=mid-1

No

Yes

M<x?

結果（未発見）を出力

mid=[(left+right)/2]

No

M=x?

Yes

結果（発見）
を出力

手順7：手順3に戻る

Yes
東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

終了
36

二分探索の計算量•

二分探索の計算量を評価してみましょう。配列の大きさをnとした場
合を考えましょう。一番時間がかかる場合、探索対象となる配列の範囲は n → n/2 → n/4 → n/8 → … → 1 となりますので、約 log2n 回のmidの計算と比較（手順3から7）が行われます。
• n → n/ 2 → n/22 → n/23 → … → n/2k なので、k+1回手順3から7を行います。このとき、 n/2k =1とするとk = log2nが成立します•

つまり、各手順の実行回数は以下の通りです。
• 手順1,2：1回• 手順3,4,5,6,7：最大で約log2n回••

つまり、合計すると最大で約 5 log2n + 2回手順を実行します。
よって、二分探索の計算量は log2n に比例する (すなわち、O(log2n )である) ことが分かり、線形探索の計算量である n よりも小さくなる
ことが分かります。

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

37

計算量の比較•

線形探索 (O(n)) と二分探索 (O(log2n)) の計算量を比較してみます。nが大きくなるほど二分探索が高速であることが良く分かります。

計 100
算
量 90
80
70
60
50
40
30
20
10
0

2

10

20

30

40
O(n)

東京大学 数理・情報教育研究センター

50

60

70

O(log2n)4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

80

90

n
38

木探索
•
•

•

木探索は、樹形図状のデータ構造である「木構造」に格納された値の中から目的の値を探す（探索を行う）問題です。
木構造は樹形図状のデータ構造です。組織図や家系図、コンピュータ上のファイル・フォルダの階層構造などは樹形図状に表現できま
すが、こういった様々な分野で用いるデータ構造です。
本教材では、以下の代表的な木探索のアルゴリズムを説明します。
• 幅優先探索• 深さ優先探索東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

39

木構造について•

例えば、ファイル・フォルダの階層構造を表す木探索では目的のファイルを探すという操作を考えられます。

•

以下はファルダ類の階層構造の例ですが、この教材では右の図の様な丸と矢印からなる図で木構造で表すことにします。

a

a

b
e

f

c

d

g

h
e

i

j

k

l

m

d

f

g

h

l

m

n

n

http://iconhoihoi.oops.jp/item/category/cat46/index_2.html
東京大学 数理・情報教育研究センター

c

b

i

j

k

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

40

木構造について••

木構造において用いる簡単な用語を説明します。
図の丸で表す部分を点と呼び、矢印を枝と呼びます。矢印が1本も入って来ない点を根と呼びます。下の例では点aが根です。ある点から出た矢印の先の点をその点の子と呼びます。下の例では点aの子
は点b,c,dの3つです。
a

c

d

f

g

h

l

m

n

b

e

i
東京大学 数理・情報教育研究センターjk4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

41

幅優先探索•木構造に対する探索は一般に、根から探索を開始し、根以外の点をどの様な順番で調べる（探索する）か、を定義します。幅優先探索は根から探索を開始し、根に近い点から順番に探索を行います。
• 同じ近さの点が2個以上存在する場合は、その中から自由に選んで構いません。

••

配列の探索では配列に格納されている値を探索しましたが、木探索では簡単のため、点の名前を探索するものとします。

1 a
2 b
5 e

4 d

3 c

6 f

g

i j k l9 10 11 12

m
13

7

h 8

n
14

この例では、
a,b,c,d,e,f,g,h,i,j,k,I,m,nの順で探索を行います（右図の赤字）。

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

42

幅優先探索•幅優先探索のアルゴリズムは次の様になります。
手順1：x を入力（探索する値＝点の名前を入力）

手順2：v を探索する木構造の根とする
手順3：v = x ならば、xを発見したと報告（出力）して終了する
手順4：今までに探索した点（vに代入されたことがある点）の子であり、かつまだ探索していない点が存在するなら、その中で一番根に近い点をvとして手順3に戻る （次に探索する点を決める）
手順5： xを発見できなかったと報告（出力）して終了する

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

43

幅優先探索のフローチャート•

幅優先探索のフローチャートです。

開始
x を入力

手順1：x を入力
手順2：v を探索する木構造の根とする
手順3：v = x ならば、xを発見したと報告（出力）して終了する
手順4：今までに探索した点（vに代入されたことがある点）の子であり、かつまだ探索していない点が存在するなら、その中で一番根に近い点をvとして手順3に戻る
手順5： xを発見できなかったと報告（出力）して終了する

東京大学 数理・情報教育研究センター

v を根とする
v=x?

Yes

No

探索済みの点の子であり、かつ未探索の点が存在する結果（発見）
を出力

No 結果（未発見）を出力

Yes
その中で一番根に近い点をvとする

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

終了

44

幅優先探索の計算量•

幅優先探索の計算量を評価してみましょう。探索する木構造の点の数をnとした場合、各手順の実行回数は以下の通りです。
• 手順1,2,5：1回• 手順3, 4：最大でn回•

つまり、合計すると最大で2n+3回手順を実行します。

•

よって、幅優先探索の計算量は最悪の場合、木構造の点の数である nに比例することが分かります。

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

45

深さ優先探索••

深さ優先探索は根から探索を開始し、できるだけ根から遠い点から順番に探索を行います。つまり、幅優先探索とはある意味逆の順番で探索を行います。
以下の例では、a,b,e,i,j,k,f,l,c,j,k,I,m,nの順で探索を行います（下図の
赤字）。
1 a
2 b

東京大学 数理・情報教育研究センター

9 c

3 e

7 f

g

i
4

k
6

m
11

j
5

l
8

14 d
10

h 13

n
12

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

46

深さ優先探索•

深さ優先探索のアルゴリズムは次の様になります。
手順1：x を入力（探索する値＝点の名前を入力）

手順2：v を探索する木構造の根とする
手順3：v = x ならば、xを発見したと報告（出力）して終了する
手順4：今までに探索した点（vに代入されたことがある点）の子であり、かつまだ探索していない点が存在するなら、その中で一番根から遠い点をvとして手順3に戻る （次に探索する点を決める）
手順5： xを発見できなかったと報告（出力）して終了する

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

47

深さ優先探索のフローチャート•

深さ先探索のフローチャートです。

開始
x を入力

手順1：x を入力
手順2：v を探索する木構造の根とする
手順3：v = x ならば、xを発見したと報告（出力）して終了する
手順4：今までに探索した点（vに代入されたことがある点）の子であり、かつまだ探索していない点が存在するなら、その中で一番根に近い点をvとして手順3に戻る
手順5： xを発見できなかったと報告（出力）して終了する

東京大学 数理・情報教育研究センター

v を根とする
v=x?

Yes

No

探索済みの点の子であり、かつ未探索の点が存在する結果（発見）
を出力

No 結果（未発見）を出力

Yes
その中で一番根から遠い点をvとする

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

終了

48

深さ優先探索の計算量••

深さ優先探索の計算量を評価してみましょう。定義やフローチャートなどからも分かりますが、探索の順番は全く違いますが、深さ優先探索と幅優先探索は非常によく似ており、計算量も同様です。
探索する木構造の点の数をnとした場合、各手順の実行回数は以下の通りです。
• 手順1,2,5：1回• 手順3, 4：最大でn回•

つまり、合計すると最大で2n+3回手順を実行します。

•

よって、深さ優先探索の計算量も最悪の場合には木構造の点の数である n に比例することが分かります。

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

49

並べ替えのアルゴリズム•

並べ替え（ソート, sort）は、数を小さい順（昇順）に並べる問題です。
• 大きい順（降順）に並べたり、それ以外の順序で並べたりする場
合もあります。数の代わりに文字列を並べる場合もあります。

•

並べ替えの対象となる数は配列に格納されているものとします。

並べ替え前の配列

8

6

10 0

5

並べ替えを実行
並べ替え後の配列

東京大学 数理・情報教育研究センター

0

5

6

8

10

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

50

並べ替えのアルゴリズム•

並べ替えを解くアルゴリズムには様々なアルゴリズムがあります。
並べ替えを行うことが問題の目的ですので、得られる結果は同じですが、手順や効率（計算量の大きさ）が異なります。
• 並べ替えのアルゴリズムは、二分探索の実行前に配列の値を並べ替えたり、コンピュータでCGを描画する際に描くべきものの順に並べたりと様々な場面で使われています。

•

本教材では、以下の代表的な並べ替えアルゴリズム（ソートアルゴ
リズム）を説明します。
• バブルソート（交換法）• 選択ソート• 挿入ソート

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

51

バブルソート•

バブルソート（交換法）では、配列の先頭から順に、隣り合う2つの数の大小を比較し、その大小が目的の順序（昇順）になっていな
い場合、その2つの数の順序を入れ替える、という手続きをまず行います。例えば、以下の図の通りです。

8

6

10 0

5

1番目(8)と2番目(6)を比較

6

8

10 0

5

2番目(6)の方が小さいので入れ替え

6

8

10 0

5

2番目(8)と3番目(10)を比較

6

8

10 0

5

2番目(8)の方が小さいのでそのまま

6

8

10 0

5

3番目(10)と4番目(0)を比較

6

8

0

10 5

4番目(0)の方が小さいので入れ替え

6

8

0

10 5

4番目(10)と5番目(5)を比較

6

8

0

5

5番目(5)の方が小さいので入れ替え

東京大学 数理・情報教育研究センター

104-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

52

バブルソート•

前頁の手順を実行完了すると、並べ替えの対象となっている数の中で最大の数が配列の最後に格納されていることに注意して下さい。
• 例では、最大の数は10です。10は元は配列の3番目に格納されていましたが、先の手順完了後は配列の最後（5番目）に格納されています。
• 最大の値が泡（バブル, bubble）の様に浮かび上がって最後尾に移動するのでバブルソートという名前がついています。

8

6

10 0

5

大小関係の比較・入れ替え前

6

8

0

10

大小関係の比較・入れ替え後

東京大学 数理・情報教育研究センター

54-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

53

バブルソート•••

これは部分的に並べ替えが完了したとみなすことができます。
どういうことかと言うと、並べ替えは数を小さい順に並べる必要があります。つまり、「一番大きい数は配列の一番最後に格納したい」ということです。そして、先の比較・入れ替えの手順によって、配列の最後に最大の数が格納されています。
つまり、元は配列の先頭から最後まで全ての数を並べ替える必要がありましたが、今は先頭から最後から2番目までの数だけを並べ替えれば良くなっていると見なせるということです。
• 例では、元は配列の1番目から5番目まで並べ替えの必要があり、比較・入れ替えの実行後は、配列の1番目から4番目まで並べ替
えれば良くなっています。

8

6

10 0

5

1番目から5番目を並べ替えたい

6

8

0

10

1番目から4番目を並べ替えたい

東京大学 数理・情報教育研究センター

54-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

54

バブルソート••

そこで、再度、配列の先頭から順に、隣り合う2つの数の大小を比較・入れ替えを行っていきます。ただし、今度は、最後までではな
く、最後から2番目まで行う様にします。
例えば、以下の図の通りです。

6

8

0

5

10

1番目(6)と2番目(8)を比較

6

8

0

5

10

1番目(6)の方が小さいのでそのまま

6

8

0

5

10

2番目(8)と3番目(0)を比較

6

0

8

5

10

3番目(0)の方が小さいので入れ替え

6

0

8

5

10

3番目(8)と4番目(5)を比較

6

0

5

8

10

4番目(5)の方が小さいので入れ替え

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

55

バブルソート•

再度、比較・入れ替えの一連の手順を実行完了すると、並べ替えの対象となっている数（先頭から最後から2番目までの数）の中で最大の数が配列の最後から2番目に格納されることになります。
• 最後から2番目に格納された数は配列の中で2番目に大きい数です。
• 例では、先頭から最後から2番目までの数の中で最大の数（配列全体では2番目に大きい数）は8です。先の手順によって最後から2番目（先頭から4番目）に格納されています。

6

8

0

5

10

大小関係の比較・入れ替え前

6

0

5

8

10

大小関係の比較・入れ替え後

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

56

バブルソート•

以降、比較・入れ替えの範囲を徐々に狭めながら、一覧の比較・入れ替えを繰り返していくと並べ替えが完了します。

6

0

5

8

10

1番目(6)と2番目(0)を比較

0

6

5

8

10

2番目(0)の方が小さいので入れ替え

0

6

5

8

10

2番目(6)と3番目(5)を比較

0

5

6

8

10

3番目(5)の方が小さいので入れ替え

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

57

バブルソート•前のページの続きです。

0

5

6

8

10

3番目に大きい数(6)が最後から3番目に格納されている

0

5

6

8

10

1番目(0)と2番目(5)を比較

0

5

6

8

10

1番目(0)の方が小さいのでそのまま

10

4番目に大きい数(5)が最後から4番目、5番目に大きい数(0)が最後から5番目（先頭）に格納されている

05東京大学 数理・情報教育研究センター

684-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

58

バブルソート•

バブルソートのアルゴリズムは次の様になります。（配列の要素数をnとします）
手順1：j=1（ j番目の比較・入れ替え＝j番目に大きい数を求める）

手順2：i=1
手順3：i番目とi+1番目の数を比較し、i+1番目の方が小さい場合、i番目とi+1番目の数を入れ替える （i番目とi+1番目の比較・入れ替え）
手順4：iを1増加する
手順5：iがn-jより小さいなら手順3に戻る。そうでなければ、jを1増加する
手順6：jがnより小さいなら、手順2に戻る。そうでなければ、結果(配列）を出力してアルゴリズムを終了する

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

59

バブルソートのフローチャート•

開始

バブルソートのフローチャートです。

j に1を代入
手順1：j=1i に1を代入

手順2：i=1
手順3：i番目とi+1番目の数を比較し、i+1番目の方が小さい場合、i番目とi+1番目の数を入れ替える

i番目の数<
i+1番目の数?

Yes

手順4：iを1増加する

No

i番目の数とi+1番目の数を入れ替えるi を1増加手順5：iがn-jより小さいなら手順3に戻る。そうでなければ、jを1増加する
手順6：jがnより小さいなら、手順2に戻る。そうでなければ、結果(配列）を出力してアルゴリズムを
終了する

Yes

i<n-j?

No

j を1増加

Yes

j<n?

No

配列を出力
終了
東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

60

バブルソートの計算量•

バブルソートの計算量を評価してみましょう。並べ替える数の個数をnとした場合、各手順の実行回数は以下の通りです。
• 手順1：1回• 手順2：n-1回• 手順3,4,5：変数jの値がaのときn-a回であり、jは1からn-1までの場合が起こり得る。よって、合計で(n-1)+…+1=n(n-1)/2回• 手順6:n-1回•

つまり、合計すると約n2回手順を実行します。

•

よって、バブルソートの計算量は n2 に比例することが分かります。

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

61

選択ソート•••

選択ソートは、配列の中から最小の数を見つける→2番目に小さい数を見つける→3番目に小さい数を見つける→…を繰り返すことで昇順に数を並べ替えるアルゴリズムです。
ただし、見つけたi番目に小さい数は配列のi番目に移動させます。
そして、i+1番目に小さい数を見つけるときには、配列のi+1番目から最後までを探す様にします。そうすることで、1番目からi番目に小さい数が格納されている場所を探さない様にして、目的の数を見つけるのに費やす時間を短くしています。
例えば、以下の例ではi=3、すなわち、1から3番目に小さい数を配列の1から3番目にそれぞれ格納した状況です。

0•5

6 10 8

また、i+1番目に小さい数を見つける手順は、配列のi+1番目から最後までの値の中で最小の数を見つける手順に等しいことに注意して下さい。

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

62

選択ソート•

選択ソートの実行例を示します。

8

6

10 0

5

最小の数 (0) を見つける

0

6

10 8

5

配列の1番目の数 (8) と0を入れ替え

0 6

10 8

5

配列の2番目から最後までの中で最小の数 (5) を見つける

0 5

10 8

6

配列の2番目の数 (6) と5を入れ替え

6

配列の3番目から最後までの中で最小の数 (6) を見つける

05 10 8東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

63

選択ソート•

前の頁の続きです。

0

5

6 8

10

配列の3番目の数 (10) と6を入れ替え

0

5

6

8

10

配列の4番目から最後までの中で最小の数 (8) を見つける

0

5

6

8

10

配列の4番目の数 (8) と8を入れ替え（8は元から4番目なので何もしない）

0

5

6

8

10

最大の数 (10) は配列の最後にあるので何もしない東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

64

選択ソート•

選択ソートのアルゴリズムは次の様になります。 （配列の要素数をnとします）
手順1：j=1（j番目に小さい数を求める）

手順2：i=j+1, x=j （手順3から4において、配列のj番目から最後までの中から最小の数を探す。暫定の最小の数は配列のx番目に格納されている）
手順3：配列のi番目の数をx番目の数と比較し、i番目の数の方が小さい場
合、xにiを代入する （暫定の最小の数の格納場所xを更新する）
手順4：iを1増加する
手順5：iがn+1より小さい場合、手順3に戻る。そうでなければ、配列のx番目の数とj番目の数を入れ替えて、jを1増加する （配列のj番目にj番目に小さい数を移動させる。その数は配列のx番目に格納されている）
手順6：jがnより小さい場合、手順2に戻る。そうでなければ結果(配列）を出力してアルゴリズムを終了する
東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

65

選択ソートのフローチャート•

開始

選択ソートのフローチャートです。

j に1を代入
手順1：j=1

i にi+1, x に j を代入

手順2：i=j+1, x=j
手順3：配列のi番目の数をx番目の数と比較し、i番目の数の方が小さい場合、xにiを代入する

i番目の数<
x番目の数?

Yes

x に i を代入

No

手順4：iを1増加する

i を1増加手順5：iがn+1より小さい場合、手順3に戻る。そうでなければ、配列のx番目の数とj番目の数を入れ替えて、jを1増加する
手順6：jがnより小さい場合、手順2に戻る。そうでなければ結果(配列）を出力してアルゴリズム
を終了する

Yes

i<n+1?

No

x 番目と j 番目の数を入れ替え、j を1増加

Yes

j<n?

No

配列を出力
終了

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

66

選択ソートの計算量•

選択ソートの計算量を評価してみましょう。並べ替える数の個数をnとした場合、各手順の実行回数は以下の通りです。
• 手順1：1回• 手順2,6：n-1回• 手順3,4,5：変数jの値がaのときn-a回であり、jは1からn-1まで増加する。よって、合計で(n-1)+…+1=n(n-1)/2回•

つまり、合計すると約n2回手順を実行します。

•

よって、選択ソートの計算量は n2 に比例することが分かります。

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

67

挿入ソート•••

挿入ソートは、並べ替え済みの配列の適切な位置に、新しい数を挿入することで数を並べ替えるアルゴリズムです。
具体的には、配列の1番目からj番目の数が並べ替え済みである状態
で、配列のj+1番目の数を配列の1番目からj+1番目の適切な位置（x番目としましょう）に移動させます。このとき、x番目からj番目の数はそれぞれx+1番目からj+1番目に移動させます。
例えば、以下の例はj=3、すなわち、配列の1,2,3番目は並べ替え済
みです。そして、4番目の値 (6) を適切な位置に移動させます。この場合は、1番目の値 (5) と2番目の間 (8) に移動するのが適切です。
よって、x=2、すなわち、2番目と3番目の値を3番目と4番目にそれぞれスライドさせます。

5
•

8

10 6

0

5

6

8 10 0

もう少し具体例を見てみましょう。

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

68

挿入ソート•

挿入ソートの実行例を示します。

8

6

10 0

5

配列の1番目の数 (8) は並べ替え済みと
みなす

8

6

10 0

5

配列の2番目の数 (6) を並べ替え済みの配列（青い部分）に挿入したい

6 8

10 0

5

6は配列の1番目の数 (8) より小さいので8の前に挿入（8を1つ後ろにずらす）

6 8

10 0

5

配列の3番目の数 (10) を挿入したい

8 10 0510は配列の2番目の数 (8) より大きいので8の後ろに挿入6

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

69

挿入ソート•

前の頁の続きです。

8

10 0

0

6

8

10 5

0は配列の1番目の数 (5) より小さいので6の前に挿入（6,8,10を1つ後ろにずらす）

0

6

8

10 5

配列の5番目の数 (5) を挿入したい

0

5

6

8

5は配列の1番目の数 (0) より大きく、2番目の数 (6) より小さい6の前に挿入（6,8,10を1つ後ろにずらす）

東京大学 数理・情報教育研究センター

5

配列の4番目の数 (0) を挿入したい

6

10

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

70

挿入ソート•

挿入ソートのアルゴリズムは次の様になります。 （配列の要素数をnとします）

手順1：j=2
入したい）（配列の1番目からj-1番目が並べ替え済み、j番目の値を挿手順2：i=j-1, y=j番目の値
探す）（j-1番目から1番目の中で適切な挿入位置を手順3：配列のi番目の数とyを比較し、yの方が大きい場合、手順6へ。そうでなければ、i番目の数をi+1番目に代入する （適切な挿入位置が見つかったら手順6を実行する。そうでなければ、i番目の数を後ろにずらす）
手順4：iを1減少する
手順5：iが0より大きい場合、手順3へ戻る（iが0だと、yを1番目に挿入）
手順6：配列のi+1番目にyを代入する。jを1増加する（適切な位置に挿入）
手順7：jがn+1より小さい場合、手順2に戻る。そうでなければ結果(配列）を出力してアルゴリズムを終了する
東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

71

挿入ソートのフローチャート•

開始

挿入ソートのフローチャートです。

j に2を代入

手順1：j=2
手順2：i=j-1, y=j番目の値

i にj-1, y に j 番目の数を代入

手順3：配列のi番目の数とyを比較し、yの方が大きい場合、手順6へ。そうでなければ、i番目の数
をi+1番目に代入する

i番目の数<y?

No

手順4：iを1減少する
手順5：iが0より大きい場合、手順3へ戻る

i番目の値をi+1番目に代入し、i を1減少

No

手順6：配列のi+1番目にyを代入する。jを1増加する
手順7：jがn+1より小さい場合、手順2に戻る。そうでなければ結果(配列）を出力してアルゴリズ
ムを終了する

Yes

i=0?

Yes

i+1番目にyを代入し、jを1増加

Yes

j<n+1?

No

配列を出力
終了

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

72

挿入ソートの計算量•

挿入ソートの計算量を評価してみましょう。並べ替える数の個数をnとした場合、各手順の実行回数は以下の通りです。
• 手順1：1回• 手順2,6,7：n-1回• 手順3,4,5：変数jの値がaのとき最大でa-1回（最小で1回）であり、jは2からnまで増加する。よって、合計で 最大で1+…+(n-1)=n(n1)/2回•

つまり、合計すると約n2回手順を実行します。

•

よって、挿入ソートの計算量は最大で n2 に比例することが分かります。
• ただし、手順3,4,5は各 j に対して最小のとき（例えば、最初から配列が並べ替え完了している様な場合）は 1 回ずつしか実行されませんので、この場合は計算量は n に比例します。

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

73

より高速な並べ替えのアルゴリズム••

今まで見てきたバブルソート・選択ソート・挿入ソートの計算量は（最大で） n2 に比例していましたが、これらより高速な（計算量の少ない）アルゴリズムが開発されています。
例えば、クイックソート、マージソート、ヒープソートという様なアルゴリズムの計算量は概ね n log2n に比例することが知られています。

東京大学 数理・情報教育研究センター

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

74

より高速な並べ替えのアルゴリズム•

最後に、バブルソートなど(O(n2)) とクイックソートなど(O(n log2n))の計算量を比較してみましょう。クイックソートの方が高速であることが分かりますね。

計 9000算
量 8000
7000
6000
5000
4000
3000
2000
1000

0

2

東京大学 数理・情報教育研究センター

10

20

30

40
O(n2)

50
O(n log2n)60

70

4-4. 時系列データの解析
東京大学 数理・情報教育研究センター
小林浩二 2021 CC BY-NC-SA

80

90

n
75