【アルゴリズム解説】「アルゴリズム探求」簡単解説‼【①ソート】

こんにちはヤク学長です。
データサイエンティスト兼ファーマシストで、アルゴリズムやBI開発を行っています。

本記事の目的は、「アルゴリズムの基本を知る」ことを目的としています。

【本記事のもくじ】

下記の方法で、簡単に概要を抑えることができます。

• １．アルゴリズムとは
• ２．ソート
• ３．バイナリサーチ

それでは、上から順番に見ていきます。
なお、本上記の方法を順番に抑えれば成果が出ます。

記事の内容は「転載 & 引用OK」問題ありません。

１．アルゴリズムとは

アルゴリズムとは

アルゴリズムとは、計算機科学や数学において、特定の問題を解決するために設計された手順や規則のことを指します。アルゴリズムは、入力を取り、それを処理して出力を生成する計算手順の一連のステップから構成されます。

アルゴリズムは、コンピュータプログラムやソフトウェアアプリケーションの中核となるものであり、例えば、ソートや検索、データ圧縮、暗号化、グラフ理論、機械学習、人工知能などの分野で広く使用されています。

アルゴリズムは、特定の問題を解決するために設計されるため、最適なアルゴリズムは問題によって異なります。アルゴリズムの性能は、入力サイズに対してどの程度効率的に動作するかによって測定され、一般的に、時間計算量や空間計算量などの指標が使用されます。

実際の現場ではどう使われる？

実際の現場では、アルゴリズムは多くの場面で活用されています。以下にいくつかの例を挙げます。

• ソフトウェア開発：プログラムの中核となるアルゴリズムを設計し、実装することによって、ソフトウェアの機能やパフォーマンスを向上させることができます。
• データサイエンス：機械学習やデータマイニングにおいて、アルゴリズムはデータの分析や予測に不可欠な役割を果たしています。
• ネットワーク設計：ルーティングや通信プロトコルなど、ネットワークの設計や最適化にアルゴリズムが活用されています。
• 組合せ最適化：組合せ最適化は、複数の要素から最適な組み合わせを見つけ出すことを目的とした分野であり、多くの場面でアルゴリズムが活用されています。
• 量子コンピュータ：量子アルゴリズムは、量子コンピュータに特化したアルゴリズムであり、高速に素因数分解や最適化問題を解決することができます。

アルゴリズムは、様々な分野で広く活用されており、技術の進歩によってますます重要性が高まっています。

Big O Notation

Big O Notation（ビッグ・オー記法）は、アルゴリズムの実行時間や空間利用量を表すために使用される記法です。アルゴリズムの性能を評価するために使用されます。

Big O Notationは、アルゴリズムの実行時間または空間利用量を、問題の入力サイズに対する上限として表します。例えば、n個のデータを処理するアルゴリズムの実行時間がO(n)である場合、nが大きくなるにつれて、アルゴリズムの実行時間はnに比例して増加することを示しています。また、O(1)であれば、入力サイズに関係なく一定の実行時間を持つことを示しています。

以下に、ビッグ・オー記法の表記方法の例を示します。

• O(1)：アルゴリズムの実行時間が一定で、問題の入力サイズに依存しない場合に使用されます。
• O(log n)：アルゴリズムの実行時間が、入力サイズの対数関数に比例する場合に使用されます。例えば、バイナリサーチアルゴリズムはO(log n)で実行されます。
• O(n)：アルゴリズムの実行時間が、入力サイズに比例する場合に使用されます。例えば、線形探索アルゴリズムはO(n)で実行されます。
• O(n log n)：アルゴリズムの実行時間が、入力サイズとその対数関数の積に比例する場合に使用されます。例えば、マージソートアルゴリズムはO(n log n)で実行されます。
• O(n^2)：アルゴリズムの実行時間が、入力サイズの二乗に比例する場合に使用されます。例えば、バブルソートアルゴリズムはO(n^2)で実行されます。

