2026a 第04回:データ構造とアルゴリズム

小テスト

本日の講義

AIとアルゴリズムの違い

https://gyazo.com/f63e5c8ebc9ea9e9af0f0a2e4b00168c

ソートアルゴリズム

バブルソートと選択ソート

バブルソートは「隣接比較→入れ替え」の繰り返し

選択ソートは「最小を覚えておいて、一気に移動」

いずれも何周もするという意味でO(n^2) で同じ

code:python

def bubble_sort(arr):

n = len(arr)

for i in range(n): # 要素の数だけ処理を繰り返す

for j in range(n - 1 - i): # 先頭から、末尾 - 繰り返し回数　のデータを走査

return arr

print("バブルソート:", bubble_sort(data1.copy()))

code:python

def selection_sort(arr):

n = len(arr)

for i in range(n): # 要素の数だけ繰り返す

min_idx = i # 最小値の場所をメモ

for j in range(i + 1, n): # 先頭+繰り返し回数 の場所から末尾までデータを走査

min_idx = j

return arr

print("選択ソート:", selection_sort(data2.copy()))

クイックソート

code:python

def quick_sort(arr):

if len(arr) <= 1: # 与えられたリストの長さが1以下なら処理終了

return arr

return quick_sort(left) + middle + quick_sort(right) # left, rightをそれぞれもう一度実行

print("クイックソート:", quick_sort(data1.copy()))

比較的暴力的なアルゴリズムもあるよ

遺伝的アルゴリズム

e.g. シフトの最適化など

1. シフトの質を評価する関数を定義する

2. 適当なシフトを組む

3. シフトの１箇所を入れ替えてみる

before-afterで比較して、評価が高いシフトを維持

→ これを繰り返し

課題

レポート課題です！

来週は休み、期日は2週間後

タイピングテスト