Security Akademeia

目次 †

目次
ソートとは
バブルソート（基本交換法、隣接交換法）
- バブルソートの流れ図
- バブルソートの計算量
選択ソート（基本選択法、選択法）
- 選択ソートの流れ図
- 選択ソートの計算量
挿入ソート（基本挿入法、挿入法：intersion sort）
シェルソート（改良挿入法）
- シェルソートの流れ図
- シェルソートの計算量
クイックソート
- クイックソートのアルゴリズム
- クイックソートの計算量
マージソート
- マージソートのアルゴリズム
- マージソートの計算量
ヒープソート
- ヒープソートの計算量
バケットソート（ビンソート）
分布数え上げソート
まとめ
参考文献

ソートとは †

　ソート（sort：整列）とは、順番通りに並べることである。例えば1～13までのトランプがあれば、それを小さい順あるいは大きい順に並べ直すことである。人ならば小さいものを左に置く、大きいものを右に置くといった方法で並び替えるだろう。しかしこれが13までではなく1万などと膨大な並び替えを必要とするとき、なんらかの手続き（アルゴリズム）にしたがって並び替えていかないと混乱してしまう。コンピュータはこうした単純作業が得意としており、並び替えの方法はたくさん考えられている。

例：ソートの例

有限個の自然数の数列を小さい順に並び替える。
本棚の本を題名の五十音順に並べ替える。

　数学的にいうとソートアルゴリズムとは「有限集合の元を与えられた全順序関数にしたがって並べ替える手順」のことである。

↑

バブルソート（基本交換法、隣接交換法） †

　最も基本的なソートである。隣同士のデータを順に比較して、大小関係が逆ならば交換する方法である。

例：1～5までのトランプをバブルソートで小さい順に並べ替える

↑

バブルソートの流れ図 †

　トランプ数ループは、「回＝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）のトランプを上記のバブルソートの流れ図を使って、小さい順に並べ替えていくときをトレースする。特に上記流れ図の☆印のところに着目してトレースしていった。

回	数	トランプ
回	数	（1）	（2)	（3）	（4）	（5）
実行前		4	2	5	1	3
5		4	2	5	1	3
	1	4	2	5	1	3
	交換	2	4	5	1	3
	2	2	4	5	1	3
	3	2	4	5	1	3
	交換	2	4	1	5	3
	4	2	4	1	5	3
	交換	2	4	1	3	5
4	1	2	4	1	3	5
	2	2	4	1	3	5
	交換	2	1	4	3	5
	3	2	1	4	3	5
	交換	2	1	3	4
3	1	2	1	3	4	5
	交換	1	2	3	4	5
	2	1	2	3	4	5
2	1	1	2	4	3	5

↑

バブルソートの計算量 †

　バブルソートの平均計算量は $O~$~n^2~$$ である。

↑

選択ソート（基本選択法、選択法） †

　最小値（あるいは最大値）を選び出して、左側（あるいは右側）に置いていく方法である。

例：1～5までのトランプを選択ソートで小さい順に並べ替える

↑

選択ソートの流れ図 †

　具体例を考えていこう。ここでは次の配列を小さい順に並べ替えることを目標とする。

トランプ(1)	トランプ(2)	トランプ(3)	トランプ(4)	トランプ(5)
4	2	5	1	3

　まず一番小さい値のトランプを探し出す流れ図を示す。

　この流れ図により、5枚の中から一番小さいトランプの位置は4であることがわかる。

　次に、この一番小さいトランプ（＝1）を先頭に持ってくる。そのためには元々先頭にあるトランプをどけないと、一番小さいトランプを置くことができない。そこで、交換するわけである。この例では「トランプ(1)」と「トランプ(4)」を交換する。

　一番小さいトランプが先頭に来たので、次に残った4枚の中から一番小さいトランプを探し出して「トランプ(2)」と交換する。このような操作を繰り返すと、トランプを小さい順に並べ替えることができる。

　以上から、トランプの枚数をN枚とすると、小さい順に並び替える流れ図は次のようになる。

