アルゴリズムとデータ構造 --- 理論編 --- 山本 真基

Presentation on theme: "アルゴリズムとデータ構造 --- 理論編 --- 山本 真基"— Presentation transcript:

1 アルゴリズムとデータ構造 --- 理論編 --- 山本 真基
バブルソート アルゴリズムとデータ構造 理論編 --- 山本　真基

2 バブルソート --- アルゴリズムの説明 ---
入力： 5, 7, 2, 9, 5, 0, 3 出力： 0, 2, 3, 5, 5, 7, 9

3 バブルソート --- アルゴリズムの説明 ---
入力された数の列 入力： 5, 7, 2, 9, 5, 0, 3 出力： 0, 2, 3, 5, 5, 7, 9 目標 2 9 5 3 7

4 バブルソート --- アルゴリズムの説明 ---
入力：　5, 7, 2, 9, 5, 0, 3 出力：　0, 2, 3, 5, 5, 7, 9 動作が分かりやすいようコピーしておく 2 9 5 3 7 5 7 2 9 5 3

5 バブルソート --- アルゴリズムの説明 ---
入力：　5, 7, 2, 9, 5, 0, 3 出力：　0, 2, 3, 5, 5, 7, 9 下段に注目 5 7 2 9 5 3 5 7 2 9 5 3

6 バブルソート --- アルゴリズムの説明 ---
入力：　5, 7, 2, 9, 5, 0, 3 出力：　0, 2, 3, 5, 5, 7, 9 １番目と２番目に着目 5 7 2 9 5 3 5 7 2 9 5 3

7 バブルソート --- アルゴリズムの説明 ---
入力：　5, 7, 2, 9, 5, 0, 3 出力：　0, 2, 3, 5, 5, 7, 9 左が大きいなら交換 5 7 2 9 5 3 5 7 2 9 5 3

8 バブルソート --- アルゴリズムの説明 ---
入力：　5, 7, 2, 9, 5, 0, 3 出力：　0, 2, 3, 5, 5, 7, 9 そうでないので 　　　　　交換しない 5 7 2 9 5 3 5 7 2 9 5 3

9 バブルソート --- アルゴリズムの説明 ---
入力：　5, 7, 2, 9, 5, 0, 3 出力：　0, 2, 3, 5, 5, 7, 9 ２番目と３番目に着目 5 7 2 9 5 3 5 7 2 9 5 3

10 バブルソート --- アルゴリズムの説明 ---
入力：　5, 7, 2, 9, 5, 0, 3 出力：　0, 2, 3, 5, 5, 7, 9 左が大きいなら交換 5 7 2 9 5 3 5 2 7 7 2 9 5 3

11 バブルソート --- アルゴリズムの説明 ---
入力：　5, 7, 2, 9, 5, 0, 3 出力：　0, 2, 3, 5, 5, 7, 9 ３番目と４番目に着目 5 7 2 9 5 3 5 2 7 9 5 3

12 バブルソート --- アルゴリズムの説明 ---
入力：　5, 7, 2, 9, 5, 0, 3 出力：　0, 2, 3, 5, 5, 7, 9 左が大きいなら交換 5 7 2 9 5 3 5 2 7 9 5 3

13 バブルソート --- アルゴリズムの説明 ---
入力：　5, 7, 2, 9, 5, 0, 3 出力：　0, 2, 3, 5, 5, 7, 9 そうでないので 　　　　　交換しない 5 7 2 9 5 3 5 2 7 9 5 3

14 バブルソート --- アルゴリズムの説明 ---
入力： 5, 7, 2, 9, 5, 0, 3 出力： 0, 2, 3, 5, 5, 7, 9 ４番目と５番目に着目 5 7 2 9 5 3 5 2 7 9 5 3

15 バブルソート --- アルゴリズムの説明 ---
入力： 5, 7, 2, 9, 5, 0, 3 出力： 0, 2, 3, 5, 5, 7, 9 左が大きいので交換 5 7 2 9 5 3 5 2 7 9 5 3

16 バブルソート --- アルゴリズムの説明 ---
入力： 5, 7, 2, 9, 5, 0, 3 出力： 0, 2, 3, 5, 5, 7, 9 左が大きいので交換 5 7 2 9 5 3 5 2 7 5 9 3

17 バブルソート --- アルゴリズムの説明 ---
入力： 5, 7, 2, 9, 5, 0, 3 出力： 0, 2, 3, 5, 5, 7, 9 ５番目と６番目に着目 5 7 2 9 5 3 5 2 7 5 9 3

18 バブルソート --- アルゴリズムの説明 ---
入力： 5, 7, 2, 9, 5, 0, 3 出力： 0, 2, 3, 5, 5, 7, 9 左が大きいので交換 5 7 2 9 5 3 5 2 7 5 9 3

19 バブルソート --- アルゴリズムの説明 ---
入力： 5, 7, 2, 9, 5, 0, 3 出力： 0, 2, 3, 5, 5, 7, 9 左が大きいので交換 5 7 2 9 5 3 5 2 7 5 9 3

20 バブルソート --- アルゴリズムの説明 ---
入力： 5, 7, 2, 9, 5, 0, 3 出力： 0, 2, 3, 5, 5, 7, 9 ６番目と７番目に着目 5 7 2 9 5 3 5 2 7 5 9 3

21 バブルソート --- アルゴリズムの説明 ---
入力： 5, 7, 2, 9, 5, 0, 3 出力： 0, 2, 3, 5, 5, 7, 9 左が大きいので交換 5 7 2 9 5 3 5 2 7 5 9 3

