Week 8 (2025/6/6)¶

今週の目的

分割統治法を用いてデータを昇順・降順に並べ替える。

今週のキーワード

ヒープを用いたヒープソート
分割統治法を用いたマージソートとクイックソート

今回はソートアルゴリズムとしてヒープソートと、マージソート、クイックソートを実装する。

課題1：ヒープでデータを並べ替える¶

前回に作成したDBクラス（親クラス）を継承したDBwHeapSortクラス（子クラス）を定義し、sortメソッドを「ヒープソートアルゴリズム」で実装せよ。なお、DBクラスはdef_db.pyモジュールのDBクラスをインポートして用いること。

今回作成するDBwHeapSortクラスの仕様は、以下の通りである。

DBwHeapSortクラス

class DBwHeapSort() DBクラスのサブクラス
格納したデータをヒープソートで並べ替えるクラス

インスタンス変数

heap: ヒープソートで用いるヒープ
queue: ヒープソートで用いるキュー

sort()
リストの中身をヒープソートで昇順に並べ替えるメソッド

なお、ヒープソートの実装には、def_heap.pyモジュールのHeapクラスとそのメソッドを用いる。Heapクラスの各メソッドの仕様はWeek8を参照すること。

まず、build_heapメソッドを用いて、DBwHeapSortインスタンス内のリストからヒープを構成し、その後、delete_minメソッドを繰り返して、値の小さいものから順にヒープから取り出す。取り出したデータはキュー（def_queue_stack.pyモジュールを用いてよい）にenqueueし、全てのデータをenqueueした後に、dequeueでデータを取り出しDBwHeapSortインスタンス内のリストに再格納する。

最後に、実装したDBwHeapSortクラスのインスタンスを用いて、allkyotobus_stop.datのデータをバス停の経度の小さい順（西から東に）に並べ替えて、その結果と実行時間を表示せよ。

プログラム実行例

week8_1.py
# 穴埋め問題用のプログラム
from def_stop import Stop  # Stopクラスの読み込み
from def_heap import Heap  # Heapクラスの読み込み
from def_queue_stack import Queue  # Queueクラスの読み込み
from def_db import DB  # DBクラスの読み込み
import time  # 実行時間を計測するためのモジュール


class DBwHeapSort(DB):  # ヒープソート用のクラス
    def __init__(self):
        super().__init__()  # 親クラスの__init()__の呼び出し
        self.heap = [____]  # ヒープのインスタンスを生成
        self.queue = [____]  # キューのインスタンスを生成

    def sort(self):
        self.heap.[____]  # self.listからヒープを構築
        min = self.heap.[____]  # ヒープの根を取得する
        while min is not [____]:  # ヒープの根が取得できる限り繰り返す
            self.queue.[____](min)  # ヒープの根をキューに追加
            min = self.heap.[____]  # ヒープの根を取得する
        i = 0
        min = self.queue.[____]  # キューからデータを取り出す
        while min is not [____]:  # キューからデータを取り出せる限り繰り返す
            self.list[i] = min  # 取り出したデータをDBのリストに追加する
            i += 1
            min = self.queue.[____]  # キューからデータを取り出す


if __name__ == '__main__':  # モジュールとしてインポートされるときは実行しない
    fi = open('allkyotobus_stop.dat', 'r', encoding='utf-8')
    lines = fi.readlines()
    db = DBwHeapSort()
    for line in lines:
        line = line.rstrip()
        items = line.split(' ')  # 1行を半角スペースで区切ってitemsリストに代入
        db.add(Stop(items[0], items[1], float(items[2]), float(items[3]), items[4:]))  # Stopオブジェクトを各DBインスタンスに追加
    start = time.time()  # ソート前の時間を記録（time()は現在時刻を返すメソッド）
    db.sort()  # データのソートを実行
    elapsed_time = time.time() - start  # ソート後の時間からソート前の時間を引き実行時間計測
    db.display()
    if db.is_sorted():
        print("ソートが完了しました！{}は{}秒かかりました。".format(db.__class__.__name__, elapsed_time))  # __class__はインスタンスのクラスを返し、__name__はそのクラスの名前を返す
    fi.close()