例：1～5まで（N=5）のトランプを上記の選択ソートの流れ図を使って、小さい順に並べ替えていくときをトレースする

回	数	小	トランプ
回	数	小	（1）	（2)	（3）	（4）	（5）
実行前			4	2	5	1	3
1		1	4	2	5	1	3
	2	1	4	2	5	1	3
	2	2	4	2	5	1	3
	3	2	4	2	5	1	3
	4	2	4	2	5	1	3
	4	4	4	2	5	1	3
	5	4	4	2	5	1	3
	交換		1	2	5	4	3
2	3	2	1	2	5	4	3
	4	2	1	2	5	4	3
	5	2	1	2	5	4	3
3	4	3	1	2	5	4	3
	4	4	1	2	5	4	3
	5	4	1	2	5	4	3
	5	5	1	2	5	4	3
	交換		1	2	3	4	5
4	5	4	1	2	3	4	5

↑

選択ソートの計算量 †

　選択ソートの平均計算量は $O~$~n^2~$$ である。

↑

挿入ソート（基本挿入法、挿入法：intersion sort） †

　まだ置いていない要素からひとつずつ取り出して、それを置くべき位置に挿入していく方法である。すでに並んでいるところの間に入れるので、「挿入」という言葉が使われる。

例：1～5までのトランプを挿入ソートで小さい順に並べ替える

　データとデータの間に新しいデータを挿入するためには、データを後ろにずらして挿入す売る領域を空けなければならないために、コンピュータで実現するには少々面倒である。

↑

挿入ソートの流れ図 †

　配列に設定されているN枚のトランプを並べ替える流れ図は次の通りになる。

　この流れ図では、挿入位置を空けて挿入するのではなく、配列の後から挿入位置まで隣と交換させながら移動することで挿入を行っている。

回	数	トランプ
回	数	（1）	（2)	（3）	（4）	（5）
実行前		4	2	5	1	3
2		4	2	5	1	3
	1	4	2	5	1	3
	交換	2	4	5	1	3
3	2	2	4	5	1	3
3	Exit	2	4	5	1	3
4	3	2	4	5	1	3
	交換	2	4	1	5	3
	2	2	4	1	5	3
	交換	2	1	4	5	3
	1	2	1	4	5	3
	交換	1	2	4	5	3
5	4	1	2	4	5	3
	交換	1	2	4	3	5
	3	1	2	4	3	5
	交換	1	2	3	4	5
	2	1	2	3	4	5
	Exit	1	2	3	4	5

　水色が比較して部分であり、灰色が挿入前のデータである。

↑

挿入ソートのアルゴリズム †

Input: A（整数の有限集合）
Output: Aのソート済みリスト

for j=2,…,length(A) do		/* j = r1 */
	key←A[j]		/* key = r3 */
	i←j-1			/* i = r2 */
	while i>0 and key≦A[i] do
		A[i+1]←A[i]
		i←i-1
	A[i+1]←key
return A

　この挿入ソートのアルゴリズムは、逐次添加法というアイデアを用いている。

↑

挿入ソートの計算量 †

　次のように文字を定義する。

tj：jに対して4行目を実行する関数
ck：k行目に必要なコスト

　各行におけるコストと時間は次のようになる。

行（Step）	コスト	時間
1	c1	n
2	c2	n-1
3	c3	n-1
4	c4	$\bigsum_{2~\le~j~\le~n}~t_{j}$
5	c5	$\bigsum_{2~\le~j~\le~n}~$~t_{j}~-1$$
6	c6	$\bigsum_{2~\le~j~\le~n}~$~t_{j}~-1$$
7	c7	n-1
8	c8	1

↑

最良計算量 †

　最初からすでにソート済みの場合、すなわち $\forall{j}~;~t_{j}~=~1$ が最良計算量となる。

$T~$~n~$$
$=~$~c_1~+~c_2~+~c_3~+~c_4~+~c_7~$~n~-~$~c_2~+~c_3~+~c_4~+~c_7~+~c_8~$$
$=~a_{1}~n~+~a_{0}~,~a_{i}~\in~\mathbb{R}~,~a_{1}~>~0$

