D. Knuth, Tha art of computer programming, Reading, Mass. Addison Wesley, 1975

　　Sorting and Searching

では，ソート・アルゴリズムの詳説も掲げられている．ソート・アルゴリズムの性能解析のために「増加列の長さの平均」を掲載しているのである．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【１】ソート・アルゴリズム概説

　ランダムな順番で並んでいるデータを大きさの順に並べ換えて整列させることをソーティングといいます．ソーティングはデータ処理において基本中の基本となるもので，プログラムを作るにはプログラミング言語や計算機自体の知識のほかにこうした定石（アルゴリズム）についての理解が必要です．

　ソーティングには多くの方法があり，アルゴリズムによって大きくスピードが異なってきます．また，もともと同じ大きさのデータがもとの順序関係を崩さないような並べ換えを「安定なソート」とか「自然な振る舞いのソート」といいます．速いソート法は一般的に不安定で順序関係を保存することはできません．遅いソート法は大量のデータのソートには適しませんが，安定かつ原理が単純で理解しやすいため好まれています．

　ソートアルゴリズムにはそれぞれ利害得失があり，スピードだけで一概にその性能を評価することはできませんが，これらのアルゴリズムをインプリメントするときの便宜のために，下表のごとく３つのグループに分類しその性能を整理しておきます．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【２】ソートの性能比較

アルゴリズム　　　　　　　　　　実行時間

単純選択法　　　　　　　　　　・Ｏ（Ｎ^2）　　・

改良選択法（ヒープ・ソート）　・Ｏ（Ｎlog2Ｎ）・

単純挿入法　　　　　　　　　　・Ｏ（Ｎ^2）　　・

改良挿入法（シェル・ソート）　・Ｏ（Ｎ^1.2）　・

単純交換法（バブル・ソート）　・Ｏ（Ｎ^2）　　・

改良交換法（クイック・ソート）・Ｏ（Ｎlog2Ｎ）・

　Ｏ（Ｎ^2）とはＮ^2に比例する実行時間が必要の意（Ｎ：データ数）．すなわち，Ｏ（Ｎ^2）ではデータ数が１００倍になると実行時間は１００００倍になります．したがって，単純選択法，単純挿入法，単純交換法はデータ数が多くなると極端に遅くなり実用的ではなくなります．

　メモリ中だけでソートすることを内部ソート（オンメモリ・ソート）といいますが，その中でもっとも平均的な効率のいい方法がクイック・ソートです．最高速だといわれているクイック・ソートでも，最悪の場合（元のデータが逆順に整列していた場合）にはＮ2 のオーダーの計算量となることがありますが，ごくまれなケースでありそのようなことはまずないと考えてよいでしょう．なお，メモリに入り切らないような巨大なデータをソートするには外部ソートのテクニックが必要になってきます．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