Help us understand the problem. What is going on with this article?

Pythonで基礎的なソートアルゴリズムの実行時間をグラフ化して比べる

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

使用した言語/ツール

  • Python
  • Jupyter Notebook

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

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

まずは結果のグラフ

figure.png

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を使うと調子がいいとわかった。

おわりに

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

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away