　よって、最良計算量は $O~$~n~$$ である。

↑

最悪計算量 †

　逆順ソート済みの場合、すなわち $\forall{j}~;~t_{j}~=~j$ が最悪計算量となる。

$T~$~n~$$
$=~\frac{c_4~+~c_5~+~c_6}{2}~n^{2}~+~$~c_1~+~c_2~+~c_3~+~c_7~+~\frac{c_4~-~c_5~-~c_6}{2}~$~n~-~$~c_2~+~c_3~+~c_4~+~c_7~-~c_8~$$
$=~a_{2}~n^2~+~a_{1}~n~+~a_{0}~,~a_{i}~\in~\mathbb{R}~,~a_{2}~>~0$

　よって、最悪計算量は $O~$~n^2~$$ である。

↑

平均計算量 †

　 $\forall{j}~;~t_{j}~=~\frac{$~j+1~$}{2}$ が平均計算量となる。

$=~a_{2}~n^2~+~a_{1}~n~+~a_{0}~,~a_{i}~\in~\mathbb{R}~,~a_{2}~>~0$

　よって、平均計算量は $O~$~n^2~$$ である。

↑

シェルソート（改良挿入法） †

　挿入ソートを改良した方法である。挿入ソートはデータを挿入するとき、データを後ろにずらすのに時間がかかる。データが1万件あって、1番目に挿入する場合は、1万件のデータを後ろにずらす必要が生じてしまう。一方、シェルソートはざっと並べ替えるので、後ろにずらすデータの数が少なくなる。

　そこで、飛び飛びに見て論理的なデータ列で考えるのである。このデータの並べ替え、間隔を半分にして同様に並べていく。

　シェルソートの概要は次の通りである。

1：適当な間隔hを決める。

2：間隔hをあけて取り出したデータ列に挿入ソートを適用する。

3：間隔hを狭めて、2.を適用する操作を繰り返す。

4：h=1になったら、最後に挿入ソートを適用して終了する。

例：1～10までのトランプをシェルソートで小さい順に並べ替える

↑

シェルソートの流れ図 †

　配列に設定されているN枚のトランプを並べ替える流れ図は次の通りになる。

　N=8の場合は、8÷2=4で、間隔は4から始まる。「トランプ(1)」と「トランプ(1+4)」、「トランプ(2)」と「トランプ(2+4)」、「トランプ(3)」と「トランプ(3+4)」、「トランプ(4)」と「トランプ(4+4)」の4つのデータ列で整列する。
　次に間隔を半分の2にし、2つのデータ列で整列する。

↑

シェルソートの計算量 †

　シェルソートの平均計算量は $O~$~n^{\frac{3}{2}}~$$ である。ただし、完全に解析されたわけではない。

↑

クイックソート †

　クイックソート（quick sort）は、軸（ピボットという）という基準値で、軸より小さいデータと大きいデータに振り分け、データ領域を2つに分けることを繰り返す並べ替え法である。2つに分割するという点において、分割統治法でアプローチしている。実際のプログラムの際に、最もよく用いられるソートアルゴリズムである。よく用いられるということは、それなりに高速性を持つわけである。

　軸の決め方は自由である。通常は、中央のデータを使うことが多い。しかしながら、軸の決め方によって、データが偏ってしまうことがある。例えば、次のようなデータ列をクイックソート（基準値は中央のデータの1）するとき、右側（軸より大きいデータ）だけにすべて移動してしまう。

　軸の左側には小さいデータ、右側には大きいデータが集まったデータ列ができるが、このデータ列に対しても同様な操作を行う。このときに再帰アルゴリズムを用いることができる。つまりアルゴリズムが単純というメリットに繋がる。

例：1～10までのトランプをクイックソートで小さい順に並べ替える

↑

クイックソートのアルゴリズム †

　クイックソートは次に示す2つのアルゴリズムが使われている。

Partition(A,p,r)←分割するアルゴリズム
Quick-Sort(A,p,r)←クイックソートのアルゴリズム

アルゴリズム：Partition(A,p,r)
Input：A（整数の有限集合）
Output：A s.t. A[p,…,r]はソート済み

