Pythonで６種類の並べ替えアルゴリズムを調べる
昇順に並べ替えることを前提とする（降順は内容を読み替えてください）
１．バブルソート
隣同士の値を比較、必要があれば入れ替え、を繰り返して整列させる
計算回数は、O(n^2)
サンプルコード
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
# 使用例
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("ソート済み配列：")
for i in range(len(arr)):
print("%d" %arr[i]),
２．クイックソート
基準値を設けて、基準値より大きいブロックと小さいブロックに分けて並び替える
計算回数は、O(n log n)
サンプルコード
def quick_sort(arr, low, high):
if low < high:
# pivotを決定する
pivot_index = partition(arr, low, high)
# pivotを中心に左側をソートする
quick_sort(arr, low, pivot_index - 1)
# pivotを中心に右側をソートする
quick_sort(arr, pivot_index + 1, high)
def partition(arr, low, high):
# pivotを最後の要素に設定する
pivot = arr[high]
# pivotより小さい要素を左側に、大きい要素を右側に配置する
i = low - 1
for j in range(low, high):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
# pivotを適切な位置に配置する
arr[i+1], arr[high] = arr[high], arr[i+1]
return i+1
# 使用例
arr = [64, 34, 25, 12, 22, 11, 90]
n = len(arr)
quick_sort(arr, 0, n-1)
print("ソート済み配列：")
for i in range(n):
print("%d" % arr[i]),
３．マージソート
対象のデータを分割し、分割後の小さいブロック内で整列、再度統合する
計算回数は、O(n log n)
サンプルコード
def merge_sort(arr):
if len(arr) > 1:
# 中央の位置を求める
mid = len(arr) // 2
# 左側と右側に分割する
left_half = arr[:mid]
right_half = arr[mid:]
# 左側と右側を再帰的にソートする
merge_sort(left_half)
merge_sort(right_half)
# ソート済みの左側と右側をマージする
i = j = k = 0
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1
# 左側に残った要素を配列にコピーする
while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1
# 右側に残った要素を配列にコピーする
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1
# 使用例
arr = [64, 34, 25, 12, 22, 11, 90]
merge_sort(arr)
print("ソート済み配列：")
for i in range(len(arr)):
print("%d" %arr[i]),
４．選択ソート
データ内の最小値（最大値）の値を見つけて、左から順番に並び替える
計算回数は、o(n^2)
サンプルコード
def selection_sort(arr):
n = len(arr)
# 配列の先頭から末尾まで、最小値を選択して配置する
for i in range(n):
min_index = i
for j in range(i+1, n):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
# 使用例
arr = [64, 34, 25, 12, 22, 11, 90]
selection_sort(arr)
print("ソート済み配列：")
for i in range(len(arr)):
print("%d" %arr[i]),
５．挿入ソート
左から順番に要素を比較しながら入れ替えていく方法
計算回数は、最大でn(n-1)/2
サンプルコード
def insertion_sort(arr):
n = len(arr)
# 配列の先頭から末尾まで、要素を挿入して配置する
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
# 使用例
arr = [64, 34, 25, 12, 22, 11, 90]
insertion_sort(arr)
print("ソート済み配列：")
for i in range(len(arr)):
print("%d" %arr[i]),
６．ヒープソート
二分木（親１に対して子２のツリー構造）の一種を構築して並べ替えをおこなう
計算回数は、O(n log n)
サンプルコード
def heapify(arr, n, i):
largest = i # 親ノード
l = 2*i + 1 # 左の子ノード
r = 2*i + 2 # 右の子ノード
# 左の子ノードが親ノードより大きい場合
if l < n and arr[largest] < arr[l]:
largest = l
# 右の子ノードが親ノードより大きい場合
if r < n and arr[largest] < arr[r]:
largest = r
# 親ノードが最大値でない場合、親ノードと最大値を交換する
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
# 子ノードのヒープも修正する
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
# 最初に、配列をヒープ構造にする
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# ヒープから一つずつ最大値を取り出して、配列の末尾に配置する
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # 最大値を末尾に配置
heapify(arr, i, 0) # 未ソート部分のヒープを再構築する
# 使用例
arr = [64, 34, 25, 12, 22, 11, 90]
heap_sort(arr)
print("ソート済み配列：")
for i in range(len(arr)):
print("%d" %arr[i]),
