ソート(整列)とは
たとえば、以下の名前の並びを考えてみよう。
佐藤、高橋、加藤、田中、石田
この5名の名前を「あいうえお順」に並べることを考えてみよう。あいうえお順は、辞書式順序(dictionary order)という。
まず、佐藤(さとう)、高橋(たかはし)、加藤(かとう)、田中(たなか)、石田(いしだ)とひらがなで考えるだろう。すると、以下のようになる。
さとう、たかはし、かとう、たなか、いしだ
まず、このなかで一番最初(になるべき)の名前を検索する。すると、「いしだ」であることがわかり、最初の名前「さとう」と交換する。
いしだ、たかはし、かとう、たなか、さとう
となる。次に、残りの、「たかはし、かとう、たなか、さとう」について、同様に、一番最初(になるべき)の名前を検索する。すると、「かとう」であることがわかり、二番目の名前「たかはし」と交換する。
いしだ、かとう、たかはし、たなか、さとう
となる。さらに、残りの「たかはし、たなか、さとう」について、同様の処理を行う。
いしだ、かとう、さとう、たなか、たかはし
となる。さらに、「たなか、たかはし」について、同様の処理を行う。
いしだ、かとう、さとう、たかはし、たなか
となる。以上の処理より、解は以下となる。
石田、加藤、佐藤、高橋、田中
ここで、以下の2つの処理が必要となることがわかる。以下では、簡単のために数字の並び替えを考えよう。
87、90、56、98、23
で考えてみよう。
23、90、56、98、87
23、56、90、98、87
23、56、87、98、90
23、56、87、90、98
となり、いわゆる「昇順」となった。この処理では、以下の2つの処理が重要であることがわかった。
この2つの処理を使うとソートのアルゴリズムは以下のようになる。
まず、データを以下のように置く。
以下で、i は変数、N は定数とする。
では、次にこのアルゴリズムをプログラミングしよう。このアルゴリズムは最小法という。値は、ランダムに生成することにしよう。