ChatGPT3.5を使って、ソートアルゴリズムの可視化のコードを作成しました。継続更新する予定

こんにちは！二度目の投稿です

今回のテーマはタイトルの通りです

説明

今回の記事では、ChatGPT 3.5を利用して、ソートアルゴリズムの可視化コードを完全にGPTに委ねて作成しました。実際、GPTは今年から注目を集めていますが、私は初版が2020年に発表された動画を最初に見て以来、ずっとその存在を知っていました。もうすぐchatGPTが一年になりますね。

普段のコードでエラーが発生し、Googleで調べても解決できない場合、私はGPTに質問して解決してもらっています。そこで、アルゴリズムが苦手な人や学びたい人に向けて、ソートアルゴリズムの可視化を見せることを考えました。もちろんネットで画像やスマホアプリもありますが、それでもできたら面白いと思ったんです。具体的なアイデアは、pygameを使用してホーム画面でアルゴリズムを選択し、スペースキーでソートアルゴリズムの可視化とその説明文も作成して表示するというものです。これらのアイデアをGPTに任せて実現しました。

会話のプロント多すぎるので一番最初の会話だけここで置きます

自分: ユーザーがpygameを利用してプログラム言語のアルゴリズムを勉強できるようなコード作ってください。

GPT: もちろんです！以下は、Pythonのpygameライブラリを使用して、ユーザーがアルゴリズムを学ぶためのシンプルなプログラムです。このプログラムでは、ランダムに生成された配列の要素をソートするアルゴリズムを視覚化します。ユーザーはプログラムを実行し、アルゴリズムがどのように動作するかを見ることができます。

import pygame
import sys
import random

# 初期設定
pygame.init()

# 画面サイズ
SCREEN_WIDTH = 800
SCREEN_HEIGHT = 600

# 色の定義
WHITE = (255, 255, 255)
BLACK = (0, 0, 0)
RED = (255, 0, 0)

# バーの設定
BAR_WIDTH = 10
BAR_HEIGHT = 300

# 配列の要素数
ARRAY_SIZE = 50

# 配列の初期化
array = [i for i in range(1, ARRAY_SIZE + 1)]
random.shuffle(array)

