仕事で急遽並び替えアルゴリズムを教える(?)事になったので、そのまとめを書き連ねていこうと思います。
クイックソートの関数
私が教えるところの要領によれば交換回数と時間を分析するとの事なので、まずクイックソートの関数には交換回数を付け加えました。
元のクイックソートのアルゴリズムはこちらのサイトを参考にしました。
(っていうかここ最近違う分野やっていたので基礎的なアルゴリズムやるの大学生以来です)
def quick(a, first, last):
cnt = 0
pivot = a[(first + last) // 2]
i = first
j = last
while True:
while a[i] < pivot:
i = i + 1
while pivot < a[j]:
j = j - 1
if i >= j:
break
temp = a[i]
a[i] = a[j]
a[j] = temp
cnt = cnt + 1
i = i + 1
j = j - 1
if first < (i - 1):
cnt = cnt + quick(a, first, i-1)
if (j + 1) < last:
cnt = cnt + quick(a, j+1, last)
return cnt
ChatGPTにはいろいろ文句を言われましたが企業さんの公式のアルゴリズムが教材(C++)と同じ内容になっていたのでとりあえず上記関数を使用します。
特殊配列
ここからは、クイックソートにおける基準値(pivot)がある条件で
O(N logN)
が
O(N^2)
になり得る可能性のある配列を探します。
当日の実験では「谷型配列」と「のこぎり型配列」「ランダム配列」「昇順配列」「降順配列」がありますが後者3つは目に見えているので今回は「谷型配列」と「のこぎり型配列」を考えてみます。
ここで、
O(N^2)
になるのは基準値が配列の中でとてもに小さいまたはとても大きい値が最悪時の計算になります。
谷型配列(V字)
谷型配列(V字)は
array = [10, 8, 6, 4, 2, 1, 3, 5, 7, 9]
といった感じで両端に行くほど値が大きく真ん中が最小値になる配列です。
def voly_array(n):
a = []
for i in range(n, 0, -2):
a.append(i)
for i in range(1, n, 2):
a.append(i)
return a
谷型配列(大きい値群から小さい値群へ)
ちょっとどう日本語に言語化すればいいか分からない(というか英語はもっと苦手だが)のでとりあえず配列のサンプルを以下に記します。
a = [5, 6, 7, 8, 9, 0, 1, 2, 3, 4]
といった感じで最初から真ん中までnの半分の値から最大値nまで単調増加して真ん中から急に値が最小値になり、そこから値が単調増加する配列になります。
def voly2_array(n):
a = []
for i in range(n//2, n):
a.append(i)
for i in range(0, n//2):
a.append(i)
return a
のこぎり型配列(もしかしたら勘違いしているかも)
題名にも書きましたが、もしかしたらこれ勘違いして実装しているかもしれないと思っている配列です。
自分の考えでは大小交互に値が格納されている配列という認識です。
a = [1, 10, 2, 9, 3, 8, 4, 7, 5, 6]
という感じです。
なんで間違っているかと感じるかは後述します。
def saw_array(n):
a = []
for i in range(1, n//2+1):
a.append(i)
a.append(n-(i-1))
return a
測定プログラム
ここからは実際に配列の大きさを変えて各種配列での計算時間と交換回数をプロットしていこうと思います。
from time import time
import matplotlib.pyplot as plt
cnt_v = []
cnt_v2 = []
cnt_s = []
volly = []
volly2 = []
saw = []
val = []
for i in range(10, 10000, 100):
val.append(i)
a = voly_array(i)
past = time()
cnt_v.append(quick(a, 0, len(a)-1))
now = time()
volly.append(now-past)
a = voly2_array(i)
past = time()
cnt_v2.append(quick(a, 0, len(a)-1))
now = time()
volly2.append(now-past)
a = saw_array(i)
past = time()
cnt_s.append(quick(a, 0, len(a)-1))
now = time()
saw.append(now-past)
plt.scatter(val, volly, label="Volley(V-pattern)")
plt.scatter(val, volly2, label="Volley(High2Low)")
plt.scatter(val, saw, label="saw")
plt.legend()
plt.xlabel("Number of elements")
plt.ylabel("Time(s)")
plt.savefig("quicksort_time.png")
plt.show()
plt.scatter(val, cnt_v, label="Volley(V-pattern)")
plt.scatter(val, cnt_v2, label="Volley(High2Low)")
plt.scatter(val, cnt_s, label="saw")
plt.legend()
plt.xlabel("Number of elements")
plt.ylabel("Number of swap")
plt.savefig("quicksort_swap.png")
plt.show()
測定結果
計算時間
先述した3つの形の配列における配列の要素を10から100ずつ増やして10000までテストした結果がこちらになります。
結果として谷型配列(V字)が最悪の場合である
O(N^2)
のように多項式回帰における二次関数に近似できそうなことが分かります。
他の配列はそこまで計算時間が長くないことが考えられます。
交換回数
次に先述した3つの形の配列における交換回数を計測した結果がこちらになります。
計算時間では谷型配列(V字)が最悪でしたが、のこぎり型配列と交換回数自体はそこまで変わらなく、また谷型配列(大群から小群)は著しく低くなっており、全配列共に一次関数の近似直線で近似できることが分かります。
考察
交換回数がほぼ同じ程度の谷型配列(V字)とのこぎり型配列が時間は大きく異なっていました。
これについてクイックソートは再帰を使うため再帰の回数によるのではないかと考えてみました。
そのため再帰の深さを記録する関数に書き換えてみました。
maxdepth = 0
def quick(a, first, last, depth):
cnt = 0
global maxdepth
if maxdepth < depth:
maxdepth = depth
pivot = a[(first + last) // 2]
i = first
j = last
while(True):
while a[i] < pivot:
i = i + 1
while pivot < a[j]:
j = j - 1
if i >= j:
break
temp = a[i]
a[i] = a[j]
a[j] = temp
cnt = cnt + 1
i = i + 1
j = j - 1
if first < (i - 1):
cnt = cnt + quick(a, first, i-1, depth+1)[0]
if (j + 1) < last:
cnt = cnt + quick(a, j+1, last, depth+1)[0]
return cnt, maxdepth
dep_v = []
dep_v2 = []
dep_s = []
val = []
for i in range(10, 10000, 100):
maxdepth = 0
a = voly_array(i)
dep_v.append(quick(a, 0, len(a)-1, 0)[1])
maxdepth = 0
a = voly2_array(i)
dep_v2.append(quick(a, 0, len(a)-1, 0)[1])
maxdepth = 0
a = saw_array(i)
dep_s.append(quick(a, 0, len(a)-1, 0)[1])
これを実行した結果下図のようになりました。
この結果から谷型配列(V字)は再起回数が非常に多いため交換回数がのこぎり型配列と同等でも時間が長かったのではないかと考えられます。
で、のこぎり型配列がなんで間違っている可能性があるかについてですが、学生のレポートを見ていると谷型配列よりのこぎり型配列の方が計算時間が長いとの事です。
そのためもしかしたらのこぎり型配列の定義が間違っているかもしれません(ここは本番で貰うプログラムを参照しよう)。
総括
こういうプログラミングってケアレスミス多いから気を付けよう。