ビッグ・オー記法は、アルゴリズムの実行時間や空間利用量を評価するために非常に重要なツールであり、アルゴリズムの選択や設計に役立ちます。しかし、ビッグ・オー記法は、アルゴリズムの全体的なパフォーマンスを評価するための指標であり、実際の実行時間や空間利用量とは異なる場合があります。

安定ソート：stable sort と unstable sort

安定ソート（stable sort）とは、ソートアルゴリズムにおいて、同一の値を持つ複数の要素の間の相対的な順序が、ソート前とソート後で変わらないことを保証するソートアルゴリズムのことを指します。逆に、安定ソートでないソートアルゴリズムを不安定ソート（unstable sort）と呼びます。

たとえば、以下のようなデータがあったとします。

[5a, 2, 4, 5b, 1]

ここで、5aと5bは同じ値を表す要素であり、相対的な順序を保つ必要があります。安定ソートを行った場合は、ソート後も5aと5bの間の相対的な順序が変わりません。

一方、不安定ソートを行った場合は、ソートの途中で5aと5bの間の相対的な順序が変わることがあります。たとえば、クイックソートは不安定ソートの一例です。以下の例を見てみましょう。

[5a, 2, 4, 5b, 1]

このデータをクイックソートでソートする場合、最初にpivotとして選ばれた値が5aである場合、以下のようにソートされます。

[2, 4, 1, 5a, 5b]

このソート結果では、5aと5bの間の相対的な順序が変わっています。同様に、5bをpivotとして選んだ場合にも5aと5bの間の相対的な順序が変わることがあります。

安定ソートの例としては、マージソート、バブルソート、挿入ソートなどがあります。不安定ソートの例としては、クイックソート、ヒープソート、選択ソートなどがあります。安定ソートの利点は、同一の値を持つ要素の順序が維持されるため、より精度の高いソート結果を得ることができることです。

２．ソート

重要なものは題目を赤文字で記載していますので、時間がない方はサクッとご覧ください。

bogoソート

bogoソートは、ランダムな順列から始めて、正しい順序になるまで要素をランダムに入れ替えながらソートを行うアルゴリズムです。ランダムに入れ替える操作を繰り返すため、実行時間が非常に長くなることがあります。最悪の場合、実行時間は無限にかかる可能性もあるため、実用的なソートアルゴリズムとは言えません。

Pythonでのbogoソートの実装例を示します。

import random

def is_sorted(lst):
"""
リストがソートされているかどうかを判定する関数
"""
for i in range(len(lst) - 1):
if lst[i] > lst[i + 1]:
return False
return True

def bogo_sort(lst):
"""
bogoソートを実行する関数
"""
while not is_sorted(lst):
random.shuffle(lst)
return lst

# 実行例
lst = [5, 2, 4, 6, 1, 3]
sorted_lst = bogo_sort(lst)
print(sorted_lst)

def bubble_sort(lst):
"""
bubbleソートを実行する関数
"""
n = len(lst)
for i in range(n - 1):
for j in range(n - i - 1):
if lst[j] > lst[j + 1]:
lst[j], lst[j + 1] = lst[j + 1], lst[j]
return lst

# 実行例
lst = [5, 2, 4, 6, 1, 3]
sorted_lst = bubble_sort(lst)
print(sorted_lst)

この実装では、2つのforループを用いて、リストの要素を順番に比較し、必要に応じて交換しています。外側のループは、配列の末尾から順に、すなわち最後には1つの要素が残るまで、処理を繰り返します。内側のループは、現在のステップで比較すべき要素を指定しています。比較する要素のペアを見て、必要に応じて交換していきます。

cocktailソート

cocktailソートは、bubbleソートの改良版で、配列を双方向にスキャンすることで交換回数を減らし、ソートの速度を向上させるアルゴリズムです。bubbleソートと同様に、隣り合う2つの要素を比較し、必要に応じて交換していくことでソートを行いますが、1度のループでは両端から交互に要素を比較していくことが特徴です。

