Jupyter による学生レポート例（ソートアルゴリズムの性能比較）¶
学生番号:
氏名:
参考: https://flogics.com/wp/ja/2019/11/technical-report-by-jupyter-notebook
今回は、データのソート（整列）アルゴリズムのうち、初歩的なバブルソート法と、実用でよく用いられるクイックソート法のアルゴリズムを Python 言語で実装し、その性能（実行時間）を比較してみた。その際、データの数を変えながら、実行時間を図示してみたい。
指導者註: 実際には Python のリスト構造を使ってソーティングをするのは、効率の良いものではありません。NumPy の array を使って書き直し、結果がどのように違うか比べるのも勉強になるでしょう。また、Python 組込の sort() メソッドを使った場合の性能と比べてみるのも良いでしょう。
データの準備¶
今回は、3種類のテスト用データ（長さ N）を用意する。なお、後で実行するソーティングの方向は、昇順ソートとする。
- data_sorted（初めからソート済み）
- data_inversed（初めは完全に逆順）
- data_random（ランダムなデータ）
In [1]:
N = 1000 # データの長さ
RANDOM_SEED = 1 # 乱数の種
import random
random.seed(RANDOM_SEED)
data_sorted = []
data_inversed = []
data_random = []
for i in range(N):
data_sorted.append(i)
data_inversed.append(N - i - 1)
data_random.append(random.randint(0, N / 2)) # 同じデータが生じるように、範囲を 0〜N / 2 とする
データを目視する¶
In [2]:
N_PART = 10
print("data_sorted:", data_sorted[:N_PART])
print("data_inversed: ", data_inversed[:N_PART])
print("data_random:", data_random[:N_PART])
テスト用関数を定義する¶
データが正しくソートされているか否かをテストする関数を定義しておく。
In [3]:
def test_sorted(array):
for i in range(1, len(array)):
if array[i] < array[i - 1]:
print("Error found at array[{}].".format(i))
return False
print("Test passed.")
return True
関数 test_sorted() が正しく動作しているかテスト¶
In [4]:
assert(test_sorted(data_sorted) == True)
In [5]:
assert(test_sorted(data_inversed) == False)
In [6]:
assert(test_sorted(data_random) == False)
ソート用関数を定義する¶
バブルソート法¶
In [7]:
def bubble_sort(orig_array):
array = orig_array.copy()
n = len(array)
swapped = True
while swapped:
swapped = False
for i in range(1, n):
if array[i - 1] > array[i]:
array[i - 1], array[i] = array[i], array[i - 1]
swapped = True
n -= 1
return array
テストしてみる¶
In [8]:
assert(test_sorted(bubble_sort(data_sorted)))
In [9]:
assert(test_sorted(bubble_sort(data_inversed)))
In [10]:
assert(test_sorted(bubble_sort(data_random)))
In [11]:
def partition(array, lo, hi):
pivot = array[hi]
i = lo
for j in range(lo, hi + 1):
if array[j] < pivot:
array[i], array[j] = array[j], array[i]
i += 1
array[i], array[hi] = array[hi], array[i]
return i
def qs(array, lo, hi):
if lo < hi:
p = partition(array, lo, hi)
qs(array, lo, p - 1)
qs(array, p + 1, hi)
def quicksort(orig_array):
array = orig_array.copy()
qs(array, 0, len(array) - 1)
return array
テストしてみる¶
In [12]:
assert(test_sorted(quicksort(data_sorted)))
In [13]:
assert(test_sorted(quicksort(data_inversed)))
In [14]:
assert(test_sorted(quicksort(data_random)))
長さを変えながら性能を測定する¶
今回は簡単のため、ランダムデータのみ測定する。
In [15]:
N_SPLIT = 10 # データの長さを何種類試すか
N_TRIALS = 10 # ソートの時間測定を何回試行するか
%matplotlib inline
import matplotlib.pyplot as plt
import time
x_series = []
time_bubble = []
time_quick = []
for i in range(1, N_SPLIT + 1):
length = i * (N // N_SPLIT)
x_series.append(length)
# バブルソート法
start = time.time()
for j in range(N_TRIALS):
bubble_sort(data_random[:length])
end = time.time()
time_bubble.append((end - start) / N_TRIALS)
# クイックソート法
start = time.time()
for j in range(N_TRIALS):
quicksort(data_random[:length])
end = time.time()
time_quick.append((end - start) / N_TRIALS)
2つのソート法の所要時間を比較する¶
In [16]:
fig = plt.figure(figsize=(20, 5))
ax = fig.subplots()
ax.grid(True)
ax.set_xlabel("Number of Data")
ax.set_ylabel("Consumed Time [seconds]")
ax.plot(x_series, time_bubble, label="Bubble Sort")
ax.plot(x_series, time_quick, label="Quicksort")
ax.legend()
plt.show()
クイックソート法だけプロットする¶
バブルソート法では、データ数が増えると指数的に実行時間が増えているように見えるが、クイックソート法ではどうか。
参考: バブルソート法の演算量は平均で $O(n^2)$ であり、クイックソート法は $O(n\log n)$ とされている。
In [17]:
fig = plt.figure(figsize=(20, 5))
ax = fig.subplots()
ax.grid(True)
ax.set_xlabel("Number of Data")
ax.set_ylabel("Consumed Time [seconds]")
# ax.plot(x_series, time_bubble, label="Bubble Sort")
ax.plot(x_series, time_quick, label="Quicksort")
ax.legend()
plt.show()
考察¶
（略）