スターリンマージソート

Zliの大LTで発表したスライドです

Transcript

1. スターリンマージソート 2021/07/10 Zli 大LT
2. 自己紹介 HN:朱雀 匠(本名:鈴木 拓眞) Twitter: @suzakutakumi3
5. 目的 スターリンソートから新しいソートアルゴリズムを考えました 実用性はない気がします また、世界のどこかに同じアルゴリズムがあると思うのでn番煎じです
6. スターリンソートとは ソートするのに邪魔な要素を粛清して、昇順・降順に並び替えるアルゴリズムです Pythonでの例: a=[1, 3, 2, -2,10,5,11] print(StalinSort(a)) 出力:[1, 3, 10, 11]
7. スターリンソートは実用的なアルゴリズムじゃない そこで、実用的なソートアルゴリズムにしよう!
8. スターリンマージソート スターリンマージソートは、スターリンソートとマージソートを元に考えました 最初にスターリンソートを繰り返し、並び替えられた配列を複数作ります その後、マージソートと同じ原理でマージしていきます 詳しくは次のページで
9. 手順1:並び替えられた配列の生成 例:[0, 114, 13, 600, -282, 114] 1.スターリンソートをして、結果と除外された値の配列を作る 整列された配列:[0, 114, 600] 除外された配列:[13, -282, 114] 2.除外された配列で1と同様のことをする 整列された配列:[13, 114] 除外された配列:[-282] これで、整列された3つの配列が用意できました [ [0,114,600], [13, 114], [-282] ]
10. 手順2:並び替えられた配列をマージする [ [0,114,600], [13, 114], [-282] ] 1.[0,114,600]と[13, 114]をマージします [ [0,13,114,114,600], [-282] ] 2.[0,13,114,114,600]と[-282]をマージします [-282,0,13,114,114,600]
11. 計算量について 最悪計算量はO(n^2)です [n,n-1,n-2,・・・,3,2,1]の場合、最悪計算量になります 平均計算量はよくわかっていません マージ部分の処理数は、 分割された配列の数mとソートする配列の長さnとすると 　O(nlogm) になります
12. 実際に時間を計測してみた [0,1,2,3,4,5,6,7,8,9]を10!通り並び替え実行し、実行し終えるまでの時間を測定しました マージソートが他のバブルソートなどよりも遅く、しっかりと計測できていなさそう
13. まとめ 平均処理数がわからないが、処理時間を見て遅いことが予想される アルゴリズムを考えてみて、先駆者たちの考えたアルゴリズムがすごかったこ とが再認識できた