以下は、Pythonでのcocktailソートの実装例です。

def cocktail_sort(lst):
"""
cocktailソートを実行する関数
"""
n = len(lst)
left, right = 0, n - 1
while left < right:
# 右に向かってスキャン
for i in range(left, right):
if lst[i] > lst[i + 1]:
lst[i], lst[i + 1] = lst[i + 1], lst[i]
right -= 1

# 左に向かってスキャン
for i in range(right, left, -1):
if lst[i - 1] > lst[i]:
lst[i], lst[i - 1] = lst[i - 1], lst[i]
left += 1
return lst

# 実行例
lst = [5, 2, 4, 6, 1, 3]
sorted_lst = cocktail_sort(lst)
print(sorted_lst)

この実装では、左右の端から順に要素を比較していき、必要に応じて交換していくことで、ソートを行います。外側のループは、配列の先頭と末尾が交差するまで処理を繰り返します。内側のループは、交互に左右のスキャンを行い、現在の位置と次の位置の要素を比較して必要に応じて交換していきます。このように、双方向にスキャンすることで、要素の比較回数を減らし、ソートの効率を向上させることができます。

comblソート

comblソートは、バブルソートの改良版で、隣り合う要素だけでなく、ある程度離れた要素を比較・交換することで、より効率的にソートを行うアルゴリズムです。bubbleソートと同様に、隣り合う2つの要素を比較し、必要に応じて交換していくことでソートを行いますが、1度のループでのステップ幅を徐々に減らしていくことが特徴です。

以下は、Pythonでのcomblソートの実装例です。

def comb_sort(lst):
"""
comblソートを実行する関数
"""
n = len(lst)
gap = n
shrink = 1.3
sorted_flag = False

while not sorted_flag:
gap = int(gap / shrink)
if gap <= 1:
gap = 1
sorted_flag = True

i = 0
while i + gap < n:
if lst[i] > lst[i + gap]:
lst[i], lst[i + gap] = lst[i + gap], lst[i]
sorted_flag = False
i += 1

return lst

# 実行例
lst = [5, 2, 4, 6, 1, 3]
sorted_lst = comb_sort(lst)
print(sorted_lst)

この実装では、まず初期のステップ幅を配列の長さとし、徐々に縮小していきます。ステップ幅は、縮小率を掛けたものを整数に変換することで求められます。ソート中に要素の交換が行われた場合には、配列がまだソートされていないことを示すフラグを立て、ループを続けます。要素の比較と交換は、現在の位置とステップ幅だけずれた位置にある要素を比較して行います。ステップ幅を徐々に縮小することで、離れた位置にある要素も比較するため、効率的にソートを行うことができます。

def selection_sort(lst):
"""
selectionソートを実行する関数
"""
n = len(lst)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if lst[j] < lst[min_idx]:
min_idx = j
lst[i], lst[min_idx] = lst[min_idx], lst[i]

return lst

# 実行例
lst = [5, 2, 4, 6, 1, 3]
sorted_lst = selection_sort(lst)
print(sorted_lst)

def gnome_sort(lst):
"""
Gnomeソートを実行する関数
"""
n = len(lst)
i = 0
while i < n:
if i == 0 or lst[i] >= lst[i-1]:
i += 1
else:
lst[i], lst[i-1] = lst[i-1], lst[i]
i -= 1

return lst

# 実行例
lst = [5, 2, 4, 6, 1, 3]
sorted_lst = gnome_sort(lst)
print(sorted_lst)

def insertion_sort(lst):
"""
Insertionソートを実行する関数
"""
n = len(lst)
for i in range(1, n):
key = lst[i]
j = i - 1
while j >= 0 and lst[j] > key:
lst[j+1] = lst[j]
j -= 1
lst[j+1] = key

return lst

# 実行例
lst = [5, 2, 4, 6, 1, 3]
sorted_lst = insertion_sort(lst)
print(sorted_lst)

