4.整列のアルゴリズム
整列(ソート)
データ
5,3,8,1,6,21,11
ソートアルゴリズム
1,3,5,6,8,11,21
データ
k,a,l,c,d,s
ソートアルゴリズム
a,c,d,k,l.s
内部整列と外部整列
CPU
高速アクセス
全データ
メモリ
CPU
高速アクセス
データの一部
メモリ
低速アクセス
全データ
ディスク
内部整列
外部整列
仮定と要求
内部整列
どのデータにも均等な時間でアクセスできる。
できるだけ高速に整列したい。
(理想的なRAMモデル上のアルゴリズムではこっち)
外部整列
CPU-メモリ間のデータ転送速度より、
ディスク-メモリ間のデータ転送速度が極端に遅い。
全体の整列をできるだけ高速にしたい。
(ディスクーメモリ間のデータ転送をあまり行わないように
する。)
ソートアルゴリズムの種類
バブルソート
挿入ソート
選択ソート
ヒープソート
クイックソート
マージソート
バケットソート
基数ソート
:教科書に掲載
ソートアルゴリズムの分類
原理
比較による
比較によらない
バブルソート
時
間
量
(
速
度
)
O(n^2)
選択ソート
バケットソート
挿入ソート
基数ソート
クイックソート
計算量はO(n)
O(n log n)
ヒープソート
マージソート
だけど条件付き
入出力形態
入力:
5 3
配列A A[0] A[1]
8
1
A[i]
4
13
2
9
A[n-1]
n 個
2
1
出力
配列A A[0] A[1]
(終了状態):
3
4
5
8
9
13
A[n-1]
n個
連結リストで入力されるとしてもいいのですが、
配列に入力データがあるとして説明します。
バブルソート
方針
隣同士比べて、小さいほうを上(添字の小さい方)に
順にもっていく。
先頭の方は、ソートされている状態にしておく。
これらを繰り返して、全体をソートする。
バブルソートの動き1
A
0
5
5
5
5
5
5
5
1
1
2
3
3
3
3
3
3
5
8
1
8
1
8
1
8
1
8
1
1
8
1
3
8
8
4 4
5 13
4
4
13
2
2
2
非交換
4
4
2
4
2
4
2
4
6
9
2
13
13
13
13
13
13
7
2
9
9
9
9
9
9
9
3
交換
3
バブルソートの動き2
A
0 1
1 5
2 3
3 8
4 2
5 4
ソ
ー
ト
済
み
繰
り
返
し
交
換
適
用
1
1
1
1
1
1
1
2
5
2
2
2
2
2
2
3
5
3
4
3
4
3
4
3
4
3
4
4
5
5
5
5
5
8
9
8
9
8
9
8
9
8
9
13
13
13
13
13
3
8
4
6 13
9
8
9
7 9
13
13
バブルソートの実現1
/*交換用の関数
A[i]とA[j]を交換する。*/
void swap(int i ,int j, datatype *A)
{
datatype temp; /* データの一次保存用*/
temp=A[i];
A[i]=A[j];
A[j]=temp;
return;
}
バブルソートの実現2
/* バブルソート*/
void bubble(datatype *A)
{
int i,j; /* カウンタ*/
for(i=0;i<n;i++)
{
for(j=n-1;j>i;j--)
{
if(A[j-1]>A[j])
{
swap(j-1,j,A);
}
}
}
return;
}
バブルソートの計算量
1回目の外側のループで、n-1回の比較と交換
2回目
n-2
・
・
・
n-1回目の外側のループで、1回の比較と交換
よって、 (n  1)  (n  2) 
時間量
2
O(n )
n(n  1)
1  i 
2
i 1
n 1
のアルゴリズム
選択ソート
方針
先頭から順に、その位置に入るデータを決める。
(最小値を求める方法で選択する。)
その位置のデータと選択されたデータを交換する。
これらを繰り返して、全体をソートする。
ソート済み
残りのデータで最小値を選択
選択ソートの動き1(最小値発
見)
探
索
済
0 5 み
5
5
5
5
5
5
5
3
3
3
3
3
3
3
3
8
3 1
8
1
8
1
8
1
8
1
8
1
8
1
8
1
5
4
4
4
4
4
4
4
4
A
1
2
未
探
索
1
3
8
4
5
4
13
13
13
13
13
13
13
13
13
6
9
9
9
9
9
9
9
9
9
7
2
2
2
2
2
2
2
2
2
min=0
min=1 min=1min=3 min=3 min=3 min=3 min=3
選択ソートの動き2
A
済
2
1
2
1
2
1
2
1
2
1
2
8
3
3
3
3
3
3
5
5
4
4
4
4
4
4
4
5
5
5
5
5
13
13
13
13
8
8
8
9
9
9
9
9
9
9
9
2
3
8
8
8
13
13
13
0
1
1
2
1
1
3
2
4
5
8 最
小
5 値
4 発
見
13
6
7
3
min=7
min=7 min=4
min=4 min=7 min=6
min=7
選択ソートの実現1
(最小値を求めるアルゴリズム)
/*選択用の関数、A[i]からA[j]をまでの最小値を求める*/
int select_min(int i ,int j, datatype *A)
{
int k;
/* カウンタ */
int min; /* 仮の最小値の添字*/
min=i;
for(k=i;k<=j;k++)
{
if(a[min]>a[k]){min=k;}
}
return k;
}
選択ソートの実現2
/* 選択ソート*/
void select(datatype *A)
{
int i; /* カウンタ*/
int min; /* 最小値の添字*/
for(i=0;i<n;i++)
{
min=select_min(i,n-1,A);
swap(i,min,A);
}
return;
}
なお、説明の都合上、関数select_minを作ったが、
関数呼び出しで余分に時間がとられるので、
実際は2重ループにするほうが速いと思われる。
(でも、オーダーでは、同じ。)
選択ソートの計算量
1回目のselect_minで、n-1回の比較
2回目
n-2
・
・
・
n-1回目のselect_minで、1回の比較
よって、 (n  1)  (n  2) 
n(n  1)
1  i 
回の比較
2
i 1
n 1
交換は、n回
時間量
2
O(n )
のアルゴリズム
挿入ソート
方針
先頭の方は、ソート済みの状態にしておく。
未ソートのデータを、ソート済みの列に挿入し、
ソート済みの列を1つ長くする。
これらを繰り返して、全体をソートする。
ソート済み
未ソートデータ
挿入ソートの動き
ソ
ー
ト
済
A
0 5
3
3
1
1
1
1
1
3
5
5
3
3
3
2
8
3 1
8
1
8
1
3
5
4
4
4
3
8
4
4
5
8
5
8
4
4
5
8
1
2
未
ソ
ー
ト
4
5
4
13
13
13
13
13
13
9
5
8
6
9
9
9
9
9
9
13
9
7
2
2
2
2
2
2
2
13
挿入ソートの実現1
(挿入位置を求める)
/*挿入位置を見つける関数、
A[0]からA[i-1]までソート済みのとき、
A[i]の順番を求める。*/
int find_pos(int i ,datatype *A)
{
int j;
/* カウンタ */
for(j=0;j<i;j++)
{
if(A[j]>A[i]){break;}
}
return j;
}
挿入ソートの実現2
/* 挿入ソート*/
void insert(datatype *A)
{
int i,j; /* カウンタ*/
int pos; /* 挿入位置の添字*/
for(i=0;i<n;i++)
{
pos=find_pos(i,A);
for(j=n-1;j<pos;j--)
{
swap(j-1,j,A);
}
}
return;
}
挿入ソートの計算量
n-1回目の外側のループで、n-1回の比較あるいは交換
n-2回目
n-2回の
・
・
・
1回目
1回の比較あるいは交換
よって、 比較と交換回数の合計は、
(n  1)  (n  2) 
時間量
2
n(n  1)
1  i 
2
i 1
O(n )
n 1
のアルゴリズム
(挿入ソートを元に高速化した、シェルソートっていうものもあるが省略。)
ヒープソート
方針
ヒープを使ってソートする。
先頭から順にヒープに挿入し、データ全体をヒープ化する。
最大値を取り出して、最後のデータにする。
0
13
1
3
7 1
2
2
4
9
4
3
5
5
6
8
ヒープソートの動き前半1
0
A 5
5
配列
1 2 3
4
3
4
8
1
ヒープ
5 6 7
13 9 2