x←A[r]
i←p-1
for j=p,…,r-1 do
	if A[j]≦x then
		i←i+1
		A[i]←→A[j]
A[i+1]←→A[r]
return (i+1,A)

　このアルゴリズムの計算量は $T_{Pertition}~$~n~$~=~\Theta~$~n~$$

アルゴリズム：Quick-Sort(A,p,r)
Input：A（整数の有限集合）
Output：(q,A) s.t. A[p,…,q-1]≦A[q]＜A[q+1,…,r]

  1
  2
  3

if p＜r then
	(q,A)←Partition(A,p,r)
	Quick-Sort(A,p,q-1)
	Quick-Sort(A,q+1,r)

↑

クイックソートの計算量 †

$n:=r-p+1$

　このようにnを定義すると、クイックソートの計算量は次のようになる。クイックソートのアルゴリズムは再帰アルゴリズムなのでMaster Theoremを使えばよい。

↑

最良計算量 †

　 $O~$~n~\log_2~n~$$ が最良計算量となる。

↑

最悪計算量 †

　 $O~$~n^2~$$ が最悪計算量となる。

↑

平均計算量 †

　 $O~$~n~\log_2~n~$$ が平均計算量となる。

↑

マージソート †

　マージソート（merge sort）とは、大量のデータをいくつかのグループに分割し、整列（ソート）と併合（マージ）を行う方法である。

　磁気テープなどに順編成ファイルとして記憶されている大量のデータを並べ替えるには、工夫が必要となる。なぜならば、主記憶装置の容量には限りがあるので、すべてのデータを主記憶装置に読み込んで整列できないからである。主記憶装置を用いて行う整列を内部整列、補助記憶装置を用いて行う整列を外部整列と呼ぶ。
　マージソートは外部整列に向くソートアルゴリズムである。

　マージソートは分割統治法で設計されている。

例1：1～10までのトランプをマージソートで小さい順に並べ替える

例2：ソート済みデータのマージの例を示す

トランプ
（1）	（2)	（3）	（4）	（5）	（6）
2	3	6	1	4	5
2	3	6	1	4	5	1
2	3	6	1	4	5	1	2
2	3	6	1	4	5	1	2	3
2	3	6	1	4	5	1	2	3	4
2	3	6	1	4	5	1	2	3	4	5
2	3	6	1	4	5	1	2	3	4	5	6

↑

マージソートのアルゴリズム †

　マージソートは次に示す2つのアルゴリズムが使われている。

Merge(A,p,q,r)←ソート済みの2つのデータ列をマージするアルゴリズム
Merge-Sort(A,p,r)←マージソートのアルゴリズム

アルゴリズム：Merge(A,p,q,r)
Input：A（整数の有限集合） s.t. A[p,…,q]かつA[q+1,…,r]はソート済み
Output：A s.t. A[p,…,r]はソート済み

n1←q-p+1,n2←r-q
for i=1,…,n1+n2 do
	T[i]←A[p+i-1]
i←1,j←n1+1
for k=p,…,r do
	if j＞n1+n2 or i≦n1 and T[i]≦T[j] then
		A[k]←T[i]
		i←i+1
	else
		A[k]←T[j]
		j←j+1

$n:=~length~$~A~$~=~r-p+1~\Rightarrow~T_{Merge}~$~n~$~=~\Theta~$~n$$

アルゴリズム：Merge-Sort(A,p,r)
Input：A（整数の有限集合） Output：A s.t. A[p,…,r]はソート済み（p=1,r=length(A)とする）

if p<r then
	q←[(p+r)/2]
	Merge-Sort(A,p,q)
	Merge-Sort(A,p+1,r)
	Merge(A,p,q,r)

　ちなみに[ ]という関数はfloor funciton*1である。

↑

マージソートの計算量 †

$n:=~r-p+1$

