整列 (Sort)
整列・ソート
選択ソート
リスト（配列）で与えられたデータ群を昇順に整列するプログラムを以下に示す。
def selection_sort(num_list):
for i in range(len(num_list)): # 最小のデータを置く場所（添え字）を設定する
min_index = i # その場所の値を暫定的な最小値とみなして添え字を記録する
for j in range(i + 1, len(num_list)): # リスト（配列）の残りの部分の要素を対象として最小値がないか探す
if num_list[j] < num_list[min_index]: # 暫定的な最小値よりも小さな要素があったら
min_index = j # その要素の位置を新たな暫定的な最小値としてその添え字を記録する
tmp = num_list[min_index] # 内側のforループでの最小値の検索が終わったら、見つかった最小値を置き換える
num_list[min_index] = num_list[i]
num_list[i] = tmp
return num_list
lst = [64, 26, 12, 34, 11, 48]
sorted_list = selection_sort(lst)
print("ソートされたリスト:", sorted_list)ソートされたリスト: [11, 12, 26, 34, 48, 64]バブルソート
リスト（配列）で与えられたデータ群を昇順に整列するプログラムを以下に示す。
def bubble_sort(num_list):
n = len(num_list)
for i in range(n):
for j in range(0, n-i-1):
if num_list[j] > num_list[j+1]:
tmp = num_list[j]
num_list[j] = num_list[j+1]
num_list[j+1] = tmp
return num_list
lst = [64, 26, 12, 34, 11, 48]
sorted_list = bubble_sort(lst)
print("ソートされたリスト:", sorted_list)ソートされたリスト: [11, 12, 26, 34, 48, 64]クリックソート
分割統治法 (Divide and Conquer Method)
リスト（配列）で与えられたデータ群を昇順に整列するプログラムを以下に示す。
再帰処理、分割統治法
再帰処理を利用する場合には、まず終了条件を確認する。
関数の引数にはリストだけでなく、リストの添え字も追加
再帰処理での処理対象となるリスト（配列）の部位を示すための添え字
def quicksort(num_list, low, high):
if low < high:
pivot = num_list[high]
i = low - 1
for j in range(low, high):
if num_list[j] <= pivot:
i += 1
tmp = num_list[i]
num_list[i] = num_list[j]
num_list[j] = tmp
tmp = num_list[high]
num_list[high] = num_list[i + 1]
num_list[i + 1] = tmp
pi = i + 1
quicksort(num_list, low, pi - 1)
quicksort(num_list, pi + 1, high)
list_data = [3, 6, 8, 10, 1, 2, 1]
print("元の配列:", list_data)
quicksort(list_data, 0, len(list_data) - 1)
print("ソート後の配列:", list_data)def quicksort(arr, low, high):
if low < high:
pi = partition(arr, low, high)
quicksort(arr, low, pi - 1)
quicksort(arr, pi + 1, high)
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
array_data = [3, 6, 8, 10, 1, 2, 1]
print("元の配列:", array_data)
quicksort(array_data, 0, len(array_data) - 1)
print("ソート後の配列:", array_data)整列法の計算量（性能評価）
整列アルゴリズムは、ここに示した例だけではなく多数のアルゴリズムが提案、利用されている。どのような整列アルゴリズムが提案されているかを調査するとともに、それらの特性の比較をしてみなさい。