0
3
ヒープ
8
1
4
5
13 9 2
未ヒープ
0
5
ヒープ
3
8
1
4
未ヒープ
13
9
2
5
1
3
ヒープソートの動き前半2
配列
1 2 3
4
3 5
4
0
A 8
1
ヒープ
ヒープ
0 8
5 6 7
13 9 2
2
1 3
未ヒープ
5
ちょっと省略
0
13
0
1
A 13 4
ヒープ
2
9
3
2
4
3
5
5
6
2
9
1 4
7
3 2
8 1
7
1
3
4
5
5
6
8
ヒープソートの動き後半1
0
1
0
A 13 4
2
3
4
5
6
9
2
3
5
8 1
13
7
1 4
3 2
ヒープ
最大要素を、ヒープから削除し
後ろに挿入
2
9
7
3
4
5
5
6
8
1
0
9
0 1 2
A 9 4 8
ヒープ
3
4
5 6
7
2
3
5 1
13
ソート済
2
1 4
3 2
8
3
4
5
5
6
1
ヒープソートの動き後半2
0 1
A 8 4
2
3
4
5
6
7
5 2
3
1
9
13
ヒープ
ソート済
0
8
1 4
3 2
3
4
ちょっと省略
A 1
2
3
4 5
8
9 13
ソート済
2
5

