Python でアルゴリズム

最終的に Python で使われているソートアルゴリズム TimSort に関する以下の記事の雰囲気が伝わるようになれることを目標にしています。 自分も外面しかまだ読めてません。 ここで前提とされている知識、 クイックソート、マージソート、ヒープソート、挿入ソートには触れて、 なんとか興味が持てるくらいのラインにまでいければと考えています。

高速な安定ソートアルゴリズム TimSort の解説

しかしながら、オリジナルのTimSortのコードは若干複雑で、 実際のところどういうアルゴリズムなのかわかりづらいところがあると思います。

そこで今回はTimSortのアルゴリズムをできるだけわかりやすく解説してみたいと思います (  クイックソート、マージソート、ヒープソート、挿入ソート  の知識を前提とします)。

アルゴリズムと聞くと難しそうですが、「探索」、「木」、「ソート」については、  「はんぶんこにすると速くなる」  という雰囲気が伝わればと思いました。 個々の細かいコードは、あまり掘り下げなくてもいいかなと感じたりもします。

流れとしては、まず「二分探索」から始まり「二分木」、そして「ソート」に話を持っていきます。

最初に「二分探索」を持って来たのは、最も短い標準ライブラリ bisect だからというのと、 そのあとの「二分探索 」につなげることができるからです。

次に「ソート」の前に「二分木」を持って来たのは、「二分ヒープ」は「ヒープソート」を、 「二分探索木」は「クイックソート」を図示することができるからです。

最後に余った「マージソート」と「挿入ソート」について触れていきます。

「素数」については、力技で調べざるを得ないので、 あまり得るものはないかなという感じもします。 純粋にコードの書き方の世界という感じがします。

たまに競プロででてきたりするので、 雰囲気だけ押さえておけばいいかなとも思います。