ソートアルゴリズムを書く

ソートアルゴリズムを実装してみよう

TypeScriptでは配列のsort()メソッドを使うことで簡単にソートが実装できますが、せっかくなのでソートアルゴリズムを自分で実装してみましょう。

Wikipediaなどでソートアルゴリズムについて調べると具体的な説明や実装例が見つかります。解説はそちらに任せ、ここではTypeScriptでの実装例を紹介します。

マージソートの実装例

例えば2つの小さい順に整列済みの配列を先頭から順番に比較して、より小さい要素を新しい配列に追加していくことで、1つのソート済みの配列を作ることができます。与えられた配列を分割して再帰的にその操作を行っていくのがマージソートの基本的な考え方です。

試しに1000個のランダムな数値を並び替えてみて、自作のマージソートと組み込みのsort()メソッドの実行時間を比較しています。結果はいかがでしょうか？これだとあまり差が出ないかもしれないので、無理のない範囲で配列の要素数を増やして試してみてください。

クイックソートの実装例

クイックソートは配列の中からピボットと呼ばれる要素を選び、その要素を基準にして配列を2つの部分に分けることでソートを行います。具体的には、ピボットより小さい要素を左側に、大きい要素を右側に配置し、その後再帰的に各部分をソートしていきます。

ピボットの選び方などの工夫があり、この説明だけだと分かりづらいので詳しくはWikipediaなどを参照してください。今回はメジャーな真ん中をピボットに選んで両端から走査・入れ替えていく手法で実装します。

クイックソートはその名の通り他のソート法と比べて一般的に最も高速だと言われており、よく使われるソートアルゴリズムの1つです。名前だけは覚えておいて損はありません。

実行結果はいかがだったでしょうか？私の環境では、要素数を増やすと自作のクイックソートの方が組み込みのsort()メソッドよりも速くなりました。これには組み込みのsort()メソッドが安定ソート（同じ値の要素の場合に元の順序を保持する）であり、不安定ソートであるクイックソートを使用していないことが影響しているかもしれません。

まとめ

ここではマージソートとクイックソートの2つのソートアルゴリズムのTypeScriptでの実装例を紹介しました。実務では組み込みのsort()メソッドを使うことがほとんどですが、ソートアルゴリズムの基本的な考え方や実装方法を理解しておくことはアルゴリズム全般の理解にも役立ちます。

さらに他のソートアルゴリズムについても興味があれば調べてみてください。バブルソートや挿入ソート、ヒープソートなど、様々なアルゴリズムが存在します。それぞれの特徴や適用場面を理解することで、より深いアルゴリズムの知識を身につけることができます。