def bucket_sort(lst, bucket_size=5):
"""
Bucketソートを実行する関数
"""
if len(lst) == 0:
return lst

# 最小値と最大値を求める
min_value = min(lst)
max_value = max(lst)

# バケットの数を決定する
bucket_count = (max_value - min_value) // bucket_size + 1

# バケットを初期化する
buckets = [[] for _ in range(bucket_count)]

# 各要素を適切なバケットに振り分ける
for value in lst:
index = (value - min_value) // bucket_size
buckets[index].append(value)

# 各バケットをソートする
for bucket in buckets:
bucket.sort()

# ソート済みの要素を結合する
sorted_lst = [value for bucket in buckets for value in bucket]

return sorted_lst

# 実行例
lst = [5, 2, 4, 6, 1, 3]
sorted_lst = bucket_sort(lst)
print(sorted_lst)

def shell_sort(lst):
"""
Shellソートを実行する関数
"""
n = len(lst)
gap = n // 2 # 初期間隔を設定する

# ギャップが0になるまで繰り返す
while gap > 0:
# 各グループについて挿入ソートを実行する
for i in range(gap, n):
temp = lst[i]
j = i
while j >= gap and lst[j - gap] > temp:
lst[j] = lst[j - gap]
j -= gap
lst[j] = temp

gap //= 2 # ギャップを縮小する

return lst

# 実行例
lst = [5, 2, 4, 6, 1, 3]
sorted_lst = shell_sort(lst)
print(sorted_lst)

def count_sort(lst):
"""
Countソートを実行する関数
"""
# 最大値と最小値を求める
min_value = min(lst)
max_value = max(lst)

# 各要素の出現回数を数える
count = [0] * (max_value - min_value + 1)
for value in lst:
count[value - min_value] += 1

# 各要素の累積和を計算する
for i in range(1, len(count)):
count[i] += count[i - 1]

# ソート済みの要素を格納するリストを初期化する
sorted_lst = [0] * len(lst)

# 各要素をソート済みのリストに格納する
for value in lst:
index = count[value - min_value] - 1
sorted_lst[index] = value
count[value - min_value] -= 1

return sorted_lst

# 実行例
lst = [5, 2, 4, 6, 1, 3]
sorted_lst = count_sort(lst)
print(sorted_lst)

def radix_sort(lst):
"""
Radixソートを実行する関数
"""
# 最大値と最小値を求める
min_value = min(lst)
max_value = max(lst)

# 各桁についてソートする
exp = 1
while (max_value - min_value) // exp > 0:
# カウント用の配列を初期化する
count = [0] * 10

# 各要素の出現回数を数える
for value in lst:
index = (value - min_value) // exp % 10
count[index] += 1

# 各要素の累積和を計算する
for i in range(1, 10):
count[i] += count[i - 1]

# ソート済みの要素を格納するリストを初期化する
sorted_lst = [0] * len(lst)

# 各要素をソート済みのリストに格納する
for value in reversed(lst):
index = (value - min_value) // exp % 10
sorted_lst[count[index] - 1] = value
count[index] -= 1

# ソート済みのリストを更新する
lst = sorted_lst

# 桁数を更新する
exp *= 10

return lst

# 実行例
lst = [5, 2, 4, 6, 1, 3]
sorted_lst = radix_sort(lst)
print(sorted_lst)

def quick_sort(lst):
"""
Quickソートを実行する関数
"""
if len(lst) <= 1:
return lst

# ピボットを選択する
pivot = lst[0]

# ピボットより小さい要素と大きい要素に分割する
left_lst = []
right_lst = []
for value in lst[1:]:
if value < pivot:
left_lst.append(value)
else:
right_lst.append(value)

# 分割された部分リストに対して、再帰的にQuickソートを実行する
sorted_left_lst = quick_sort(left_lst)
sorted_right_lst = quick_sort(right_lst)

# ソート済みの部分リストを結合する
sorted_lst = sorted_left_lst + [pivot] + sorted_right_lst

