【基本情報技術者試験】ソートアルゴリズムをPythonで実装する
基本情報技術者試験でも出題されるアルゴリズムについて、実際に手を動かすことでより理解に繋がると思うので、Pythonで実装してみたいと思います！
ソートアルゴリズムについて大体理解できたが更に理解を深めたい方、自分で手を動かして確認してみたい方は下記を参考に試してみてください。
Pythonを選んだ理由は簡単に環境構築ができ、実行結果も簡単に確認できるためです。
ここではcolabを使って確認していきます。colabの使い方についてはリンク先を参照してください。
ソートアルゴリズムとは？
ソートアルゴリズムとはランダムに並んだ数列や文字列を昇順や降順に並べ替えるアルゴリズムのことです。（例えば4, 2, 3, 1という数列を1, 2, 3, 4のように並べ替える）
ソートアルゴリズムは様々なものがありますが、本ブログでは基本情報技術者試験で出題される下記アルゴリズムの実装を行います。その中でも本記事ではバブルソートを扱います。
- 基本交換法（バブルソート）←今回の対象
- 基本選択法（選択ソート）
- 基本挿入法（挿入ソート）
- シェルソート
- クイックソート
- マージソート
- ヒープソート
バブルソート
バブルソートとは隣り合わせの値の大小を比較して並べ替えるアルゴリズムです。基本交換法とも呼ばれます。
１番目と２番目の要素を比較し順番が逆の場合は入替、次に２番目と３番目の要素を比較、入替というような形で繰り返していきます。すると後ろの要素から順にソートされていきます。例えば4, 2, 5, 3, 1という数列があったときに下記のように更新していきます。（赤字部分が固定箇所になります。）
① 2, 4, 3, 1, 5 （4>2のため交換、4<5のためそのまま、5>3のため交換、5>1のため交換）
② 2, 3, 1, 4, 5 （2<4のためそのまま、4>3のため交換、4>1のため交換）
③ 2, 1, 3, 4, 5 （2>3のためそのまま、3>1のため交換）
④ 1, 2, 3, 4, 5 （2>1のため交換）
実際のPythonで書いたコードは下記になります。
listNum = [4, 2, 5, 3, 1]
listNum[4, 2, 5, 3, 1]
lenNum = len(listNum)
for i in range(lenNum):
for j in range(1, lenNum - i):
if listNum[j - 1] > listNum[j]:
listNum[j - 1], listNum[j] = listNum[j], listNum[j - 1]
listNum[1, 2, 3, 4, 5]
バブルソートでのソート方法は以上となります。
次回は選択ソートをPythonで実装します。
コメント