バブルソート
ソートとは、並べ替えを意味する英単語だ。バブルソートとは、その名の通り、並べ替えたい数値が移動している様子が泡のように浮かび上がってくることから、その名前が付けられた。 例えば、リストaがあり、[24,17,16,18]が入っていたとしよう。
この配列の中身を、小さい順に並べ替える方法を考える。
今回は、その中の1つの考え方であるバブルソートについて解説する。
https://gyazo.com/789860a837b098a91c08c8f089aec338
画像は最新情報の科学P.88より引用
この作業には、大きな繰り返しと、小さな繰り返しがある。
大きな繰り返しの中に、小さな繰り返しが入っている。
上の図を参考にしながら、順番にみていこう。
バブルソートは隣同士を比べて、比べた2つの数値のうち小さい方を左側に移動する作業を繰り返すアルゴリズムだ。
24と17を比べる。17の方が小さいので、並べ替える。
24と16を比べる。16の方が小さいので、並べ替える。
24と18を比べる。18の方が小さいので、並べ替える。
ここで、大きな繰り返しの1回目と、小さい繰り返しの3回目(最後)が終わった。
ここまでやると、4つの中で最大の数値24が一番右側に来たので、24と他の数値は比べなくても良い。
従って、大きな繰り返しの2回目では、小さい繰り返しは2回繰り返せば良い。
17と16を比べる。16の方が小さいので、並べ替える。
17と18を比べる。18の方が大きいので、そのまま。
ここで、大きな繰り返しの2回目と、小さい繰り返しの2回目(最後)が終わった。
24の次に大きな数値18が24の左に来たので、18と24は他の数値と比べなくても良い。
従って、大きな繰り返し3回目では、小さい繰り返しは1回だけで良い。
16と17を比べる。17の方が大きいので、そのまま。
ここで、大きな繰り返しの3回目と、小さい繰り返し1回が終わった。
17が18の左にあるので、17と18と24は他の数値と比べなくても良い。
終わり。ここまで繰り返したら、小さい順番に並べ変わっている。
さぁ、このプログラムを組んでみよう。
kadai15
バブルソートを行い、a [24,17,16,18]を小さい順に並べ替えるプログラムを作成せよ
code:ヒント
for i in range(●●●):←ここはrange関数のページを参考にすること
for j in range(●●●):←ここはrange関数のページを参考にすること
if ●●●●●●●●●●(この部分を自分で考える):
並べ替える(この部分を自分で考える)
print(list)