# バーの位置と高さを計算する関数
def calculate_bar_positions():
    bar_positions = []
    for i, value in enumerate(array):
        x = i * (SCREEN_WIDTH // ARRAY_SIZE)
        y = SCREEN_HEIGHT - value * (SCREEN_HEIGHT / ARRAY_SIZE)
        bar_positions.append((x, y, BAR_WIDTH, value * (SCREEN_HEIGHT / ARRAY_SIZE)))
    return bar_positions

# 描画関数
def draw_bars(screen, bar_positions):
    for x, y, width, height in bar_positions:
        pygame.draw.rect(screen, WHITE, (x, y, width, height))

# ソートアルゴリズム
def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                # バーの描画
                screen.fill(BLACK)
                draw_bars(screen, calculate_bar_positions())
                pygame.display.flip()
                pygame.time.delay(10)

# Pygameの初期化
screen = pygame.display.set_mode((SCREEN_WIDTH, SCREEN_HEIGHT))
pygame.display.set_caption("Algorithm Visualization")

# メインループ
running = True
while running:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            running = False

    # バーを描画
    screen.fill(BLACK)
    draw_bars(screen, calculate_bar_positions())
    pygame.display.flip()

    # ソート実行
    bubble_sort(array)

# Pygameの終了
pygame.quit()
sys.exit()

GPT: このプログラムでは、bubble_sort関数がバブルソートアルゴリズムを実装しています。アルゴリズムの各ステップで、バーの位置を計算し、描画しています。ユーザーはプログラムを実行し、バーがソートされる様子を可視化できます。

ソートアルゴリズム一覧表

by wikipedia まだ問題があります。修正していないです。

今回作成したアルゴリズムを丸付けました

使用チェック	名称	平均計算時間	最悪計算時間	メモリ使用量	安定性	手法	備考
○	バブルソート	(O(n^2))	(O(n^2))	(O(1))	○	交換
×	シェーカーソート	(O(n^2))	(O(n^2))	(O(1))	○	交換
×	コムソート	(O(n\log n))	(O(n^2))	(O(1))	×	交換	コードサイズが小さくて済む。
×	ノームソート	(O(n^2))	(O(n^2))	(O(1))	○	交換
○	選択ソート	(O(n^2))	(O(n^2))	(O(1))	×	選択	安定ソートとしても実装可能
×	挿入ソート	(O(n^2))	(O(n^2))	(O(1))	○	挿入	最良計算時間が (\Theta(n)) になる。
×	シェルソート	(O(n\log n))	(O(n^{1.5}))	(O(1))	×	挿入	最悪 (\Omega(n^{3/2})) や (\Omega(n^{4/3})) の数列が実用化されている。
×	2分木ソート	(O(n\log n))	(O(n\log n))	(O(n))	○	挿入	平衡2分探索木を使った場合
×	図書館ソート	(O(n\log n))	(O(n^2))	(O(n))	○	挿入
×	マージソート	(O(n\log n))	(O(n\log n))	( (n))	○	マージ	連結リストの場合は (O(1)) 外部メモリ。
×	In-place マージソート	(O(n\log^2 n))	(O(n\log^2 n))	(O(1))	○	マージ	実装例
×	ヒープソート	(O(n\log n))	(O(n\log n))	(O(1))	×	選択
×	スムースソート	—	(O(n\log n))	(O(1))	×	選択
○	クイックソート	(O(n\log n))	(O(n^2))	(O(\log n))	×	パーティショニング	メモリはコールスタック（素朴な実装では (\Omega(n)) になる）
○	イントロソート	(O(n\log n))	(O(n\log n))	(O(\log n))	×	混成	メモリはコールスタック
×	ペイシェンスソート	—	(O(n^2))	(O(n))	×	挿入	(O(n\log n)) 以内にすべての最長増加部分列を探す。
×	ストランドソート	(O(n\log n))	(O(n^2))	(O(n))	○	選択
○	奇偶転置ソート	(O(n^2))	(O(n^2))	(O(1))	○	交換
×	シェアソート	(O(n^{1.5}))	(O(n^{1.5}))	(O(1))	×	交換

動作動画です

GPT が作成したコードです

11/19 アップロード日

import pygame
import sys
import random
import threading
import math

# 初期設定
pygame.init()

# 画面サイズ
SCREEN_WIDTH = 800
SCREEN_HEIGHT = 600
BAR_NUMBER_HEIGHT = 20  # バーの下に表示される番号の高さ

# 色の定義
WHITE = (255, 255, 255)
BLACK = (0, 0, 0)
RED = (255, 0, 0)
GREEN = (0, 255, 0)

# バーの設定
BAR_WIDTH = 10
BAR_HEIGHT = 300

# 配列の要素数
ARRAY_SIZE = 50

# 配列の初期化
array = [i for i in range(1, ARRAY_SIZE + 1)]
random.shuffle(array)

# バブルソートの説明文
bubble_sort_description = [
    "バブルソートは、隣接する要素を比較し",
    "順序が逆であれば交換するという",
    "単純なソートアルゴリズムです。",
    "リスト全体を通過する操作を繰り返し",
    "リストがソートされるまでこれを行います。",
]

# 選択ソートの説明文
selection_sort_description = [
    "選択ソートは、リストから最小値を探し出し",
    "それをリストの先頭と交換することを繰り返す",
    "単純なソートアルゴリズムです。",
    "リスト全体を通過する操作を繰り返し",
    "リストがソートされるまでこれを行います。",
]

# クイックソートの説明文
quick_sort_description = [
    "クイックソートは、分割統治法を基にした",
    "効率の高いソートアルゴリズムです。",
    "基準となる要素（ピボット）を選び、",
    "ピボットを基準にして配列を分割し、",
    "それぞれの部分を再帰的にソートします。",
]
# イントロソートの説明文
intro_sort_description = [
    "イントロソートは、クイックソートとヒープソートを",
    "組み合わせたソートアルゴリズムです。",
    "クイックソートを使用し、再帰の深さが一定以上に",
    "なるとヒープソートに切り替えます。",
]


# bubble_sortアルゴリズム
def bubble_sort(arr, screen, lock, description_y, description):
    n = len(arr)
    for i in range(n - 1):
        for j in range(0, n - i - 1):
            # 赤色で比較対象を表示
            compare_indices = [j, j + 1]
            swap_indicator = None
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                # スワップを示す矢印の位置
                swap_indicator = (
                    j * (SCREEN_WIDTH // ARRAY_SIZE) + BAR_WIDTH // 2,
                    SCREEN_HEIGHT
                    - max(arr[j], arr[j + 1]) * (SCREEN_HEIGHT / ARRAY_SIZE),
                )
            # バーの描画
            with lock:
                screen.fill(BLACK)
                draw_bars(
                    screen,
                    calculate_bar_positions(),
                    compare_indices,
                    swap_indicator,
                    list(range(n - i, n)),  # ソートが終わったバーの番号
                )
                pygame.display.flip()
                pygame.time.delay(50)
                # 元の色に戻す
                compare_indices = []
                screen.fill(BLACK)
                draw_bars(
                    screen,
                    calculate_bar_positions(),
                    compare_indices,
                    None,
                    list(range(n - i, n)),
                )
                pygame.display.flip()

    with lock:
        # 説明文を表示
        description_y = draw_description(screen, bubble_sort_description)
        pygame.display.flip()
        # 描画が終わった後に「mキーで戻る」を表示
        font = pygame.font.Font("C:/Windows/Fonts/HGRPP1.TTC", 22)
        text = font.render("mキーで戻る", True, WHITE)
        screen.blit(text, (10, description_y))
        pygame.display.flip()


# selection_sortアルゴリズム
def selection_sort(arr, screen, lock, description_y, description):
    n = len(arr)
    for i in range(n):
        min_index = i
        for j in range(i + 1, n):
            # 赤色で比較対象を表示
            compare_indices = [min_index, j]
            if arr[min_index] > arr[j]:
                min_index = j
            # バーの描画
            with lock:
                screen.fill(BLACK)
                draw_bars(
                    screen,
                    calculate_bar_positions(),
                    compare_indices,
                    None,
                    list(range(i, n)),  # ソートが終わったバーの番号
                )
                pygame.display.flip()
                pygame.time.delay(50)
                # 元の色に戻す
                compare_indices = []
                screen.fill(BLACK)
                draw_bars(
                    screen,
                    calculate_bar_positions(),
                    compare_indices,
                    None,
                    list(range(i, n)),
                )
                pygame.display.flip()

        # 最小値を見つけたら交換
        arr[i], arr[min_index] = arr[min_index], arr[i]
        # バーの描画（交換後）
        with lock:
            screen.fill(BLACK)
            draw_bars(
                screen,
                calculate_bar_positions(),
                [i, min_index],
                (i * (SCREEN_WIDTH // ARRAY_SIZE) + BAR_WIDTH // 2, SCREEN_HEIGHT),
                list(range(i, n)),  # ソートが終わったバーの番号
            )
            pygame.display.flip()
            pygame.time.delay(50)
            # 元の色に戻す
            screen.fill(BLACK)
            draw_bars(
                screen,
                calculate_bar_positions(),
                [],
                None,
                list(range(i, n)),
            )
            pygame.display.flip()

    with lock:
        # 説明文を表示
        description_y = draw_description(screen, selection_sort_description)
        pygame.display.flip()
        # 描画が終わった後に「mキーで戻る」を表示
        font = pygame.font.Font("C:/Windows/Fonts/HGRPP1.TTC", 22)
        text = font.render("mキーで戻る", True, WHITE)
        screen.blit(text, (10, description_y))
        pygame.display.flip()


# quick_sortアルゴリズム
def quick_sort(arr, screen, lock, description_y, description):
    def partition(arr, low, high):
        i = low - 1
        pivot = arr[high]

        for j in range(low, high):
            # 赤色で比較対象を表示
            compare_indices = [j, high]
            # バーの描画
            with lock:
                screen.fill(BLACK)
                draw_bars(
                    screen,
                    calculate_bar_positions(),
                    compare_indices,
                    None,
                    list(range(low + 1, high + 1)),  # ソート範囲を修正
                )
                pygame.display.flip()
                pygame.time.delay(50)
                # 元の色に戻す
                compare_indices = []
                screen.fill(BLACK)
                draw_bars(
                    screen,
                    calculate_bar_positions(),
                    compare_indices,
                    None,
                    list(range(low + 1, high + 1)),  # ソート範囲を修正
                )
                pygame.display.flip()

            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

    def quick_sort_recursive(arr, low, high):
        if low < high:
            pi = partition(arr, low, high)

            quick_sort_recursive(arr, low, pi - 1)
            quick_sort_recursive(arr, pi + 1, high)

    n = len(arr)
    quick_sort_recursive(arr, 0, n - 1)

    with lock:
        # ソートが完了した後に説明文を表示
        description_y[0] = draw_description(screen, description)
        pygame.display.flip()
        # 描画が終わった後に「mキーで戻る」を表示
        font = pygame.font.Font("C:/Windows/Fonts/HGRPP1.TTC", 22)
        text = font.render("mキーで戻る", True, WHITE)
        screen.blit(text, (10, description_y[0]))
        pygame.display.flip()

    # ソートが完了した後にリストを表示
    print("After Quick Sort:", arr)


# イントロソートアルゴリズム
def intro_sort(arr, screen, lock, description_y, description):
    def partition(arr, low, high, screen, lock):
        i = low - 1
        pivot = arr[high]

        for j in range(low, high):
            compare_indices = [j, high]
            with lock:
                screen.fill(BLACK)
                draw_bars(
                    screen,
                    calculate_bar_positions(),
                    compare_indices,
                    None,
                    list(range(low + 1, high + 1)),
                )
                pygame.display.flip()
                pygame.time.delay(50)
                compare_indices = []
                screen.fill(BLACK)
                draw_bars(
                    screen,
                    calculate_bar_positions(),
                    compare_indices,
                    None,
                    list(range(low + 1, high + 1)),
                )
                pygame.display.flip()

            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

    def quick_sort_recursive(arr, low, high, depth_limit, screen, lock):
        if low < high:
            if depth_limit == 0:
                heap_sort(arr, low, high, screen, lock)
                return
            depth_limit -= 1
            pi = partition(arr, low, high, screen, lock)
            quick_sort_recursive(arr, low, pi - 1, depth_limit, screen, lock)
            quick_sort_recursive(arr, pi + 1, high, depth_limit, screen, lock)

    def heap_sort(arr, low, high, screen, lock):
        n = high - low + 1
        for i in range(n // 2 - 1, -1, -1):
            heapify(arr, n, i, low, screen, lock)

        for i in range(n - 1, 0, -1):
            arr[i + low], arr[0] = arr[0], arr[i + low]
            heapify(arr, i, 0, low, screen, lock)

    def heapify(arr, n, i, low, screen, lock):
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2

        if left < n and arr[left + low] > arr[largest + low]:
            largest = left

        if right < n and arr[right + low] > arr[largest + low]:
            largest = right

        if largest != i:
            arr[i + low], arr[largest + low] = arr[largest + low], arr[i + low]
            with lock:
                screen.fill(BLACK)
                draw_bars(
                    screen,
                    calculate_bar_positions(),
                    [i + low, largest + low],
                    (
                        i * (SCREEN_WIDTH // ARRAY_SIZE) + BAR_WIDTH // 2,
                        SCREEN_HEIGHT,
                    ),
                    list(range(low, n + low)),
                )
                pygame.display.flip()
                pygame.time.delay(50)
                screen.fill(BLACK)
                draw_bars(
                    screen,
                    calculate_bar_positions(),
                    [],
                    None,
                    list(range(low, n + low)),
                )
                pygame.display.flip()
            heapify(arr, n, largest, low, screen, lock)

    n = len(arr)
    depth_limit = 2 * int(math.log2(n))
    quick_sort_recursive(arr, 0, n - 1, depth_limit, screen, lock)

    with lock:
        description_y[0] = draw_description(screen, description)
        pygame.display.flip()
        font = pygame.font.Font("C:/Windows/Fonts/HGRPP1.TTC", 22)
        text = font.render("mキーで戻る", True, WHITE)
        screen.blit(text, (10, description_y[0]))
        pygame.display.flip()

    print("After Intro Sort:", arr)


"""
# 説明文表示関数
def draw_description(screen, description, description_y):
    font = pygame.font.Font("C:/Windows/Fonts/HGRPP1.TTC", 22)
    y = 10
    for line in description:
        text = font.render(line, True, WHITE)
        screen.blit(text, (10, y))
        y += text.get_height() + 5
    description_y[0] = y  # 描画が終わった後のy座標を更新
"""


# 説明文表示関数
def draw_description(screen, description):
    font = pygame.font.Font("C:/Windows/Fonts/HGRPP1.TTC", 22)
    y = 10
    for line in description:
        text = font.render(line, True, WHITE)
        screen.blit(text, (10, y))
        y += text.get_height() + 5
    return y  # 描画が終わった後のy座標を返す


# バーの位置と高さを計算する関数
def calculate_bar_positions():
    bar_positions = []
    for i, value in enumerate(array):
        x = i * (SCREEN_WIDTH // ARRAY_SIZE)
        y = SCREEN_HEIGHT - value * (SCREEN_HEIGHT / ARRAY_SIZE)
        bar_positions.append((x, y, BAR_WIDTH, value * (SCREEN_HEIGHT / ARRAY_SIZE)))
    return bar_positions


# 描画関数
def draw_bars(screen, bar_positions, compare_indices, swap_indicator, sorted_indices):
    font = pygame.font.Font("C:/Windows/Fonts/HGRPP1.TTC", 15)  # 日本語フォントを指定
    for i, (x, y, width, height) in enumerate(bar_positions):
        color = RED if i in compare_indices else GREEN if i in sorted_indices else WHITE
        pygame.draw.rect(screen, color, (x, y, width, height))
        text = font.render(str(array[i]), True, color)
        text_rect = text.get_rect(
            center=(x + width // 2, y + height + BAR_NUMBER_HEIGHT // 2)
        )
        screen.blit(text, text_rect)

    # スワップを示す矢印を描画
    if swap_indicator is not None:
        arrow_x, arrow_y = swap_indicator
        pygame.draw.polygon(
            screen,
            RED,
            [(arrow_x, arrow_y - 20), (arrow_x - 10, arrow_y), (arrow_x + 10, arrow_y)],
        )


# メインメニュー表示関数
def draw_main_menu(screen):
    font = pygame.font.Font("C:/Windows/Fonts/HGRPP1.TTC", 28)
    menu_text = font.render("1: バブルソート", True, WHITE)
    screen.blit(
        menu_text,
        (SCREEN_WIDTH // 2 - menu_text.get_width() // 2, SCREEN_HEIGHT // 2 - 50),
    )
    selection_sort_text = font.render("2: 選択ソート", True, WHITE)
    screen.blit(
        selection_sort_text,
        (
            SCREEN_WIDTH // 2 - selection_sort_text.get_width() // 2,
            SCREEN_HEIGHT // 2,
        ),
    )
    quick_sort_text = font.render("3: クイックソート", True, WHITE)
    screen.blit(
        quick_sort_text,
        (
            SCREEN_WIDTH // 2 - quick_sort_text.get_width() // 2,
            SCREEN_HEIGHT // 2 + 50,
        ),
    )
    intro_sort_text = font.render("4: イントロソート", True, WHITE)
    screen.blit(
        intro_sort_text,
        (
            SCREEN_WIDTH // 2 - intro_sort_text.get_width() // 2,
            SCREEN_HEIGHT // 2 + 100,
        ),
    )


# 説明文表示関数
def draw_description(screen, description):
    font = pygame.font.Font("C:/Windows/Fonts/HGRPP1.TTC", 22)
    y = 10
    for line in description:
        text = font.render(line, True, WHITE)
        screen.blit(text, (10, y))
        y += text.get_height() + 5
    return y  # 描画が終わった後のy座標を返す


# ロックオブジェクト
lock = threading.Lock()

# Pygameの初期化
screen = pygame.display.set_mode((SCREEN_WIDTH, SCREEN_HEIGHT + BAR_NUMBER_HEIGHT))
pygame.display.set_caption("アルゴリズムの可視化")

# メインループ
running = True
sorting = False
selected_algorithm = None
description_y = [0]
lock = threading.Lock()
while running:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            running = False
        elif event.type == pygame.KEYDOWN:
            if sorting:
                if event.key == pygame.K_m:  # mが押されたらメインメニューに戻る
                    sorting = False
                    array = [i for i in range(1, ARRAY_SIZE + 1)]
                    random.shuffle(array)
            else:
                if event.key == pygame.K_1:  # 1が押されたらバブルソートを実行
                    sorting = True
                    selected_algorithm = bubble_sort
                    # バブルソートの実行
                    threading.Thread(
                        target=selected_algorithm,
                        args=(
                            array,
                            screen,
                            lock,
                            description_y,
                            bubble_sort_description,
                        ),
                    ).start()
                elif event.key == pygame.K_2:  # 2が押されたら選択ソートを実行
                    sorting = True
                    selected_algorithm = selection_sort
                    # 選択ソートの実行
                    threading.Thread(
                        target=selected_algorithm,
                        args=(
                            array,
                            screen,
                            lock,
                            description_y,
                            selection_sort_description,
                        ),
                    ).start()
                elif event.key == pygame.K_3:  # 3が押されたらクイックソートを実行
                    sorting = True
                    selected_algorithm = quick_sort
                    # クイックソートの実行
                    threading.Thread(
                        target=selected_algorithm,
                        args=(
                            array,
                            screen,
                            lock,
                            description_y,
                            quick_sort_description,
                        ),
                    ).start()
                elif event.key == pygame.K_4:  # 4が押されたらクイックソートを実行
                    sorting = True
                    selected_algorithm = intro_sort
                    # クイックソートの実行
                    threading.Thread(
                        target=selected_algorithm,
                        args=(
                            array,
                            screen,
                            lock,
                            description_y,
                            intro_sort_description,
                        ),
                    ).start()

    if not sorting:
        # メインメニューを表示
        screen.fill(BLACK)
        draw_main_menu(screen)
        pygame.display.flip()

# Pygameの終了
pygame.quit()
sys.exit()

最後

これから時間があったら、継続更新する予定です。
最後まで見てくれてありがとうございます。
bug はまだ大量存在しています。。。