Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Sign up for free
Menu
Search
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Pricing
Search
Sign in
Sign up for free
スターリンマージソート
Search
Sponsored
·
Your Podcast. Everywhere. Effortlessly.
Share. Educate. Inspire. Entertain. You do you. We'll handle the rest.
→
suzakutakumi
July 10, 2021
Programming
660
3
Share
Embed
Copy iframe code
Copy JS code
Copy link
Start on current slide
スターリンマージソート
Zliの大LTで発表したスライドです
suzakutakumi
July 10, 2021
Transcript
13 slides
スターリンマージソート 2021/07/10 Zli 大LT
自己紹介 HN:朱雀 匠(本名:鈴木 拓眞) Twitter: @suzakutakumi3
None
None
目的 スターリンソートから新しいソートアルゴリズムを考えました 実用性はない気がします また、世界のどこかに同じアルゴリズムがあると思うのでn番煎じです
スターリンソートとは ソートするのに邪魔な要素を粛清して、昇順・降順に並び替えるアルゴリズムです Pythonでの例: a=[1, 3, 2, -2,10,5,11] print(StalinSort(a)) 出力:[1, 3,
10, 11]
スターリンソートは実用的なアルゴリズムじゃない そこで、実用的なソートアルゴリズムにしよう!
スターリンマージソート スターリンマージソートは、スターリンソートとマージソートを元に考えました 最初にスターリンソートを繰り返し、並び替えられた配列を複数作ります その後、マージソートと同じ原理でマージしていきます 詳しくは次のページで
手順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] ]
手順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]
計算量について 最悪計算量はO(n^2)です [n,n-1,n-2,・・・,3,2,1]の場合、最悪計算量になります 平均計算量はよくわかっていません マージ部分の処理数は、 分割された配列の数mとソートする配列の長さnとすると O(nlogm) になります
実際に時間を計測してみた [0,1,2,3,4,5,6,7,8,9]を10!通り並び替え実行し、実行し終えるまでの時間を測定しました マージソートが他のバブルソートなどよりも遅く、しっかりと計測できていなさそう
まとめ 平均処理数がわからないが、処理時間を見て遅いことが予想される アルゴリズムを考えてみて、先駆者たちの考えたアルゴリズムがすごかったこ とが再認識できた
More Decks by suzakutakumi
See All by suzakutakumi
ピクロス作成の中間発表
suzakutakumi
0
120
しゅみろん
suzakutakumi
0
200
trap-search
suzakutakumi
1
75
Pyramid Makerの作成
suzakutakumi
0
74
マークダウンパーサーの自作
suzakutakumi
0
140
絵文字ジェネレータボットの作成
suzakutakumi
0
180
send_discord
suzakutakumi
0
76
独自ドメインについて
suzakutakumi
0
72
ESP32とAlexaを用いたエアコン制御
suzakutakumi
0
1.4k
Other Decks in Programming
See All in Programming
クラウドエージェントは、 何がそんなに便利なのか / what makes cloud agents so useful
rkaga
5
950
そのデザイントークン、Flutterでも同じ見た目になりますか?
nakamizu
0
440
AIがコードを書いてくれる時代、我々は何を確かめるのか
yosuke_furukawa
PRO
13
6.1k
クラウドゲーミングのパフォーマンス最適化に挑む / Cloud Gaming Performance Tuning
vivion
0
360
Augmenting AI with the Power of Jakarta EE
ivargrimstad
0
390
プロジェクトコードをキレイキレイしよう!暗黙的な参照を読み解く静的解析
ostk0069
0
220
どうしても Eloquent でリポジトリパターンをやりたいんだ #phpcon_niigata / phpcon-niigata-2026
shogogg
0
660
Claude Code ハーネスDeep Dive – 君はどこまで制御する? -
takateeen_knj
6
6.2k
Spec-driven Development with AI
simas
PRO
0
2.3k
Vapor Mode でアクセシビリティは 壊れないか検証した話
fuqda
1
350
TS 7.0 で baseUrl が使えなくなった今、パスエイリアスをどうするか
bicstone
2
760
AI時代のFlutter品質設計 — アプリ品質を守るQuality Layers
omatty198
0
390
Featured
See All Featured
4 Signs Your Business is Dying
shpigford
187
23k
The Pragmatic Product Professional
lauravandoore
37
7.5k
Leveraging Curiosity to Care for An Aging Population
cassininazir
1
570
The browser strikes back
jonoalderson
0
2k
Side Projects
sachag
456
43k
GraphQLの誤解/rethinking-graphql
sonatard
75
12k
Music & Morning Musume
bryan
48
7.5k
Crafting Experiences
bethany
1
450
Odyssey Design
rkendrick25
PRO
3
960
RailsConf 2023
tenderlove
30
1.6k
Navigating Algorithm Shifts & AI Overviews - #SMXNext
aleyda
1
1.7k
Designing Experiences People Love
moore
143
24k