YomuAA

読むアスキーアート/ よむえーえー / やる夫スレ自己まとめ

本作品は「AIにやる夫スレを作らせるにはどうすればよさそうかを考える」をテーマとした作品です。 そして第一話はAIに適当に作らせた「やる夫で学ぶクイックソート」となります。 「面白さとか背景知識説明の雑さはおいておいて、とりあえずこれくらいはできるんだなあ」というのをお見せするというのが今回のテーマとなります。

1
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓ ┃　やる夫で学ぶクイックソート　┃ ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
2
?????????????????????????????????????????? ?　～ライブラリ依存からスクラッチ実装への道～　? ??????????????????????????????????????????
3
?????????????????????????????????????????? ?　第1章：やる夫、ソートを完了する（？）　? ??????????????????????????????????????????
4
　　　　　　____ 　　　　 ／　　 　＼ 　　　／　 _ノ 　ヽ、＼ 　 ／ 　oﾟ⌒　　⌒ﾟo　＼　　　クイックソートの実装できたお！ 　 |　　 　（__人__）　　　|　　　これでソートはバッチリだお！ 　 ＼　　　 ` ⌒´ 　 　／
5
━━━ python ━━━ # yaruo_sort.py - やる夫の「実装」 data = [64, 34, 25, 12, 22, 11, 90] result = sorted(data) print(f"ソート完了: {result}") # 出力: ソート完了: [11, 12, 22, 25, 34, 64, 90] ━━━━━━━━━━━━━━
6
　　　　　/ ￣￣＼ 　　　 ／　　 _ノ　＼ 　　　 |　　　（ ●）（●） 　 .　　|　　　　 （__人__）　　　……やる夫、それは「使った」だけで 　　　 |　　　　　｀ ⌒´ﾉ 　　　「実装した」とは言わないだろ 　 .　　|　　　　　　　 }　　　　常識的に考えて…… 　 .　　ヽ　　　　 　 } 　　　　 ヽ　　　　ノ 　　　　　/　　　 ヽ
7
　　　　　　____ 　　　　 ／　　 　＼ 　　　／　 ⌒　　⌒　＼ 　 ／ 　 （●） 　（●）　＼　　　え？でも結果は正しく出てるお？ 　 |　　 　（__人__）　　　|　　　仕事では動けばいいんだお！ 　 ＼　　　 ` ⌒´ 　 　／
8
　　　　　/ ￣￣＼ 　　　 ／　　 _ノ　＼ 　　　 |　　　（ ー）（ー） 　 .　　|　　　　 （__人__）　　　じゃあ聞くが、sorted()の中で 　　　 |　　　　　｀ ⌒´ﾉ 　　　何が起きているか説明できるか？ 　 .　　|　　　　　　　 } 　 .　　ヽ　　　　 　 }　　　　　クイックソートとは何か、 　　　　 ヽ　　　　ノ　　　　　 答えてみろ 　　　　　/　　　 ヽ
9
　　　　　　____ 　　　　 ／　　 　＼ 　　　／　 u　　　　＼ 　 ／ 　 　 　（○） 　＼　　　え、えーっと…… 　 |　　 　u　（__人__）　|　　　速いソート……？ 　 ＼　　　　 ` ⌒´ 　／
10
?????????????????????????????????????????? ?　第2章：クイックソートの基本を学ぶ　? ??????????????????????????????????????????
11
　　　　　/ ￣￣＼ 　　　 ／　　 _ノ　＼ 　　　 |　　　（ ●）（●） 　 .　　|　　　　 （__人__）　　　クイックソートは「分割統治法」に 　　　 |　　　　　｀ ⌒´ﾉ 　　　基づくアルゴリズムだ 　 .　　|　　　　　　　 } 　 .　　ヽ　　　　 　 }　　　　　基本的な考え方は3ステップだ 　　　　 ヽ　　　　ノ 　　　　　/　　　 ヽ
12
┌───────────────────────────────────┐ │　クイックソートの3ステップ　│ └───────────────────────────────────┘
13
1. 【ピボット選択】: 配列から基準となる要素を1つ選ぶ 2. 【分割（Partition）】: ピボットより小さい要素を左、大きい要素を右に振り分ける 3. 【再帰】: 左右それぞれの部分配列に対して同じ処理を繰り返す
14
　　　　　　____ 　　　　 ／　　 　＼ 　　　／　 ⌒　　⌒　＼ 　 ／ 　 （●） 　（●）　＼　　　なるほど！じゃあこうだお！ 　 |　　 　（__人__）　　　| 　 ＼　　　 ` ⌒´ 　 　／
15
━━━ python ━━━ # yaruo_quicksort_v1.py - やる夫の最初の挑戦 def quicksort_yaruo_v1(arr): """やる夫の最初のクイックソート実装""" if len(arr) <= 1: return arr pivot = arr[0] # 最初の要素をピボットに left = [x for x in arr if x < pivot] right = [x for x in arr if x > pivot] return quicksort_yaruo_v1(left) + [pivot] + quicksort_yaruo_v1(right) # テスト data = [64, 34, 25, 12, 22, 11, 90] print(quicksort_yaruo_v1(data)) # 出力: [11, 12, 22, 25, 34, 64, 90] ━━━━━━━━━━━━━━
16
　　　　　　____ 　　　　 ／　　 　＼ 　　　／　 _ノ 　ヽ、＼ 　 ／ 　oﾟ⌒　　⌒ﾟo　＼　　　やったお！ちゃんと動いたお！ 　 |　　 　（__人__）　　　|　　　これでクイックソートマスターだお！ 　 ＼　　　 ` ⌒´ 　 　／
17
　　　　　/ ￣￣＼ 　　　 ／　　 _ノ　＼ 　　　 |　　　（ ー）（ー） 　 .　　|　　　　 （__人__）　　　待て。このコードには 　　　 |　　　　　｀ ⌒´ﾉ 　　　いくつか問題があるだろ…… 　 .　　|　　　　　　　 } 　 .　　ヽ　　　　 　 }　　　　　 　　　　 ヽ　　　　ノ　　　　　 　　　　　/　　　 ヽ
18
?????????????????????????????????????????? ?　第3章：重複要素の罠　? ??????????????????????????????????????????
19
　　　　　/ ￣￣＼ 　　　 ／　　 _ノ　＼ 　　　 |　　　（ ●）（●） 　 .　　|　　　　 （__人__）　　　やる夫、このデータでテストしてみろ 　　　 |　　　　　｀ ⌒´ﾉ 　　　 　 .　　|　　　　　　　 } 　 .　　ヽ　　　　 　 }　　　　　 　　　　 ヽ　　　　ノ 　　　　　/　　　 ヽ
20
━━━ python ━━━ # 重複要素を含むデータ data_with_duplicates = [64, 34, 25, 12, 22, 11, 90, 22, 34, 11] print(f"元データ: {data_with_duplicates}") print(f"やる夫版: {quicksort_yaruo_v1(data_with_duplicates)}") print(f"sorted(): {sorted(data_with_duplicates)}") ━━━━━━━━━━━━━━
21
　　　　　　____ 　　　　 ／　　 　＼ 　　　／　 u　　　　＼ 　 ／ 　 　 　（○） 　＼　　　あれ……？ 　 |　　 　u　（__人__）　| 　 ＼　　　　 ` ⌒´ 　／ # 出力: # 元データ: [64, 34, 25, 12, 22, 11, 90, 22, 34, 11] # やる夫版: [12, 22, 25, 34, 64, 90] ← 要素が消えてる！ # sorted(): [11, 11, 12, 22, 22, 25, 34, 34, 64, 90]
22
　　　　　/ ￣￣＼ 　　　 ／　　 _ノ　＼ 　　　 |　　　（ ●）（●） 　 .　　|　　　　 （__人__）　　　重複した要素が消えてるだろ 　　　 |　　　　　｀ ⌒´ﾉ 　　　お前のコード、x < pivot と x > pivot 　 .　　|　　　　　　　 }　　　　しか見てないから x == pivot の場合が 　 .　　ヽ　　　　 　 }　　　　　抜け落ちてるんだ 　　　　 ヽ　　　　ノ 　　　　　/　　　 ヽ
23
　　　　　　____ 　　　　 ／　　 　＼ 　　　／　 ⌒　　⌒　＼ 　 ／ 　 （●） 　（●）　＼　　　そうか！<= にすればいいんだお！ 　 |　　 　（__人__）　　　| 　 ＼　　　 ` ⌒´ 　 　／
24
━━━ python ━━━ # yaruo_quicksort_v2.py - 重複対応版 def quicksort_yaruo_v2(arr): """重複要素に対応したクイックソート""" if len(arr) <= 1: return arr pivot = arr[0] left = [x for x in arr if x < pivot] middle = [x for x in arr if x == pivot] # ピボットと等しい要素を集める right = [x for x in arr if x > pivot] return quicksort_yaruo_v2(left) + middle + quicksort_yaruo_v2(right) # テスト data_with_duplicates = [64, 34, 25, 12, 22, 11, 90, 22, 34, 11] print(f"やる夫版v2: {quicksort_yaruo_v2(data_with_duplicates)}") print(f"sorted() : {sorted(data_with_duplicates)}") # 出力: # やる夫版v2: [11, 11, 12, 22, 22, 25, 34, 34, 64, 90] # sorted() : [11, 11, 12, 22, 22, 25, 34, 34, 64, 90] ━━━━━━━━━━━━━━
25
　　　　　　____ 　　　　 ／　　 　＼ 　　　／　 _ノ 　ヽ、＼ 　 ／ 　oﾟ⌒　　⌒ﾟo　＼　　　一致したお！完璧だお！ 　 |　　 　（__人__）　　　| 　 ＼　　　 ` ⌒´ 　 　／
26
?????????????????????????????????????????? ?　第4章：計算量の落とし穴　? ??????????????????????????????????????????
27
　　　　　/ ￣￣＼ 　　　 ／　　 _ノ　＼ 　　　 |　　　（ ー）（ー） 　 .　　|　　　　 （__人__）　　　やる夫、クイックソートの 　　　 |　　　　　｀ ⌒´ﾉ 　　　計算量はいくつだ？ 　 .　　|　　　　　　　 } 　 .　　ヽ　　　　 　 }　　　　　 　　　　 ヽ　　　　ノ 　　　　　/　　　 ヽ
28
　　　　　　____ 　　　　 ／　　 　＼ 　　　／　 ⌒　　⌒　＼ 　 ／ 　 （●） 　（●）　＼　　　O(n log n) だお！ 　 |　　 　（__人__）　　　|　　　だから速いんだお！ 　 ＼　　　 ` ⌒´ 　 　／
29
　　　　　/ ￣￣＼ 　　　 ／　　 _ノ　＼ 　　　 |　　　（ ●）（●） 　 .　　|　　　　 （__人__）　　　それは「平均計算量」だ 　　　 |　　　　　｀ ⌒´ﾉ 　　　最悪計算量は O(n?) になる 　 .　　|　　　　　　　 }　　　　どういう場合か分かるか？ 　 .　　ヽ　　　　 　 }　　　　　 　　　　 ヽ　　　　ノ 　　　　　/　　　 ヽ
30
　　　　　　____ 　　　　 ／　　 　＼ 　　　／　 u　　　　＼ 　 ／ 　 　 　（○） 　＼　　　う……わからないお…… 　 |　　 　u　（__人__）　| 　 ＼　　　　 ` ⌒´ 　／
31
　　　　　/ ￣￣＼ 　　　 ／　　 _ノ　＼ 　　　 |　　　（ ●）（●） 　 .　　|　　　　 （__人__）　　　お前のコードでは最初の要素を 　　　 |　　　　　｀ ⌒´ﾉ 　　　ピボットにしているだろ 　 .　　|　　　　　　　 } 　 .　　ヽ　　　　 　 }　　　　　もしソート済みの配列が来たら 　　　　 ヽ　　　　ノ　　　　　 どうなると思う？ 　　　　　/　　　 ヽ
32
━━━ python ━━━ # 最悪ケースの例 import time def quicksort_yaruo_v2_with_count(arr, depth=0): """再帰の深さをカウントするバージョン""" global max_depth max_depth = max(max_depth, depth) if len(arr) <= 1: return arr pivot = arr[0] left = [x for x in arr if x < pivot] middle = [x for x in arr if x == pivot] right = [x for x in arr if x > pivot] return (quicksort_yaruo_v2_with_count(left, depth+1) + middle + quicksort_yaruo_v2_with_count(right, depth+1)) # ランダムデータ vs ソート済みデータ import random # ランダムデータ random_data = list(range(1000)) random.shuffle(random_data) max_depth = 0 quicksort_yaruo_v2_with_count(random_data.copy()) print(f"ランダムデータ(n=1000): 最大再帰深度 = {max_depth}") # ソート済みデータ（最悪ケース） sorted_data = list(range(1000)) max_depth = 0 # quicksort_yaruo_v2_with_count(sorted_data.copy()) # これは危険！ print(f"ソート済みデータ: 最大再帰深度 = 約1000 (スタックオーバーフローの危険)") ━━━━━━━━━━━━━━
33
　　　　　　____ 　　　　 ／　　 　＼ 　　　／　 u　　　　＼ 　 ／ 　 　 　（○） 　＼　　　そうか！ソート済みだと 　 |　　 　u　（__人__）　|　　　毎回最小値がピボットになって 　 ＼　　　　 ` ⌒´ 　／　　　片側にしか分割されないのかお！
34
　　　　　/ ￣￣＼ 　　　 ／　　 _ノ　＼ 　　　 |　　　（ ●）（●） 　 .　　|　　　　 （__人__）　　　その通りだ 　　　 |　　　　　｀ ⌒´ﾉ 　　　対策として一般的なのは： 　 .　　|　　　　　　　 } 　 .　　ヽ　　　　 　 }　　　　　1. ランダムピボット選択 　　　　 ヽ　　　　ノ　　　　　 2. 三値の中央値（median-of-three） 　　　　　/　　　 ヽ　　　　　　3. イントロソート（深さ制限付き）
35
?????????????????????????????????????????? ?　第5章：本格的な実装へ　? ??????????????????????????????????????????
36
　　　　　　____ 　　　　 ／　　 　＼ 　　　／　 ⌒　　⌒　＼ 　 ／ 　 （●） 　（●）　＼　　　よーし！全部盛り込んで 　 |　　 　（__人__）　　　|　　　完璧な実装を作るお！ 　 ＼　　　 ` ⌒´ 　 　／
37
　　　　　/ ￣￣＼ 　　　 ／　　 _ノ　＼ 　　　 |　　　（ ー）（ー） 　 .　　|　　　　 （__人__）　　　待て。その前にもう一つ 　　　 |　　　　　｀ ⌒´ﾉ 　　　重要な問題がある 　 .　　|　　　　　　　 } 　 .　　ヽ　　　　 　 }　　　　　今のコード、メモリ効率が悪いだろ 　　　　 ヽ　　　　ノ 　　　　　/　　　 ヽ
38
　　　　　　____ 　　　　 ／　　 　＼ 　　　／　 u　　　　＼ 　 ／ 　 　 　（○） 　＼　　　え？リスト内包表記は 　 |　　 　u　（__人__）　|　　　Pythonらしくていいと思ったお…… 　 ＼　　　　 ` ⌒´ 　／
39
　　　　　/ ￣￣＼ 　　　 ／　　 _ノ　＼ 　　　 |　　　（ ●）（●） 　 .　　|　　　　 （__人__）　　　リスト内包表記は読みやすいが、 　　　 |　　　　　｀ ⌒´ﾉ 　　　毎回新しいリストを作るから 　 .　　|　　　　　　　 }　　　　O(n)の追加メモリを使う 　 .　　ヽ　　　　 　 }　　　　　 　　　　 ヽ　　　　ノ　　　　　 本来のクイックソートは 　　　　　/　　　 ヽ　　　　　　「in-place」で実装するべきだ
40
┌───────────────────────────────────┐ │　In-place パーティションの概念　│ └───────────────────────────────────┘
41
　　　　　/ ￣￣＼ 　　　 ／　　 _ノ　＼ 　　　 |　　　（ ●）（●） 　 .　　|　　　　 （__人__）　　　in-placeのパーティションは 　　　 |　　　　　｀ ⌒´ﾉ 　　　配列の要素を「交換」して 　 .　　|　　　　　　　 }　　　　並べ替えるんだ 　 .　　ヽ　　　　 　 }　　　　　 　　　　 ヽ　　　　ノ　　　　　 有名なのがLomutoとHoareの 　　　　　/　　　 ヽ　　　　　　2つのスキームだ
42
【Lomutoパーティション】のイメージ：
43
━━━ code ━━━ 配列: [3, 6, 8, 10, 1, 2, 1] ピボット = 1（最後の要素） i = -1 (小さい要素の境界) j = 0 (スキャン位置) [3, 6, 8, 10, 1, 2, | 1] ← 1(ピボット)より小さい要素を左に集める ↑ ピボット 処理後: [1, 1, 2, 10, 6, 8, 3] ではなく適切に分割される ━━━━━━━━━━━━
44
?????????????????????????????????????????? ?　第6章：完全版の実装　? ??????????????????????????????????????????
45
　　　　　　____ 　　　　 ／　　 　＼ 　　　／　 ⌒　　⌒　＼ 　 ／ 　 （●） 　（●）　＼　　　全部理解したお！ 　 |　　 　（__人__）　　　|　　　完全版を実装するお！ 　 ＼　　　 ` ⌒´ 　 　／
46
━━━ python ━━━ # yaruo_quicksort_final.py - 完全版クイックソート """ やる夫とやらない夫で作り上げた完全版クイックソート 特徴: - In-place実装でメモリ効率が良い - median-of-three によるピボット選択 - 重複要素に対応 - 小さい配列には挿入ソートを使用（最適化） """ from typing import List, TypeVar from loguru import logger import random T = TypeVar('T') # ログ設定 logger.remove() logger.add( sink=lambda msg: print(msg, end=''), format="{level}: {message}", level="DEBUG" ) def insertion_sort(arr: List[T], low: int, high: int) -> None: """ 挿入ソート（小さい配列用） Parameters ---------- arr : List[T] ソート対象の配列 low : int 開始インデックス high : int 終了インデックス（含む） Examples -------- >>> data = [5, 2, 4, 1, 3] >>> insertion_sort(data, 0, 4) >>> data [1, 2, 3, 4, 5] """ logger.debug(f"insertion_sort: arr[{low}:{high+1}] = {arr[low:high+1]}") for i in range(low + 1, high + 1): key = arr[i] j = i - 1 while j >= low and arr[j] > key: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key def median_of_three(arr: List[T], low: int, high: int) -> int: """ 三値の中央値を選んでピボットとする Parameters ---------- arr : List[T] 配列 low : int 開始インデックス high : int 終了インデックス Returns ------- int 中央値のインデックス Examples -------- >>> arr = [8, 3, 5] >>> median_of_three(arr, 0, 2) # 3, 5, 8 の中央値は 5 2 """ mid = (low + high) // 2 # low, mid, high の3つの値を比較 if arr[low] > arr[mid]: arr[low], arr[mid] = arr[mid], arr[low] if arr[low] > arr[high]: arr[low], arr[high] = arr[high], arr[low] if arr[mid] > arr[high]: arr[mid], arr[high] = arr[high], arr[mid] # 中央値は mid に来る logger.debug(f"median_of_three: 選択されたピボット = {arr[mid]} (index={mid})") return mid def partition(arr: List[T], low: int, high: int) -> int: """ Hoareパーティションの改良版 ピボットより小さい要素を左に、大きい要素を右に配置 Parameters ---------- arr : List[T] パーティション対象の配列 low : int 開始インデックス high : int 終了インデックス Returns ------- int ピボットの最終位置 Examples -------- >>> arr = [3, 6, 8, 10, 1, 2, 1] >>> pivot_idx = partition(arr, 0, 6) >>> # ピボット位置の左は全てピボット以下、右は全てピボット以上 """ # median-of-threeでピボットを選択し、最後に移動 pivot_idx = median_of_three(arr, low, high) arr[pivot_idx], arr[high] = arr[high], arr[pivot_idx] pivot = arr[high] logger.debug(f"partition: arr[{low}:{high+1}] = {arr[low:high+1]}, pivot = {pivot}") i = low - 1 # 小さい要素の境界 for j in range(low, high): if arr[j] <= pivot: i += 1 arr[i], arr[j] = arr[j], arr[i] logger.debug(f" swap: arr[{i}]={arr[i]} <-> arr[{j}]={arr[j]}") # ピボットを正しい位置に arr[i + 1], arr[high] = arr[high], arr[i + 1] logger.debug(f" ピボット位置確定: index={i+1}, 配列 = {arr[low:high+1]}") return i + 1 def quicksort_inplace(arr: List[T], low: int, high: int, insertion_threshold: int = 10) -> None: """ In-place クイックソート本体 Parameters ---------- arr : List[T] ソート対象の配列 low : int 開始インデックス high : int 終了インデックス insertion_threshold : int, optional 挿入ソートに切り替える閾値, by default 10 """ if low < high: # 小さい配列は挿入ソートの方が速い if high - low + 1 <= insertion_threshold: logger.debug(f"小さい配列のため挿入ソートに切り替え: size={high-low+1}") insertion_sort(arr, low, high) return # パーティション pivot_idx = partition(arr, low, high) # 再帰（小さい方を先にソートしてスタック使用量を削減） if pivot_idx - low < high - pivot_idx: quicksort_inplace(arr, low, pivot_idx - 1, insertion_threshold) quicksort_inplace(arr, pivot_idx + 1, high, insertion_threshold) else: quicksort_inplace(arr, pivot_idx + 1, high, insertion_threshold) quicksort_inplace(arr, low, pivot_idx - 1, insertion_threshold) def quicksort(arr: List[T]) -> List[T]: """ クイックソートのメインインターフェース 元の配列を変更せず、ソート済みの新しいリストを返す Parameters ---------- arr : List[T] ソート対象の配列 Returns ------- List[T] ソート済みの配列（新しいリスト） Examples -------- >>> quicksort([64, 34, 25, 12, 22, 11, 90]) [11, 12, 22, 25, 34, 64, 90] >>> quicksort([64, 34, 25, 12, 22, 11, 90, 22, 34, 11]) [11, 11, 12, 22, 22, 25, 34, 34, 64, 90] >>> quicksort([]) [] >>> quicksort([1]) [1] """ logger.info(f"quicksort開始: 入力 = {arr}") if len(arr) <= 1: logger.info("要素数が1以下のためそのまま返却") return arr.copy() if arr else [] # コピーを作成してin-placeソート result = arr.copy() quicksort_inplace(result, 0, len(result) - 1) logger.info(f"quicksort完了: 出力 = {result}") return result # === テスト === if __name__ == "__main__": print("=" * 60) print("やる夫とやらない夫のクイックソート 最終テスト") print("=" * 60) # テストケース1: 基本 test1 = [64, 34, 25, 12, 22, 11, 90] result1 = quicksort(test1) expected1 = sorted(test1) print(f"\nテスト1（基本）:") print(f" 入力: {test1}") print(f" 出力: {result1}") print(f" 期待: {expected1}") print(f" 結果: {'? PASS' if result1 == expected1 else '? FAIL'}") # テストケース2: 重複あり test2 = [64, 34, 25, 12, 22, 11, 90, 22, 34, 11] result2 = quicksort(test2) expected2 = sorted(test2) print(f"\nテスト2（重複あり）:") print(f" 入力: {test2}") print(f" 出力: {result2}") print(f" 期待: {expected2}") print(f" 結果: {'? PASS' if result2 == expected2 else '? FAIL'}") # テストケース3: ソート済み（最悪ケース対策確認） test3 = list(range(100)) result3 = quicksort(test3) expected3 = sorted(test3) print(f"\nテスト3（ソート済み100要素）:") print(f" 結果: {'? PASS' if result3 == expected3 else '? FAIL'}") # テストケース4: 逆順（最悪ケース対策確認） test4 = list(range(100, 0, -1)) result4 = quicksort(test4) expected4 = sorted(test4) print(f"\nテスト4（逆順100要素）:") print(f" 結果: {'? PASS' if result4 == expected4 else '? FAIL'}") # テストケース5: ランダム大規模 test5 = [random.randint(1, 10000) for _ in range(1000)] result5 = quicksort(test5) expected5 = sorted(test5) print(f"\nテスト5（ランダム1000要素）:") print(f" 結果: {'? PASS' if result5 == expected5 else '? FAIL'}") # テストケース6: 空配列 test6 = [] result6 = quicksort(test6) expected6 = [] print(f"\nテスト6（空配列）:") print(f" 結果: {'? PASS' if result6 == expected6 else '? FAIL'}") # テストケース7: 1要素 test7 = [42] result7 = quicksort(test7) expected7 = [42] print(f"\nテスト7（1要素）:") print(f" 結果: {'? PASS' if result7 == expected7 else '? FAIL'}") print("\n" + "=" * 60) print("全テスト完了！") print("=" * 60) ━━━━━━━━━━━━━━
47
?????????????????????????????????????????? ?　第7章：振り返りと完結　? ??????????????????????????????????????????
48
　　　　　　____ 　　　　 ／　　 　＼ 　　　／　 ⌒　　⌒　＼ 　 ／ 　 （●） 　（●）　＼　　　全部のテストがパスしたお！ 　 |　　 　（__人__）　　　|　　　sorted()と同じ結果が出てるお！ 　 ＼　　　 ` ⌒´ 　 　／
49
　　　　　/ ￣￣＼ 　　　 ／　　 _ノ　＼ 　　　 |　　　（ ●）（●） 　 .　　|　　　　 （__人__）　　　よくやった。今回学んだことを 　　　 |　　　　　｀ ⌒´ﾉ 　　　まとめてみろ 　 .　　|　　　　　　　 } 　 .　　ヽ　　　　 　 }　　　　　 　　　　 ヽ　　　　ノ 　　　　　/　　　 ヽ
50
┌───────────────────────────────────┐ │　やる夫のまとめ　│ └───────────────────────────────────┘
51
問題点　対策 重複要素が消える　`x == pivot` のケースも処理する 最悪計算量 O(n?)　median-of-three でピボット選択 メモリ効率が悪い　in-place パーティションで実装 小配列で非効率　挿入ソートへの切り替え スタックオーバーフロー　小さい部分配列を先に処理
52
　　　　　/ ￣￣＼ 　　　 ／　　 _ノ　＼ 　　　 |　　　（ ●）（●） 　 .　　|　　　　 （__人__）　　　ついでに言っておくと、 　　　 |　　　　　｀ ⌒´ﾉ 　　　Pythonの sorted() は実は 　 .　　|　　　　　　　 }　　　　クイックソートじゃなくて 　 .　　ヽ　　　　 　 }　　　　　「Timsort」というアルゴリズムだ 　　　　 ヽ　　　　ノ 　　　　　/　　　 ヽ
53
　　　　　　____ 　　　　 ／　　 　＼ 　　　／　 u　　　　＼ 　 ／ 　 　 　（○） 　＼　　　えっ 　 |　　 　u　（__人__）　| 　 ＼　　　　 ` ⌒´ 　／
54
　　　　　/ ￣￣＼ 　　　 ／　　 _ノ　＼ 　　　 |　　　（ ー）（ー） 　 .　　|　　　　 （__人__）　　　Timsortはマージソートと 　　　 |　　　　　｀ ⌒´ﾉ 　　　挿入ソートのハイブリッドで、 　 .　　|　　　　　　　 }　　　　現実のデータに対して 　 .　　ヽ　　　　 　 }　　　　　非常に効率が良いんだ 　　　　 ヽ　　　　ノ 　　　　　/　　　 ヽ　　　　　　……まあ、それはまた別の話だな
55
　　　　　　____ 　　　　 ／　　 　＼ 　　　／　 ⌒　　⌒　＼ 　 ／ 　 （●） 　（●）　＼　　　次はTimsortを実装するお！ 　 |　　 　（__人__）　　　| 　 ＼　　　 ` ⌒´ 　 　／
56
　　　　　/ ￣￣＼ 　　　 ／　　 _ノ　＼ 　　　 |　　　（ ー）（ー） 　 .　　|　　　　 （__人__）　　　気が早いな…… 　　　 |　　　　　｀ ⌒´ﾉ 　　　まあ、その意気は買うが 　 .　　|　　　　　　　 } 　 .　　ヽ　　　　 　 }　　　　　 　　　　 ヽ　　　　ノ 　　　　　/　　　 ヽ
57
?????????????????????????????????????????? ?　おまけ：計算量の可視化　? ??????????????????????????????????????????
58
━━━ python ━━━ # complexity_comparison.py """ クイックソートの計算量を可視化するスクリプト """ import time import random import matplotlib.pyplot as plt from typing import List, Callable import numpy as np def measure_time(sort_func: Callable, data: List[int], iterations: int = 5) -> float: """ソート関数の実行時間を測定""" times = [] for _ in range(iterations): test_data = data.copy() start = time.perf_counter() sort_func(test_data) end = time.perf_counter() times.append(end - start) return np.median(times) # 計測 sizes = [100, 500, 1000, 2000, 3000, 5000] random_times = [] sorted_times = [] for n in sizes: # ランダムデータ random_data = list(range(n)) random.shuffle(random_data) random_times.append(measure_time(quicksort, random_data)) # ソート済みデータ（median-of-threeのおかげで安全） sorted_data = list(range(n)) sorted_times.append(measure_time(quicksort, sorted_data)) # プロット plt.figure(figsize=(10, 6)) plt.plot(sizes, random_times, 'b-o', label='ランダムデータ') plt.plot(sizes, sorted_times, 'r-s', label='ソート済みデータ') plt.xlabel('データサイズ (n)') plt.ylabel('実行時間 (秒)') plt.title('クイックソートの実行時間比較') plt.legend() plt.grid(True) plt.savefig('quicksort_performance.png', dpi=150) plt.show() ━━━━━━━━━━━━━━
59
【～ 完 ～】
今回の作品はキャプションの枠となっている部分が適当になっていたり、よくみるとAAがずれていたり、背景説明がそっけなかったり...というのがわかると思います。 次回ではこういった問題点を踏まえつつ、今回どのようにしてこの話を作ったか、改善点はどのような感じかをまとめていく方針です。 読者の皆様、ありがとうございました。