はじめに
今までに大学の講義や自主学習でアルゴリズムとデータ構造については勉強してきた。
そのため、忘れている内容や新たに知り得た内容について説明していく。
アルゴリズムとデータ構造
例えば、車を作ることを考えてみよう。
タイヤやドア、エンジンなど様々な部品があり、これらを順に組み合わせて一つの車が出来上がる。
ここで、車を作るときの部品や材料がプログラムでいうデータ、組み立てる手順がアルゴリズムにあたる。
また、部品や材料はばらばらに管理するとよくわからなくなるため、カテゴリーごとに分けて管理したほうがいい。
この部品や材料の管理の仕方、つまりデータの扱い方をデータ構造という。
アルゴリズムの基本
順次処理・分岐処理・繰り返し処理これら 3 つのの組み合わせでプログラミングすることを構造化プログラミングという。
アルゴリズムであるには正当性と停止性という 2 つの条件をクリアしている必要がある。
主要なデータ構造
- 配列
- リスト（単方向リスト・循環リスト・双方向リスト）
- 連想記憶（ハッシュテーブル・辞書・Map）
- スタック（LIFO）とキュー（FIFO）
- ツリー構造
- ヒープ構造
主要なアルゴリズム
ユークリッドの互除法
2 つの数の最大公約数を求めるアルゴリズム。
- 大きい方の数 M を小さい方の数 N で割ってその余り D を求める。
- D が 0 なら N が最大公約数になる。
- D が 0 でないなら、M を N として、N を D として 1 と 2 の処理を繰り返す。
エストラテネスのふるい
ある自然数までの素数をすべて求めるアルゴリズム。
N = 100
primeNumbers = list(range(2, N))
index = 0
while index < len(primeNumbers):
n = primeNumbers[index]
for i in range(n * 2, max(primeNumbers), n):
if i in primeNumbers:
primeNumbers.remove(i)
index += 1
print(primeNumbers)
リニアサーチとバイナリサーチ
リニアサーチは実装は簡単であるが、データ数が増えると処理時間が長くなる。
target = 3
list = [1, 10, 5, 4, 2, 7, 3, 9, 6, 8]
# リニアサーチ
for i, num in enumerate(list):
if num == target:
print(str(i) + '場目に発見！')
break
バイナリサーリは処理時間が短いが、リストはソートされている必要がある。
# バイナリサーチ
low = 0
high = len(list)
list = sorted(list)
while (low != high):
center = (low + high) // 2
if list[center] < target:
low = center + 1
elif list[center] > target:
high = center - 1
else:
print(str(center + 1) + '番目に発見！')
break
バブルソート
右から左に向かって、隣り合う２つの数字を比較して交換する操作を繰り返してソートする。
実装は容易であるが、計算量が O(n2) で処時間が長い。
list = [5, 9, 3, 1, 2, 8, 4, 7, 6]
print(list)
for i in range(len(list) - 2):
for j in range(len(list) -1, i, -1):
if list[j] < list[j - 1]:
list[j - 1], list[j] = list[j], list[j - 1]
print(list)
選択ソート
リストの中から最大値（最小値）を検索し、左端の値と交換する操作を繰り返してソートする。
計算量はバブルソートと同じく O(n2) 。
list = [5, 9, 3, 1, 2, 8, 4, 7, 6]
print(list)
for i in range(len(list)):
mi = list[i:].index(min(list[i:]))
list[i], list[i + mi] = list[i + mi], list[i]
print(list)
挿入ソート
ソート済みのリストに新たな数字を適切な位置に挿入していくことでソートする。
計算量はバブルソートや選択ソートと同じく O(n2) 。
list = [5, 9, 3, 1, 2, 8, 4, 7, 6]
print(list)
for right in range(1, len(list)):
left = right
while left > 0 and list[left] < list[left - 1]:
list[left], list[left - 1] = list[left - 1], list[left]
left -= 1
print(list)
シェルソート
シェルソートは挿入ソートを改良したアルゴリズムで、隣り合う数字を比較するのではなく h ずつ離れた数字を比較する。
h ずつ離れた数字のリストに対して挿入ソートでソートする。
次に h を小さくしていき、同じ処理を繰り返すことでリスト全体をソートする。
list = [5, 9, 3, 1, 2, 8, 4, 7, 6]
print(list)
h = len(list) // 2
while h > 0:
for right in range(h, len(list)):
left = right
while left >= h and list[left] < list[left - h]:
list[left], list[left - h] = list[left - h], list[left]
left -= h
h = h // 2
print(list)
バケツソート・分布数え上げソート
あらかじめデータが取りうる値の範囲がわかっている場合に有効なソート手法。
取りうる全ての値に対応した空のバケツを順番に並べたリストを作っておき、ソートしたい値を対応したバケツに入れていく。
最後に空のバケツ以外のバケツの値を順番に取り出せばソートされる。
バケツソートではバケツに値を入れるが、分布数え上げソートでは値の出現回数を入れる点が異なる。
大量のメモリが必要になるという問題がある。
list = [5, 9, 3, 1, 2, 8, 4, 7, 6]
print(list)
bucket = [0 for i in range(10)]
for num in list:
bucket[num] += 1
i = 0
for index, num in enumerate(bucket):
if num != 0:
for cnt in range(num):
list[i] = index
i += 1
print(list)
おわりに
自分が選んだまたは実装したアルゴリズムが正しくても適切とは限らない。
最低限のメモリ使用で、最速の処理速度で実行できるアルゴリズムがすばらしい。
参考資料
- 1週間で身につくアルゴリズムとデータ構造
- 石田保輝・宮崎修一（2017）「アルゴリズム図鑑」 翔泳社．