　このようにnを定義すると、T(n）は次のようになる。再帰アルゴリズムからこのような形になる。

$T~$~n~$~=~2T~$~\frac{n}{2}~$~+~\Theta~$~n~$$
$\Rightarrow~a=2,b=2,f~$~n~$~=~\Theta~$~n~$$ 　（∵Master Theoremより）
$\Rightarrow~n^{\log_b~a}~=~n^{\log~2}~=~n$
$\Rightarrow~f~$~n~$~=~\Theta~$~n~$~=~\Theta~$~n^{log_b~a}~log^0~n~$$
$\Rightarrow~T~$~n~$~=~\Theta~$~n^{\log_b~a}~\log~n~$~=~\Theta~$~n~\log~n~$$

　以上より、最良・最悪・平均計算量はいずれも $\Theta~$~n~\log~n~$$ である。

↑

ヒープソート †

　未整列の部分を部分木で表し、そこから最大値または最小値を取り出して既整列の部分に移していく。この操作を繰り返して、未整列を縮めていくソートアルゴリズムがヒープソート（heap sort）である。

　ヒープ（heap）*2は2分木の節を配列の添字に対応させて表現し、「親＜子」または「親＞子」となるようなデータ構造である。ヒープは子の添字を2で割ることで親の添字がわかる。「親＞子」の場合、根に最大値があることを利用するのがヒープソートである。

例：次の配列が与えられたときに、ヒープソートで小さい順に並べ替える

1	2	3	4	5	6	7
70	60	50	40	30	20	10

　ここでは「親＞子」として考える。配列の添字に、根を配列1、節kの左を2k、節kの右を2k+1として対応させる。配列とその値のセットで考えていく。上記の配列をヒープに変換すると次のようになる。

　根から最大値を取り出して、配列の末尾に置く。

　次にヒープを再構成して、根から最大値を取り出して、配列の末尾に置く。

　さらにヒープを再構成して、根から最大値を取り出して、配列の末尾に置く。

　同様に繰り返していく。

↑

ヒープソートの計算量 †

　ヒープソートの平均計算量は $O~$~n~\log_2~n~$$ である。

↑

バケットソート（ビンソート） †

　バケットソート（bucket sort）とは、あらかじめデータがとりうる値すべての容器（バケツ＝bucket）を順番通りに並べて用意しておいて、値を対応する容器に移すことでソートを行うアルゴリズムである。ビンソート（bin sort）とも呼ばれる（ビンとは物を閉まっておくための蓋付きの容器のことである）。

↑

バケットソートの特徴 †

　特徴から明らかだが、とりうる値がわかっていなければ、容器を準備できないので、バケットソートは使えない。

　また、容器という作業領域が必要となるので、データの範囲が大きすぎると、それに比例してメモリを大量に消費してしまう。例えば、データの範囲が1～1,024かつバケツひとつに1バイトの領域が必要なら、すべてのバケツを用意するだけで1Kバイトの領域が必要となってしまう。

　さらに、ソート対象のデータは重複が許されないという大きな特徴を持つ。バケツは想定される値をキーとして用意されるから、同じ値が存在しても対応する複数のバケツを用意できないのである。この点を改良したソートアルゴリズムに、分布数え上げソートがある。

↑

バケットソートのアルゴリズム †

　ビンソートは、ソートしたい値を配列番号とするので、配列への入力が一番の重要部分となる。

例：テストの成績で考えてみる。

　並べる対象となるデータ要素をキーと呼ぶ。この例では、出席番号がキーとなる（出席番号は基本的に重複はないので、キーにできる）。そこで、出席番号に対応する配列番号（配列名はDataとしておく）を考える。その配列のデータがテストの点数になる。

　番号順に答案用紙を並べなくても、「配列番号＝出席番号」となる配列に点数を入れていく。

配列要素	[0]	[1]	[2]	[3]	…	30	…	[40]
データ	-1	50	82	38	…	-1	…	69

注意
- [0]は使わない。
- 配列は最初に-1で初期化する。

　出席番号は1から始まる一方で、配列の要素番号は0から始まる。よって、上記のように、Data[0]から点数を格納し始める。ただし、欠席してテストを受けていなく、点数がない生徒がいるときは、Data[その生徒の出席番号]には-1で初期化しておく。

　後は、配列を先頭から見ていけば、出席番号順になっている（出席番号順にソートされている）。

↑

実験 †

↑

Javaによるバケットソートの実験 †

　バケットソートのJavaプログラム（BucketSort.java）を作成してみる。

　ビンソートの入力処理用のメソッドをInputDataとする。このメソッドは入力が成功したか失敗したか、失敗したらどのような失敗かをmainメソッドに返す必要がある。この値をfinalを付けた定数で定義した。

 
 
 
 
 
 
 
 
-
|
|
|
|
|
|
|
|
|
|
-
-
|
!
!
|
|
|
-
|
|
|
-
|
|
|
-
|
-
|
|
!
|
|
-
|
!
!
!
|
|
|
-
-
|
|
|
|
|
|
-
|
!
|
|
-
|
!
|
|
|
|
-
|
|
-
|
!
|
!
|
|
-
|
|
|
|
-
|
-
|
-
|
-
|
!
!
|
|
|
|
!
!

/*
 * BucketSort：バケットソートにより出席番号順に点数を並べて表示する
 * 入力：出席番号、点数
 * 出力：番号順の点数
 */
import java.io.*;
import java.text.DecimalFormat;
 
public class BucketSort {
    //InputDataが返す値を定義する
    static final int SUCCESS=0;    //成功
    static final int FINISH=1;    //入力終了
    static final int NUM_ERR=2;    //番号が範囲を越えている
    static final int DUP_ERR=3;    //入力済み
    
    static int[] Data=new int[41];    //ソートした値を記録する配列（必要があればここを修正）
    
    //InitData：データの配列を-1で初期化する
    //戻り値：なし
    static void InitData(){
        for(int i=0;i < Data.length;i++){
            Data[i]=-1;
        }
    }
    
    //ShowData：データの配列を表示する
    //戻り値：なし
    static void ShowData(){
        //1行分を改行
        System.out.println("");
        
        for(int i=1;i < Data.length;i++){
            //表示桁を揃える
            String si=new DecimalFormat("00").format(i);
            
            if(Data[i] >= 0){
                System.out.print(si+" : "+Data[i]+"点\t");
            }else{
                //欠席の場合の表示
                System.out.print(si+" : ----\t");
            }
            
            //5つごとに改行を入れる
            if(i%5 == 0){
                System.out.println("");
            }
        }
    }
    
    //InputData：データを入力する
    //戻り値：成功（SUCCESS）、番号エラー（NUM_ERROR）、終了（FINISH）
    static int InputData(){
        try{
            BufferedReader rd=new BufferedReader(new InputStreamReader(System.in));
            System.out.print("番号（終了：E）");
            String ln=rd.readLine();
            int n=Integer.parseInt(ln);
            
            //番号が範囲を越えている
            if(n <= 0 || Data.length <= n){
                return NUM_ERR;
            }
            
            //重複している
            if(Data[n] > -1){
                return DUP_ERR;
            }
            
            System.out.print("点数：");
            ln=rd.readLine();
            Data[n]=Integer.parseInt(ln);
        }catch(IOException e){
            System.out.println("入力エラー");
            System.exit(0);
        }catch(NumberFormatException e){
            return FINISH;    //数字以外が入力されたら終了
        }
        return SUCCESS;
    }
    
    //main
    public static void main(String[] args) {
        //配列を-1で初期化する
        InitData();
        
        //データを入力し配列に記録する
        while(true){
            int ret=InputData();
            if(ret == NUM_ERR){
                System.out.println("番号が範囲を越えている。");
            }else if(ret == DUP_ERR){
                System.out.println("入力済みである。");
            }else if(ret == FINISH){
                break;    //終了する
            }
        }
        
        //表示する
        //配列の先頭は表示しない
        ShowData();
    }
}

　実行すると次のようになる。

>java BucketSort
番号（終了：E）1
点数：10
番号（終了：E）2
点数：33
番号（終了：E）3
点数：83
番号（終了：E）4
点数：65
番号（終了：E）6
点数：100
番号（終了：E）7
点数：90
番号（終了：E）10
点数：38
番号（終了：E）50
番号が範囲を越えている。
番号（終了：E）10
入力済みである。
番号（終了：E）E

01 : 10点	02 : 33点	03 : 83点	04 : 65点	05 : ----	
06 : 100点	07 : 90点	08 : ----	09 : ----	10 : 38点	
11 : ----	12 : ----	13 : ----	14 : ----	15 : ----	
16 : ----	17 : ----	18 : ----	19 : ----	20 : ----	
21 : ----	22 : ----	23 : ----	24 : ----	25 : ----	
26 : ----	27 : ----	28 : ----	29 : ----	30 : ----	
31 : ----	32 : ----	33 : ----	34 : ----	35 : ----	
36 : ----	37 : ----	38 : ----	39 : ----	40 : ----

↑

分布数え上げソート †

　分布数え上げソート（counting sort）とは、ソート対象のデータをキーにして、キーの出現回数とその累積度数分布を計算して利用するソートアルゴリズムである。バケットソートと同じようにキーとなるデータがとりうる値の範囲をあらかじめ知っておく必要がある。バケットソートはキーの重複に対応していなかったが、分布数え上げソートではキーの重複に対応している。

　特徴として、バケットソートと同様に作業領域がたくさん必要となる。しかし大きな作業領域と引き換えにデータの大小を比較しなくてもよいので、高速なソートを実現できる。

↑

まとめ †

　各種ソートアルゴリズムのオーダーをまとめておく。

アルゴリズム名	オーダー
バブルソート	$O~$~n^2~$$
選択ソート	$O~$~n^2~$$
挿入ソート	$O~$~n^2~$$
シェルソート	$O~$~n^{\frac{3}{2}}~$$
ヒープソート	$O~$~n~\log_2~n~$$
クイックソート	$O~$~n~\log_2~n~$$

　n2の関数が赤色、n3/2の関数が緑色、nlog2nの関数が青色である。上のグラフからわかるように、圧倒的に赤色のほうがnの値が増えるにつれて増加していることがわかる。また、一番効率がよいのは青色であることがわかる。

　計算量のオーダーだけで考えるとクイックソートなどが一番効率がよい。しかしながら、厳密には空間量のオーダーも考える必要がある（ソートにおいてはあまり重要でない）。さらに、どのソートアルゴリズムを使うかは、データがどのような値をとるか調べることも重要である。極端な例だと、1万件のデータでも0と1しかない数列ならば、0の数を数えたほうが早い。

↑

参考文献 †

講義資料・ノート
『超図解mini　基本情報技術者試験　平成19年度版』
『1週間で分かる基本情報技術者集中ゼミ【午前編】　2006春秋』
『1週間で分かる基本情報技術者集中ゼミ【午後編】　2006春秋』
『Eclipseによる体験学習　Javaではじめるアルゴリズム入門』

*1 小数点切り捨て
*2 ヒープの元の意味は「モノを積み上げた山」のことである。

Top / ソートソート

目次 †

ソートとは †

バブルソート（基本交換法、隣接交換法） †

バブルソートの流れ図 †

バブルソートの計算量 †

選択ソート（基本選択法、選択法） †

選択ソートの流れ図 †

選択ソートの計算量 †

挿入ソート（基本挿入法、挿入法：intersion sort） †

挿入ソートの流れ図 †

挿入ソートのアルゴリズム †

挿入ソートの計算量 †

最良計算量 †

最悪計算量 †

平均計算量 †

シェルソート（改良挿入法） †

シェルソートの流れ図 †

シェルソートの計算量 †

クイックソート †

クイックソートのアルゴリズム †

クイックソートの計算量 †

最良計算量 †

最悪計算量 †

平均計算量 †

マージソート †

マージソートのアルゴリズム †

マージソートの計算量 †

ヒープソート †

ヒープソートの計算量 †

バケットソート（ビンソート） †

バケットソートの特徴 †

バケットソートのアルゴリズム †

実験 †

Javaによるバケットソートの実験 †

分布数え上げソート †

まとめ †

参考文献 †

Top / ソート
ソート