5
1
ヒープソートの実現
void heap_sort(datatype *A)
{
int i;
/* カウンタ */
datatype max; /*最大値*/
/* ヒープ化 */
for(i=0;i<n;i++){insert_heap(A[i],A);}
/* 最大値を順に後ろに挿入*/
for(i=n-1;i>=0;i--)
{
max=delete_max(A);
A[i]=max;
}
return ;
}
ヒープソートの計算量
ヒープ化の部分
操作insert_heap(A) 1回あたり、時間量 O(log n)
n回行うので、時間量
O(n log n)
最大値発見と移動の部分
操作delete_max(A) 1回あたり、時間量 O(log n)
n回行うので、時間量
O(n log n)
これらは、1づつ行われるので、
時間量 O(n log n)
のアルゴリズム
(実は、ヒープ化の部分は、
O(n) の時間量で実現する方法もあるが、省略)
マージソート
方針
問題を小分けにして、あとで組み合わせる。(分割統治法)
小分けした問題は、再帰的にソートする。
もしソートされた2つの配列があれば、
それらのそれらを組み合わせて、
大きいソートの列をつくる。(マージ操作)
B 1
3
5
8
A 1
C
2
4
9 13
2
3
4 5
8
9
13
マージの動き
B 1
3
5
2
4
9 13
B 1
3
5
2
4
9 13
C
C
8
8
B 1
3
5
2
4
9 13
C
8
A
A 1
ソート済み
A 1
2
分割
もし2つのソート列があったら、
マージ操作によって、長いソート列がえられることが
わかった。
どうやって、2つのソート列を作るのか?
おなじ問題で、
問題のサイズが小さくなっていることに
注意する。
列を二等分にして、再帰的にソートする。
マージソート動き前半(分割)
0
1
2
3
4
A 5
A[0]からA[3]まで
ソートして。
3
8
1
4
5 6 7
13 9 2
A[4]からA[7]まで
ソートして。
0
1
2
3
4
5
m_sort(0,1,A)
3
8
1
4
5 6
13 9
7
2
m_sort(2,3,A)
0
1
2
3
4
5
3
8
1
4
0
1
5
3
3
2
8
1
4
4
5
13
5
13
6
7
9
2
6
7
9
2
マージソート動き後半(マージ)
0
1
2
5
3
8
3
4
1
4
5
13
6
9
7
5
13
6
7
2
marge
0
1
3
5
0
2
4
3
4
1 8
1
26
2
3
4
5
5
8
2
4
1 3
A
0
1
2
3
4
5
1
2
3 4
5
8
6 7
9 13
6 7
9 13
79
マージの実現
/* 配列Bと配列Cを配列Aにマージする。概略です。細かい部分は省略*/
void marge(int posA,datatype *A,datatype *B ,int numB,datatype *C,int numC)
{
int iA=0,iB=0,iC=0;
/* カウンタ*/
while(iA<=numB+numC-1)
{
if(B[iB]<C[iC])
{
A[posA+iA]=B[iB];
iB++;
}
else
{
A[posA+iA]=C[iC];
iC++
}
iA++;
}
return;
}
マージソートの実現
/*概略です。細かい部分は省略*/
void marge_sort(int left,int right,datatype *A)
{
int mid;
/* 配列の中央 */
datatype B[n],C[n]; /*作業用の配列*/
if(left==right)return;
mid=(left+right)/2;
marge_sort(left,mid,A);
marge_sort(mid,right,A);
/*ここに、A[left]からA[mid]を配列Bに、
A[mid]からA[right]を配列Cにコピーする処理を書く。 */
marge(left,A,mid-left,B,right-mid,C);
return;
}
マージソートの計算量
解析を簡単にするため、データを n  2k 個あると仮定します。
まず、マージの計算量 M (n) を考えます。
明らかに、出来上がるソート列の長さに比例した時間量です。
 M (n)  O(n)
