22:52:50)追加された行はこの色です。削除された行はこの色です。ソート(sort:整列)とは、順番通りに並べることである。1〜13までのトランプがあれば、それを小さい順あるいは大きい順に並べ直すことである。人ならば小さいものを左に置く、大きいものを右に置くといった方法で並び替えるだろう。これが13までではなく1万などと膨大な並び替えを必要とするとき、なんらかの手続き(アルゴリズム)にしたがって並び替えていかないと混乱してしまう。コンピュータはこうした単純作業が得意としており、並び替えの方法はたくさん考えられている。例:ソートの例-有限個の自然数の数列を小さい順に並び替える。-本棚の本を題名の五十音順に並べ替える。数学的にいうとソートアルゴリズムとは「有限集合の元を与えられた全順序関数にしたがって並べ替える手順」のことである。基本的なソートである。隣同士のデータを順に比較して、大小関係が逆ならば交換する方法である。トランプ数ループは、「回=N〜2」である。「回=2〜N」でないかを考えてみよう。例としてN=5として考える。1回目は、1〜5の範囲を比較して一番大きいものを「トランプ(5)」に置く。よって、最大値ループは「数=1〜4」である。2回目は「トランプ(5)」は確定しているので、1〜4の範囲を比較して一番大きいものを「トランプ(4)」に置く。よって、最大値ループは「数=1〜3」である。したがって、最大値のループ範囲を指定するときに、トランプ数のループを「回=N〜2」としておけば、「数=1〜回-1」と回を使えるので便利である。例:1〜5まで(N=5)のトランプを上記のバブルソートの流れ図を使って、小さい順に並べ替えていくときをトレースする。上記流れ図の☆印のところに着目してトレースしていった。最小値(あるいは最大値)を選び出して、左側(あるいは右側)に置いていく方法である。具体例を考えていこう。ここでは次の配列を小さい順に並べ替えることを目標とする。小さい値のトランプを探し出す流れ図を示す。この流れ図により、5枚の中から一番小さいトランプの位置は4であることがわかる。次に、この一番小さいトランプ(=1)を先頭に持ってくる。そのためには元々先頭にあるトランプをどけないと、一番小さいトランプを置くことができない。そこで、交換するわけである。この例では「トランプ(1)」と「トランプ(4)」を交換する。小さいトランプが先頭に来たので、次に残った4枚の中から一番小さいトランプを探し出して「トランプ(2)」と交換する。このような操作を繰り返すと、トランプを小さい順に並べ替えることができる。以上から、トランプの枚数をN枚とすると、小さい順に並び替える流れ図は次のようになる。置いていない要素からひとつずつ取り出して、それを置くべき位置に挿入していく方法である。並んでいるところの間に入れるので、「挿入」という言葉が使われる。データとデータの間に新しいデータを挿入するためには、データを後ろにずらして挿入す売る領域を空けなければならないために、コンピュータで実現するには少々面倒である。配列に設定されているN枚のトランプを並べ替える流れ図は次の通りになる。この流れ図では、挿入位置を空けて挿入するのではなく、配列の後から挿入位置まで隣と交換させながら移動することで挿入を行っている。#img(http://security2600.sakura.ne.jp/main2/image1/sounyuu2.jpg)#img(,clear)例:1〜5まで(N=5)のトランプを上記のバブルソートの流れ図を使って、小さい順に並べ替えていくときをトレースする。上記流れ図の☆印のところに着目してトレースしていった。水色が比較して部分であり、灰色が挿入前のデータである。この挿入ソートのアルゴリズムは、逐次添加法というアイデアを用いている。次のように文字を定義する。各行におけるコストと時間は次のようになる。1");が最良計算量となる。j");が最悪計算量となる。\)}{2}");が平均計算量となる。挿入ソートを改良した方法である。挿入ソートはデータを挿入するとき、データを後ろにずらすのに時間がかかる。データが1万件あって、1番目に挿入する場合は、1万件のデータを後ろにずらす必要が生じてしまう。シェルソートはざっと並べ替えるので、後ろにずらすデータの数が少なくなる。そこで、飛び飛びに見て論理的なデータ列で考えるのである。このデータの並べ替え、間隔を半分にして同様に並べていく。シェルソートの概要は次の通りである。1:適当な間隔hを決める。2:間隔hをあけて取り出したデータ列に挿入ソートを適用する。3:間隔hを狭めて、2.を適用する操作を繰り返す。4:h=1になったら、最後に挿入ソートを適用して終了する。配列に設定されているN枚のトランプを並べ替える流れ図は次の通りになる。N=8の場合は、8÷2=4で、間隔は4から始まる。「トランプ(1)」と「トランプ(1+4)」、「トランプ(2)」と「トランプ(2+4)」、「トランプ(3)」と「トランプ(3+4)」、「トランプ(4)」と「トランプ(4+4)」の4つのデータ列で整列する。次に間隔を半分の2にし、2つのデータ列で整列する。完全に解析されたわけではない。sort)''は、軸(''ピボット''という)という基準値で、軸より小さいデータと大きいデータに振り分け、データ領域を2つに分けることを繰り返す並べ替え法である。実際のプログラムの際に、最もよく用いられるソートアルゴリズムである。用いられるということは、それなりに高速性を持つわけである。軸の決め方は自由である。通常は、中央のデータを使うことが多い。軸の決め方によって、データが偏ってしまうことがある。次のようなデータ列をクイックソート(基準値は中央のデータの1)するとき、右側(軸より大きいデータ)だけにすべて移動してしまう。軸の左側には小さいデータ、右側には大きいデータが集まったデータ列ができるが、このデータ列に対しても同様な操作を行う。このときに[[再帰アルゴリズム]]を用いることができる。アルゴリズムが単純というメリットに繋がる。クイックソートは次に示す2つのアルゴリズムが使われている。このようにnを定義すると、クイックソートの計算量は次のようになる。Theorem]]を使えばよい。\)");が最良計算量となる。\)");が最悪計算量となる。\)");が平均計算量となる。sort)''とは、大量のデータをいくつかのグループに分割し、整列(ソート)と併合(マージ)を行う方法である。磁気テープなどに順編成ファイルとして記憶されている大量のデータを並べ替えるには、工夫が必要となる。主記憶装置の容量には限りがあるので、すべてのデータを主記憶装置に読み込んで整列できないからである。主記憶装置を用いて行う整列を''内部整列''、補助記憶装置を用いて行う整列を''外部整列''と呼ぶ。マージソートは外部整列に向くソートアルゴリズムである。マージソートは分割統治法で設計されている。マージソートは次に示す2つのアルゴリズムが使われている。funciton((小数点切り捨て))である。このようにnを定義すると、T(n)は次のようになる。再帰アルゴリズムからこのような形になる。未整列の部分を部分木で表し、そこから最大値または最小値を取り出して既整列の部分に移していく。sort)''である。ヒープ(heap)((ヒープの元の意味は「モノを積み上げた山」のことである。))は2分木の節を配列の添字に対応させて表現し、「親<子」または「親>子」となるようなデータ構造である。ヒープは子の添字を2で割ることで親の添字がわかる。「親>子」の場合、根に最大値があることを利用するのがヒープソートである。ここでは「親>子」として考える。配列の添字に、根を配列1、節kの左を2k、節kの右を2k+1として対応させる。配列とその値のセットで考えていく。上記の配列をヒープに変換すると次のようになる。根から最大値を取り出して、配列の末尾に置く。次にヒープを再構成して、根から最大値を取り出して、配列の末尾に置く。ヒープを再構成して、根から最大値を取り出して、配列の末尾に置く。同様に繰り返していく。sort)''とは、あらかじめデータがとりうる値すべての容器(バケツ=bucket)を順番通りに並べて用意しておいて、値を対応する容器に移すことでソートを行うアルゴリズムである。sort)とも呼ばれる。特徴から明らかだが、とりうる値がわかっていなければ、容器を準備できないので、バケットソートは使えない。容器という作業領域が必要となるので、データの範囲が大きすぎると、それに比例してメモリを大量に消費してしまう。データの範囲が1〜1,024かつバケツひとつに1バイトの領域が必要なら、すべてのバケツを用意するだけで1Kバイトの領域が必要となってしまう。ソート対象のデータは重複が許されないという大きな特徴を持つ。バケツは想定される値をキーとして用意されるから、同じ値が存在しても対応する複数のバケツを用意できないのである。この点を改良したソートアルゴリズムに、分布数え上げソートがある。sort)''とは、ソート対象のデータをキーにして、キーの出現回数とその累積度数分布を計算して利用するソートアルゴリズムである。バケットソートと同じようにキーとなるデータがとりうる値の範囲をあらかじめ知っておく必要がある。バケットソートはキーの重複に対応していなかったが、分布数え上げソートではキーの重複に対応している。特徴として、バケットソートと同様に作業領域がたくさん必要となる。大きな作業領域と引き換えにデータの大小を比較しなくてもよいので、高速なソートを実現できる。各種ソートアルゴリズムのオーダーをまとめておく。nSUP{2};の関数が赤色、nSUP{3/2};の関数が緑色、nlogSUB{2};nの関数が青色である。上のグラフからわかるように、圧倒的に赤色のほうがnの値が増えるにつれて増加していることがわかる。効率がよいのは青色であることがわかる。計算量のオーダーだけで考えるとクイックソートなどが一番効率がよい。厳密には空間量のオーダーも考える必要がある(ソートにおいてはあまり重要でない)。どのソートアルゴリズムを使うかは、データがどのような値をとるか調べることも重要である。極端な例だと、1万件のデータでも0と1しかない数列ならば、0の数を数えたほうが早い。