return sorted_lst

# 実行例
lst = [5, 2, 4, 6, 1, 3]
sorted_lst = quick_sort(lst)
print(sorted_lst)

def merge_sort(lst):
"""
Mergeソートを実行する関数
"""
if len(lst) <= 1:
return lst

# リストを2つの部分リストに分割する
mid = len(lst) // 2
left_lst = lst[:mid]
right_lst = lst[mid:]

# 各部分リストに対して、再帰的にMergeソートを実行する
sorted_left_lst = merge_sort(left_lst)
sorted_right_lst = merge_sort(right_lst)

# 分割された2つの部分リストをマージする
sorted_lst = []
i = j = 0
while i < len(sorted_left_lst) and j < len(sorted_right_lst):
if sorted_left_lst[i] < sorted_right_lst[j]:
sorted_lst.append(sorted_left_lst[i])
i += 1
else:
sorted_lst.append(sorted_right_lst[j])
j += 1

# 余った要素を追加する
sorted_lst.extend(sorted_left_lst[i:])
sorted_lst.extend(sorted_right_lst[j:])

return sorted_lst

# 実行例
lst = [5, 2, 4, 6, 1, 3]
sorted_lst = merge_sort(lst)
print(sorted_lst)

def heap_sort(lst):
"""
Heapソートを実行する関数
"""
# リストをヒープに変換する
def heapify(lst, index, heap_size):
largest = index
left = 2 * index + 1
right = 2 * index + 2

if left < heap_size and lst[left] > lst[largest]:
largest = left

if right < heap_size and lst[right] > lst[largest]:
largest = right

if largest != index:
lst[index], lst[largest] = lst[largest], lst[index]
heapify(lst, largest, heap_size)

n = len(lst)
for i in range(n // 2 - 1, -1, -1):
heapify(lst, i, n)

# ヒープから要素を取り出して、ソート済みのリストに追加する
for i in range(n - 1, 0, -1):
lst[0], lst[i] = lst[i], lst[0]
heapify(lst, 0, i)

return lst

# 実行例
lst = [5, 2, 4, 6, 1, 3]
sorted_lst = heap_sort(lst)
print(sorted_lst)

def tim_sort(lst):
"""
Timソートを実行する関数
"""
def insertion_sort(lst, left, right):
for i in range(left + 1, right + 1):
value = lst[i]
j = i - 1
while j >= left and lst[j] > value:
lst[j + 1] = lst[j]
j -= 1
lst[j + 1] = value

def merge(lst, left, mid, right):
lst1 = lst[left:mid + 1]
lst2 = lst[mid + 1:right + 1]
i = j = 0
k = left
while i < len(lst1) and j < len(lst2):
if lst1[i] < lst2[j]:
lst[k] = lst1[i]
i += 1
else:
lst[k] = lst2[j]
j += 1
k += 1

while i < len(lst1):
lst[k] = lst1[i]
i += 1
k += 1

while j < len(lst2):
lst[k] = lst2[j]
j += 1
k += 1

n = len(lst)
min_run = 32
for i in range(0, n, min_run):
insertion_sort(lst, i, min(i + min_run - 1, n - 1))

size = min_run
while size < n:
for left in range(0, n, 2 * size):
mid = left + size - 1
right = min(left + 2 * size - 1, n - 1)
merge(lst, left, mid, right)
size *= 2

return lst

# 実行例
lst = [5, 2, 4, 6, 1, 3]
sorted_lst = tim_sort(lst)
print(sorted_lst)

def binary_search(lst, target):
"""
バイナリサーチを実行する関数
"""
left, right = 0, len(lst) - 1
while left <= right:
mid = (left + right) // 2
if lst[mid] == target:
return mid
elif lst[mid] < target:
left = mid + 1
else:
right = mid - 1

return -1

# 実行例
lst = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 7
index = binary_search(lst, target)
if index == -1:
print("Not found")
else:
print(f"Found at index {index}")