マージソートの時間量を T (n) とします。
以下の再帰式を満たします。
T (1)  c1



n
n
n
T (n)  T ( )  T ( )  M (n)  2T ( )  c2 n


2
2
2
T (n)  O(n log n)
これを解いて、
クイックソート
方針
問題を小分けにして、あとで組み合わせる。(分割統治法)
前半部分は特定要素(ピボット)より小さく、
後半部分はピボットより大きく分割する。
ピボットの位置を確定し、
小分けした問題は、再帰的にソートする。
5 6 7
0 1 2 3 4
A 5 3 8 1 4 13 9 2
ピボット
A 4
3
小さい
2 1
5
13
9
8
大きい
説明上の注意
全てのデータが異なるとして、
説明します。
クイックソートのアルゴリズムでは、
ピボットの選び方にあいまいさがあります。
(自由度といったほうがいいかも。)
ここでは、ソート範囲の最初の要素をピボットとして
説明します。
実際に、
プログラミングするときは、
もっといろんな状況を考えましょう。
クイックソートの動き前半(分割)
A 5
3
8
1
13
4
9
ピボットより小さい
値を探す
ピボットより
大きい値を探す
A 5
3
2 1
2
4
13 9 8
探索が交差したら終了。
ピボットと前半最後の要素を交換し、あとは再帰呼び出し。
A 4
3
2 1
5
13 9
8
クイックソートの動き後半(再帰)
1
0
2
3
4
A 4 3 2 1 5
A[0]からA[4]までを
ソートして
q_sort(0,3,A)
0
1
A 4
3
0
1
A 1
3
2
3
4
5
2 1
3 位置確定
2
2
4
以下省略
5 6 7
13 9 8
A[5]からA[7]までを
ソートして
5 6 7
13 9 8
5
6
9 8
7
13
クイックソートの実現1(分割)
/*概略です。細かい部分は省略*/
int partition(int left,int right,datatype *A)
{
int i,j;
/*カウンタ*/
i=left+1;
j=right;
for(;;)
{
while(A[i]<A[left]){i++;}
while(A[j]>A[left]){j--;}
if(i>=j){break;}
swap(i,j,A);
}
return(i);
}
クイックソートの実現2(再帰)
/*概略です。細かい部分は省略*/
void quick_sort(int left,int right,datatype *A)
{
int pos;
/*分割位置 */
pos=partition(left,right,A);
swap(left,pos,A);
quick_sort(left,pos-1,A);
quick_sort(pos+1,right,A);
return;
}
クイックソートの計算量
クイックソートは、
最悪時の計算量と平均の計算量が異なります。
これらは、
ピボットの選び方にもよりますが、
どんな選び方によっても最悪のデータ初期配置があります。
ここでは、最悪計算量と、平均計算量の両方を考えます。
クイックソートの最悪計算量
まず、関数partition(i,j,A)の1回の時間量は、
j-i+1に比例した時間量です。
再帰の同じ深さで、parttition()の時間量を
総計すると O ( n) になります。
いつも0個、ピボット、残りのように
分割されるのが最悪の場合です。
つまり、ピボットとしていつも最小値が
選択されたりするのが最悪です。
(他にも最悪の場合はあります。)
このときでも、partition(i,j,A)の実行に
は、j-i+1回の演算が必要です。
これは、結局選択ソートの実行と同じ
ようになり、
最悪時間量
O(n2 )
のアルゴリズムです。
クイックソートの平均計算量
初期状態として、 n ! 通りの並びが
すべて等確率だとしましょう。
クイックソートの時間量 を T (n) とします。
ピボットが i 番目のときには、
以下の漸化式を満たす。
T (n)  T (i  1)  T (n  i)  c(n  1)
小さい方の分割を
再帰的にソートする分
大きい方の分割を
再帰的にソートする分
partition()分
ピボットの順位は、n通り全て均等におこるので、
それらを総和して、nで割ったものが平均時間量
1 n
T (n)  T (i  1)  T (n  i )  c(n  1)
n i 1
T (n)  O(n log n)
2分探索木のときの解析と同様にして、
ちょっと寄り道
(一個一個が大きいデータを処理する工夫)
配列A A[0] A[1]
A[i]
A[i]
A[j]
A[n-1]
名前、
生年月日、
住所、
経歴、
趣味
A[j]
交換は大変
大きいデータを処理する工夫2
工夫:大きいデータは動かさずに、
たどり方だけがわかればいい。
data1
data2
配列A A[0] A[1]
A[i]
A[n-1]
0
1
i
n-1
配列B B[0] B[1]
B[i]
B[n-1]
添字の配列Bだけを操作して、配列Aは動かさない。
data2
配列A A[0] A[1]
swap(0,i); (data1が最小値のとき。)
data1
A[i]
A[n-1]
i
1
配列B B[0] B[1]
0
B[i]
n-1
B[n-1]
大きいデータを処理する工夫3
イメージ
data2
配列A A[0] A[1]
data1
A[i]
A[n-1]
data2
配列A A[0] A[1]
data1
A[i]
A[n-1]
ソート順は、下の情報からえられる。
(配列の添字の利用だけでなく、ポインタでも同様のことができる。)
問題とアルゴリズム
(復習p.18参照)
具体的なアルゴリズムを作ることは、
問題の難しさ(問題固有の計算量)の上界を与えています。
最適なアルゴリズムの存在範囲
アルゴリズムがない問題は、難しさがわからない。
ソート問題
の難しさ
バブルソート発見 O(n2 )
O(n2 )
ソート問題
の難しさ
マージソート発見 O(n log n)
ソート問題
の難しさ
O(n log n)
O(n2 )
問題と下界
一方、問題の難しさの範囲を下の方から狭めるには、
問題を解くアルゴリズムが無いことを示さないといけない。
実は、1つのアルゴリズムを作ることより、アルゴリズムが存在
しないことを示すことの方が難しい。
最適なアルゴリズムの存在範囲
ソート問題
の難しさ
O(n log n)
O(n2 )
?
ソート問題
の難しさ
アルゴリズムが
存在しない。
?
O(n log n)
O(n2 )
ソート問題の場合は、なんとか示せます。
アルゴリズムと決定木
(比較によるソートの下界証明の準備)
決定木の根:初期状態
決定木の節点:それまでの計算の状態
決定木の枝
初期状態
:アルゴリズムの進行による状態の遷移
状態遷移
決定木の葉:終了状態
いままでの、データ構造の木ではなくて、
概念的、抽象的なもの。
根からの道が、
アルゴリズムの実行順に対応し、
根から葉までの道の長さが時間量に対応
します。
終了状態
3要素バブルソートの決定木
abc
acb
bac
bca
cab
cba
結果の可能性
1:true
abc
bac
bca
1
A[0]<A[1]?
(b<c?)
acb
cab
cba
1
bac
A:b a c
1
0
bac
bca
配列Aの内容
0:false
A:a b c
abc
A:a b c
A[1]<A[2]?
(b<c?)
A:a b c
A:a c b
A[0]<A[1]?
(a<c?)
acb
cab
cba
A:b a c
A:a c b
0
A[1]<A[2]?
(a<c?)
bca
A:b c a
0
A:c a b
1
A[1]<A[2]?
(a<c?)
0
cab
cba
A:c a b
A:c b a
ソート問題の下界
どんな入力でもきちんとソートするには、
決定木にn!個以上の葉がなければならない。
それで、アルゴリズムの比較回数は、
決定木の高さで定まる。
最悪時間が良いアルゴリズムは高さが低く、
悪いアルゴリズムは高さが高い。
高さがhの決定木では、高々2h 個の葉 しかない。
よって、
h  log 2 n!  n log n
よって、 ソートアルゴリズムでは少なくとも
(n log n) の時間量が必要である。
ソート問題の難しさ
ソート問題
の難しさ
決定木による証明
アルゴリズム開発
(マージソート
ヒープソート等)
 (n log n)