22 バブルソート --- アルゴリズムの説明 ---
入力： 5, 7, 2, 9, 5, 0, 3 出力： 0, 2, 3, 5, 5, 7, 9 左が大きいので交換 5 7 2 9 5 3 5 2 7 5 3 9

23 バブルソート --- アルゴリズムの説明 ---
入力： 5, 7, 2, 9, 5, 0, 3 出力： 0, 2, 3, 5, 5, 7, 9 ここまでの動作で， 　　　何か起きたのか？ 5 7 2 9 5 3 最大の９が最右に移動 5 2 7 5 3 9

24 バブルソート --- アルゴリズムの説明 ---
入力： 5, 7, 2, 9, 5, 0, 3 出力： 0, 2, 3, 5, 5, 7, 9 最大である数字９の 位置が確定 5 7 2 9 5 3 最大の９が最右に移動 5 2 7 5 3 9

25 バブルソート --- アルゴリズムの説明 ---
入力： 5, 7, 2, 9, 5, 0, 3 出力： 0, 2, 3, 5, 5, 7, 9 下段を利用 5 7 2 9 5 3 7 5 3 9 2 7 5 3 9 2

26 バブルソート --- アルゴリズムの説明 ---
入力：　5, 7, 2, 9, 5, 0, 3 出力：　0, 2, 3, 5, 5, 7, 9 第２ラウンド目 7 5 3 9 2 7 5 3 9 2

27 バブルソート --- アルゴリズムの説明 ---
入力：　5, 7, 2, 9, 5, 0, 3 出力：　0, 2, 3, 5, 5, 7, 9 １番目と２番目に着目 7 5 3 9 2 7 5 3 9 2

28 バブルソート --- アルゴリズムの説明 ---
入力：　5, 7, 2, 9, 5, 0, 3 出力：　0, 2, 3, 5, 5, 7, 9 左が大きいので交換 7 5 3 9 2 7 5 3 9 2

29 バブルソート --- アルゴリズムの説明 ---
入力：　5, 7, 2, 9, 5, 0, 3 出力：　0, 2, 3, 5, 5, 7, 9 左が大きいので交換 7 5 3 9 2 2 5 7 5 3 9

30 バブルソート --- アルゴリズムの説明 ---
入力：　5, 7, 2, 9, 5, 0, 3 出力：　0, 2, 3, 5, 5, 7, 9 同様の操作を繰り返す 7 5 3 9 2 7 5 3 9 2

31 バブルソート --- アルゴリズムの説明 ---
入力：　5, 7, 2, 9, 5, 0, 3 出力：　0, 2, 3, 5, 5, 7, 9 第２ラウンド終了 7 5 3 9 2 5 3 7 9 2

32 バブルソート --- アルゴリズムの説明 ---
入力：　5, 7, 2, 9, 5, 0, 3 出力：　0, 2, 3, 5, 5, 7, 9 第２ラウンドで 　　　何が起きたのか？ 5 2 7 5 3 9 ２番目に大きい７が右から２番目に移動 2 5 5 3 7 9

33 バブルソート --- アルゴリズムの説明 ---
入力：　5, 7, 2, 9, 5, 0, 3 出力：　0, 2, 3, 5, 5, 7, 9 ２番目に大きい数字７の位置が確定 5 2 7 5 3 9 ２番目に大きい７が右から２番目に移動 2 5 5 3 7 9

34 バブルソート --- アルゴリズムの説明 ---
入力：　5, 7, 2, 9, 5, 0, 3 出力：　0, 2, 3, 5, 5, 7, 9 以降，同様の操作を 繰り返す 5 2 7 5 3 9 5 3 7 9 2

35 バブルソート --- アルゴリズムの説明 ---
入力：　5, 7, 2, 9, 5, 0, 3 出力：　0, 2, 3, 5, 5, 7, 9 第３ラウンド終了 3 5 7 9 2

36 バブルソート --- アルゴリズムの説明 ---
入力：　5, 7, 2, 9, 5, 0, 3 出力：　0, 2, 3, 5, 5, 7, 9 第４ラウンド終了 3 5 7 9 2

37 バブルソート --- アルゴリズムの説明 ---
入力：　5, 7, 2, 9, 5, 0, 3 出力：　0, 2, 3, 5, 5, 7, 9 第５ラウンド終了 3 5 7 9 2

38 バブルソート --- アルゴリズムの説明 ---
入力：　5, 7, 2, 9, 5, 0, 3 出力：　0, 2, 3, 5, 5, 7, 9 第６ラウンド終了 3 5 7 9 2

39 バブルソート --- アルゴリズムの説明 ---
入力：　5, 7, 2, 9, 5, 0, 3 出力：　0, 2, 3, 5, 5, 7, 9 第７ラウンド終了 3 5 7 9 2

40 バブルソート --- アルゴリズムの説明 ---
入力：　5, 7, 2, 9, 5, 0, 3 出力：　0, 2, 3, 5, 5, 7, 9 第７ラウンド終了 3 5 7 9 2 ソーティング完了！

41 2 3 5 5 7 9 バブルソート：考察 ７ ６ ５ ４ ３ ２ １ 各ラウンドで一つの 入力： 5, 7, 2, 9, 5, 0, 3
入力：　5, 7, 2, 9, 5, 0, 3 出力：　0, 2, 3, 5, 5, 7, 9 各ラウンドで一つの 　　数字の位置が確定 2 3 5 5 7 9 ７ ６ ５ ４ ３ ２ １