線形時間のソート

ソートアルゴリズムにおいて，ソート順が入力要素の比較にのみ基づいて決定されるものを比較ソート(comparison sort)といいます．比較ソートでは，n個の要素をソートするために最悪Ω(nlgn)回の比較を行わなければなりません．ということなので，定数倍を除くとマージソートやヒープソートより早い比較ソートは存在しないのです．

<!-- ここまでコピペ -->

そんな中，O(n)で動作するようなやばいソートもあります．例えば，計数ソート，基数ソート，バケットソートなど…．

■計数ソート(counting sort)
このソートでは，配列aがn個の要素a₀, a₁, …a_n-1,を持っていた時，以下を仮定します．
0≦a_i<k
で，次のように処理を進めます．
1.配列aにおいて，iに等しい要素の個数c_iを計算
2.1.の結果を用いて，c_iがi以下の要素の個数を含むように計算
3.配列aの各要素a_iがどこに位置するかをc_aiで調べ，出力配列bに順次代入．

k=O(n)の時，このソートの計算量はO(n)です．

□コード

view plainprint?

1. // 計数ソート  
2. void countingSort(int[] a, int k){  
3.  int n=a.length;  
4.  int[] b=new int[n];  
5.  int[] c=new int[k];  
6.  for(int i=0; i<n; i++)  
7.   c[a[i]]++;  
8.  // c[i]はiに等しい要素の個数を含んでいる  
9.  c[0]--;  
10.  for(int i=1; i<k; i++)  
11.   c[i]+=c[i-1];  
12.  // c[i]はi以下の要素の個数-1を含んでいる  
13.  for(int i=n-1; i>=0; i--)  
14.   b[c[a[i]]--]=a[i];  
15.  System.arraycopy(b, 0, a, 0, n);  
16. }  

// 計数ソート
void countingSort(int[] a, int k){
 int n=a.length;
 int[] b=new int[n];
 int[] c=new int[k];
 for(int i=0; i<n; i++)
  c[a[i]]++;
 // c[i]はiに等しい要素の個数を含んでいる
 c[0]--;
 for(int i=1; i<k; i++)
  c[i]+=c[i-1];
 // c[i]はi以下の要素の個数-1を含んでいる
 for(int i=n-1; i>=0; i--)
  b[c[a[i]]--]=a[i];
 System.arraycopy(b, 0, a, 0, n);
}

■基数ソート(radix sort)
基数ソートは，i桁目に関するソートを最下位桁から最上位桁まで繰り返します．
ソートは安定ソートなら何でもいいのですが，各桁の値のとる範囲が小さければ計数ソートを使うのが妥当です．
要素数がn，各桁の値の範囲が0からk-1(k種類)，桁数がdであるとします．各桁の計数ソートの実行時間は，O(n+k)となります．計数ソートはd回行われるので，基数ソートの実行時間はO(dn+kd)となります．dが定数，k=O(n)ならば，結局O(n)になるので，線形時間で動作するという事になります．

□適用例
ソートする配列

329

457

657

839

436

720

355

1桁目(1の位)に注目してソート

720

355

436

457

657

329

839

2桁目(10の位)に注目してソート．安定ソートを用いているので，下2桁はソートされています．

720

329

436

839

355

457

657

3桁目(100の位)に注目してソート．これで完全にソートされました．

329

355

436

457

657

720

839

□コード
各桁の値は，10進数ではなく2進数で計算しています．2進数では，各桁の値をシフト演算で求める事が出来る，という利点があります．

view plainprint?

1. // 基数ソート  
2. void radixSort(int[] a){  
3.  for(int i=0; i<32; i++)  
4.   // 安定ソートを用いてi桁目に関する配列をソートする  
5.   countingSort(a, i);  
6. }  
7.   
8. void countingSort(int[] a, int d){  
9.  int n=a.length;  
10.  int[] b=new int[n];  
11.  int[] c=new int[2];  
12.  for(int i=0; i<n; i++)  
13.   c[(a[i]>>d)&1]++;  
14.  c[0]--;  
15.  c[1]+=c[0];  
16.  for(int i=n-1; i>=0; i--)  
17.   b[c[(a[i]>>d)&1]--]=a[i];  
18.  System.arraycopy(b, 0, a, 0, n);  
19. }  