こんなことを考えるのが、
計算量理論の分野です。
比較によらないソート
バケットソート
データが上限のある整数のような場合に用いる。
データの種類が定数種類しかない場合には、
ハッシュ関数で整数に変えてから用いてもよい。
基数ソート
大きい桁の数に対して、
桁毎にバケットソートをしてソートする。
バケットソート
とりあえず、簡単のために、
データは、
1.重複がなく、
2. 0からm-1の整数
という性質を満足するとしましょう。
(例えば、学籍番号の下2桁とか。)
方針
m個のバケット(配列)を用意して、
データを振り分けていく。
データそのものを配列の添字として使う。
バケットソートの動き1
2
3
6
1
配列A A[0] A[1]
A[i]
-1 -1 -1 -1
配列B B[0] B[1] B[2] B[3]
6
3
配列A A[0] A[1]
0
A[n-1]
-1 -1 -1
2
A[i]
4
0
A[n-1]
-1 -1 -1 3
配列B B[0] B[1] B[2] B[3]
-1
-1
3 6
配列A A[0] A[1]
1
4
1
2
A[i]
4
0
A[n-1]
-1 -1 -1 3
配列B B[0] B[1] B[2] B[3]
-1
-1
-1
-1
B[m-1]
-1
B[m-1]
6 -1
B[6] B[m-1]
バケットソートの実現
/*概略です。細かい部分は省略
入力データの配列の型がintであることに注意*/
void bucket_sort(int *A,int *B)
{
int i;
/*カウンタ*/
for(i=0;i<n;i++)
{
B[A[i]]=A[i];
}
return;
}
バケットソートの動き2(添字を用いた場合)
2
3
6
1
配列A A[0] A[1]
A[i]
-1 -1 -1 -1
配列B B[0] B[1] B[2] B[3]
3
6
配列A A[0] A[1]
0
A[n-1]
-1 -1 -1
2
A[i]
4
-1 -1 -1 0
配列B B[0] B[1] B[2] B[3]
-1
3
1
配列A A[0] A[1]
1
4
6
-1
B[m-1]
0
A[n-1]
-1 -1
2
A[i]
4
0
A[n-1]
-1 -1 -1 3
配列B B[0] B[1] B[2] B[3]
-1
-1
-1
B[m-1]
-1
1
B[6] B[m-1]
バケットソートの実現2
/* 配列の添字を用いて、間接的にソート*/
void bucket_sort(int *A,int *B)
{
int i;
/*カウンタ*/
for(i=0;i<n;i++)
{
B[A[i]]=i;
}
return;
}
i番目のデータの参照は、A[B[i]]で行う。
バケットソート(重複あり)
方針
重複した分を、リストとして繋ぐ。
(外部ハッシュ法参照。)
後の基数ソートへの利用では、
重複データのリストへの挿入順序が大事。
(外部ハッシュでは、余り重要ではなかったが。)
バケットソートの動き3(重複あり)
A
B
C
0
2
0
6
1
2
4
1
2
2
5
1
3 0
3
4 2
5 2
4
1
5
7
3
0
4
1 0
2 1
0
3
0
2
4 2
5 2
6 0
6 4
7 5
7 5
先入れ先出しのキューに
しておいたほうがいいです。
バケットソートの実現3(重複あ
り)
/* リストの細かい実現は省略*/
void bucket_sort(int *A,struct cell **B,int *C)
{
int i,j;
/*カウンタ*/
/*配列Bへ挿入*/
for(i=0;i<n;i++){enque(B[A[i]],=i);}
/*ソート順に配列Cへ挿入*/
i=0;
for(j=0;j<m;j++){
while(B[j]が空でない){
C[i]=A[deque(B[j])];
i++;
}
return;
}
バケットソートの計算量
配列1回のアクセスには、定数時間で実行できる。
(RAMモデルの能力を最大限に使っていることに
注意しましょう。)
繰り返し回数は、明らかにデータ数n回です。
また、
配列Bの準備や、走査のために、O(m) の時間量必要です。
最悪時間量
O ( m  n)
のアルゴリズムです。
基数ソート
方針
大きい桁の数に対して、
桁毎にバケットソートをしてソートする。
下位桁から順にバケットソートする。
基数ソートの動き(3桁)
A
0
221
650
1
2
23
3
2
4 106
5 226
6 250
7 126
8 372
47
9
10 215
11 33
0桁で
ソート
A
0 650
1 250
2 221
3
2
4 372
5 23
6
7
33
215
106
8
9 226
10 126
11 47
A
0
2
106
215
1
2
3 221
23
1桁で 4
ソート 5 226
6
7
A
126
33
8 47
9 650
10 250
11 372
0
2桁で
ソート
2
23
1
2
33
3
47
4 106
5 126
6 215
7 221
8 226
9 250
10 372
11 650
基数ソートの実現
/*細かい実現は省略*/
void radix_sort(int *A)
{
int i,j;
/*カウンタ*/
for(k=0;k<max_k;k++)
{
bbucket_sort(A,k); /*バケットソートを第k桁でソートして、
もとの配列に戻すように拡張する。*/
}
return;
}
基数ソートの計算量
バケットソートを桁数分行えばよいので、
k桁数を基数ソートするには、
最悪時間量
O(k (m  n)) のアルゴリズムです。
また、
N
種類のデータを区別するには、
k  logm N
桁必要です。
N n のときには、 結局
O(m log n  n log n) の時間量を持つアルゴリズムです。
だから、バケットソートや基数ソートは、
データ範囲mや、桁数kに注意しましょう。
ダウンロード

4.整列のアルゴリズム