1: 下夜久野駅前(ID:ED01_85)のバス停の緯度経度は(35.32033486,134.99883496)です。
2: 畑口(ID:ED01_86)のバス停の緯度経度は(35.32009052,135.00174923)です。
（中略）
1849: 自治会館前(ID:ED01_2850)のバス停の緯度経度は(34.86017838,135.89218112)です。
1850: 緑苑坂東(ID:ED01_2851)のバス停の緯度経度は(34.86244101,135.89352647)です。
ソートが完了しました！DBwHeapSortは0.03531908988952637秒かかりました。

課題2：データを並べ替える（マージソート）¶

課題1に作成したDBクラス（親クラス）を継承し、DBwMergeSortクラス（子クラス）を定義して、sortメソッドを「マージソートアルゴリズム」で実装せよ。

今回作成するDBwMergeSortクラスの仕様は、以下の通りである。

DBwMergeSortクラス

class DBwMergeSort() DBクラスのサブクラス
格納したデータをマージソートで並べ替えるクラス

sort() リストの中身をマージソートで昇順に並べ替えるメソッド

最後に、実装したクラスのインスタンスを用いて、allkyotobus_stop.datのデータをバス停の経度の小さい順（西から東に）に並べ替えて、その結果と実行時間を表示せよ。

実行例

1: 下夜久野駅前(ID:ED01_85)のバス停の緯度経度は(35.32033486,134.99883496)です。
2: 畑口(ID:ED01_86)のバス停の緯度経度は(35.32009052,135.00174923)です。
（中略）
1849: 自治会館前(ID:ED01_2850)のバス停の緯度経度は(34.86017838,135.89218112)です。
1850: 緑苑坂東(ID:ED01_2851)のバス停の緯度経度は(34.86244101,135.89352647)です。
ソートが完了しました！DBwMergeSortは0.013421058654785156秒かかりました。

課題3：データを並べ替える（クイックソート）¶

課題1で作成したDBクラス（親クラス）を継承し、DBwQuickSortクラス（子クラス）を定義して、sortメソッドを「クイックソートアルゴリズム」で実装せよ。

今回作成するDBwQuickSortクラスの仕様は、以下の通りである。

DBwQuickSortクラス

class DBwQuickSort() DBクラスのサブクラス
格納したデータをクイックソートで並べ替えるクラス

sort()
リストの中身をクイックソートで昇順に並べ替えるメソッド

最後に、実装したクラスのインスタンスを用いて、allkyotobus_stop.datのデータをバス停の経度の小さい順（西から東に）に並べ替えて、その結果と実行時間を表示せよ。

実行例

1: 下夜久野駅前(ID:ED01_85)のバス停の緯度経度は(35.32033486,134.99883496)です。
2: 畑口(ID:ED01_86)のバス停の緯度経度は(35.32009052,135.00174923)です。
（中略）
1849: 自治会館前(ID:ED01_2850)のバス停の緯度経度は(34.86017838,135.89218112)です。
1850: 緑苑坂東(ID:ED01_2851)のバス停の緯度経度は(34.86244101,135.89352647)です。
ソートが完了しました！DBwQuickSortは0.008417844772338867秒かかりました。

発展課題4：データの並べ替え時間を比較する¶

これまで実装したDBwBubbleSortクラス、DBwSelectSortクラス、DBwInsertSortクラス、DBwHeapSortクラス、DBwMergeSortクラス、DBwQuickSortクラスの各インスタンスを用いて、allkyotobus_stop.datのデータをバス停の経度の小さい順（西から東に）に並べ替えて、その実行時間を表示せよ。本課題は、実装が異なると実行速度が変わることを理解することが目的である。

実行例

ソートが完了しました！DBwBubbleSortは0.6107010841369629秒かかりました。
ソートが完了しました！DBwSelectSortは0.3105299472808838秒かかりました。
ソートが完了しました！DBwInsertSortは0.1937861442565918秒かかりました。
ソートが完了しました！DBwHeapSortは0.024415016174316406秒かかりました。
ソートが完了しました！DBwMergeSortは0.009604930877685547秒かかりました。
ソートが完了しました！DBwQuickSortは0.009488821029663086秒かかりました。