// 基数ソート
void radixSort(int[] a){
 for(int i=0; i<32; i++)
  // 安定ソートを用いてi桁目に関する配列をソートする
  countingSort(a, i);
}

void countingSort(int[] a, int d){
 int n=a.length;
 int[] b=new int[n];
 int[] c=new int[2];
 for(int i=0; i<n; i++)
  c[(a[i]>>d)&1]++;
 c[0]--;
 c[1]+=c[0];
 for(int i=n-1; i>=0; i--)
  b[c[(a[i]>>d)&1]--]=a[i];
 System.arraycopy(b, 0, a, 0, n);
}

■バケットソート(bucket sort)
バケットソートでは，配列の各要素が区間[0, 1)に一様分布する実数だと仮定します．
配列aの要素数をnとします．
このソートでは，区間[0, 1)をn等分し，n個の要素を各バケットに分配します．
例えばn=10なら，
[0,0.1)，[0.1,0.2)，[0.2,0.3)，[0.3,0.4)，[0.4,0.5)，[0.5,0.6)，[0.6,0.7)，[0.7,0.8)，[0.8,0.9)，[0.9,1)．
その後，各バケットをソートし，順に繋げていくだけです．
この時のソートアルゴリズムは挿入ソートを用います．
挿入ソートの計算量はO(n²)(n個の要素に対して)ですが，色々あってほぼΘ(1)となります．さらに，バケット数がnですので，結果的にO(n)になるのですよ．

□コード

view plainprint?

1. // バケットソート  
2. void bucketSort(double[] a){  
3.  int n=a.length;  
4.  LinkedList<Double>[] list=new LinkedList[n];  
5.  for(int i=0; i<n; i++)  
6.   list[i]=new LinkedList<Double>();  
7.  for(int i=0; i<n; i++)  
8.   list[(int)(n*a[i])].add(a[i]);  
9.  for(int i=0, k=0; i<n; i++){  
10.   Double[] b=list[i].toArray(new Double[0]);  
11.   // リストlist[i]を挿入ソートでソートする  
12.   insertionSort(b);  
13.   for(double d : b)  
14.    a[k++]=d;  
15.  }  
16. }  
17.   
18. // 挿入ソート  
19. void insertionSort(Double[] a){  
20.  int n=a.length;  
21.  for(int j=1; j<n; j++){  
22.   double key=a[j];  
23.   int i=j-1;  
24.   while(i>=0&&a[i]>key){  
25.    a[i+1]=a[i];  
26.    i--;  
27.   }  
28.   a[i+1]=key;  
29.  }  
30. }  

// バケットソート
void bucketSort(double[] a){
 int n=a.length;
 LinkedList<Double>[] list=new LinkedList[n];
 for(int i=0; i<n; i++)
  list[i]=new LinkedList<Double>();
 for(int i=0; i<n; i++)
  list[(int)(n*a[i])].add(a[i]);
 for(int i=0, k=0; i<n; i++){
  Double[] b=list[i].toArray(new Double[0]);
  // リストlist[i]を挿入ソートでソートする
  insertionSort(b);
  for(double d : b)
   a[k++]=d;
 }
}

// 挿入ソート
void insertionSort(Double[] a){
 int n=a.length;
 for(int j=1; j<n; j++){
  double key=a[j];
  int i=j-1;
  while(i>=0&&a[i]>key){
   a[i+1]=a[i];
   i--;
  }
  a[i+1]=key;
 }
}

元ネタは，アルゴリズムイントロダクション第1巻より第9章 線形時間のソーティングでした．