第5章. 帽子なしのソート
この作品はAIを使って翻訳されている。ご意見、ご感想をお待ちしている:translation-feedback@oreilly.com
この章では、配列のN個の値を昇順に並べ替えるアルゴリズムを紹介する。ソートされた順序で値の集合を整理することは、多くのプログラミングの効率を向上させるために不可欠な最初のステップである。ソートはまた、従業員の名前と電話番号が記載された会社のディレクトリを印刷したり、空港のディスプレイに飛行機の出発時刻を表示したりするような、多くの実世界のアプリケーションでも必要である。
並び順のない配列の場合、値の検索は最悪の場合O(N)である。配列がソートされている場合、バイナリ配列検索は、最悪の場合、O(log N)のパフォーマンスで目的の値を見つけることができる。
スワップによるソート
図5-1の一番上にある配列、A の値をソートしてみよう。鉛筆を使って、図5-1の値を紙にコピーしてみよう(あるいはペンを持ってきて、このページに書き込んでみよう!)。配列中の2つの値の位置を繰り返し入れ替えることで、これらの値を昇順にソートすることに挑戦する。最も少ないスワップ回数は何回だろうか?また、2つの値を比較した回数もカウントしてみよう。私はこれらの値を5回のスワップでソートした。もっと少なくすることは可能か?1
図5-1. サンプル配列、A 、ソートする。
スワップの回数をカウントすることも重要だが、2つの値の比較回数もカウントする必要がある。手始めに、A 、たった7回の比較で、2が最小の値であることがわかる。これは第1章で示したとおりである。最小値はA[3] で発見されたので、A[0] と入れ替える。これにより、最小の値は本来あるべき配列の先頭に移動する。図5-1では、スワップされた値をハイライトしている。太字の枠は、最終的な位置にあることが保証されている値をマークするために使っている。太字の枠の外側の値はすべてソートされる。
残りの値をスキャンして最大の値24を発見し(6つの比較を使用)、 ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access