基本情報技術者試験のアルゴリズム対策を始めましたので、基礎的なソートプログラムをPythonで書いてみました。下記コードを実行すれば同じようなグラフが描画できると思います。間違いがあればご指摘していただければ幸いです。

使用した言語/ツール

Python
Jupyter Notebook

今回登場するソートアルゴリズム

バブルソート
選択ソート
挿入ソート
シェルソート

まずは結果のグラフ

xは32, 64, 128, 256, 512, 1024, 2048, 4096, 8192個のランダムな数値(1から50000)が入ったリストです。
縦軸には実行時間をとっています。

コード

間違いがあれば指摘していただければ幸いです。

import copy
import random
import time


def bubble_sort(list_data):
    start = time.time()
    sample_data = copy.copy(list_data)
    for h in range(len(sample_data)):
        for i in range(len(sample_data)-1):

            if sample_data[i] > sample_data[i+1]:
                a = sample_data[i]
                b = sample_data[i+1]
                sample_data[i] = b
                sample_data[i+1] = a
    end = time.time()
    result = end - start
    return sample_data, result


def selection_sort(list_data):
    start = time.time()
    sample_data = copy.copy(list_data)
    for h in range(len(sample_data)):
        m = 0
        for i in range(len(sample_data)-h):
            if sample_data[m] < sample_data[i]:
                m = i
            if i == len(sample_data)-1-h:
                work = sample_data[i]
                sample_data[i] = sample_data[m]
                sample_data[m] = work
                continue

    end = time.time()
    result = end - start
    return sample_data, result


def insertion_sort(list_data):
    start = time.time()
    sample_data = copy.copy(list_data)
    for i in range(1, len(sample_data)):
        if sample_data[i-1] > sample_data[i]:
            j = i
            while j > 0 and sample_data[j-1] > sample_data[j]:
                work = sample_data[j]
                sample_data[j] = sample_data[j-1]
                sample_data[j-1] = work
                j -= 1

    end = time.time()
    result = end - start
    return sample_data, result


def shell_sort(list_data):
    start = time.time()
    sample_data = copy.copy(list_data)

    h = 1
    while h < len(sample_data) / 9:
        h = h * 3 + 1

    while h > 0:
        for i in range(h, len(sample_data)):
            if sample_data[i-h] > sample_data[i]:
                j = i
                while j > 0 and sample_data[j-h] > sample_data[j]:
                    work = sample_data[j]
                    sample_data[j] = sample_data[j-h]
                    sample_data[j-h] = work
                    j -= 1

        h = h // 3

    end = time.time()
    result = end - start
    return sample_data, result


time_bubble = list()
time_selection = list()
time_insertion = list()
time_shell = list()
for i in range(5,14):
    num = 2**i
    print(num)
    random.seed(1)
    samples = random.sample(range(1, 50000), k=num)
    time_bubble.append(round(bubble_sort(samples)[1], 5))
    time_selection.append(round(selection_sort(samples)[1], 5))
    time_insertion.append(round(insertion_sort(samples)[1], 5))
    time_shell.append(round(shell_sort(samples)[1], 5))

# print("{:<16}".format("bubble"), time_bubble)
# print("{:<16}".format("selection"), time_selection)
# print("{:<16}".format("insertion"), time_insertion)
# print("{:<16}".format("shell"), time_shell)

グラフの描画

%matplotlib inline

import numpy as np
import matplotlib.pyplot as plt

x = [32, 64, 128, 256, 512, 1024, 2048, 4096, 8192]
y_bubble = time_bubble
y_selection = time_selection
y_insertion = time_insertion
y_shell = time_shell

plt.title("sort time")
plt.xlabel("len(list)")
plt.ylabel("time(s)")
plt.plot(x, y_bubble, label="bubble")
plt.plot(x, y_selection, label="slection")
plt.plot(x, y_insertion, label="insertion")
plt.plot(x, y_shell, label="shell")
plt.legend()

上のコードの数値を変えれば数字の個数を変更できます。

現在は2の5乗から2の13乗までになっています。

for i in range(5,14):
    num = 2**i
    print(num)
    random.seed(1)
    samples = random.sample(range(1, 50000), k=num)

今回わかったこと

個数が多いとシェルソートは速い。
シェルは開発者の名前。
こういう作業はJupyter Notebookを使うと調子がいいとわかった。

おわりに

実行する環境によって細かな描画が変わってくると思います。ご了承ください。