プログラミング技法とデータ構造

ソート(整列)とは

ソート(sort)とは，与えられた値を，値の大小関係により，ある一定の順序により並べ替える操作のことをいう．小さい値から大きい値に並べ替えることを昇順(ascending order)，逆に大きい値から小さい値の順に並べることを降順(descending order)と呼ぶ．

ソートは，整数データだけを扱うものではなく，構造体のようにいくつもの情報をまとめた要素(レコード)単位に対して，検索IDのような整数値や，名前などの五十音順，など要素に含まれる特定の項目により，並べ替えを行うことが一般的にである．

並べ替えの対象となる項目に，複数の要素で等しい値があった時には，並べ替えた後に，その同じ値が連続させることになる．ソートの観点からは，それで問題は起きないが，同じ値の要素がソート操作の前後で，元の位置関係を保つものを，特に，安定な(stable)ソートと呼ぶ．

ソートの種類

ソートには，コンピュータのメモリ容量の大きさの制限がきつかった時代からの歴史的経緯で，内部ソートと外部ソートに分けられている．内部ソートはコンピュータのメモリ上で動作することが前提で，要素にランダムアクセスする操作を伴うソートである．外部ソートは外部記憶装置にデータファイルを格納し，それを順次シーケンシャルに読み出して操作することが前提のものである．現代においてはメモリ容量が格段に大きくなったため，日常的な場面では内部ソートで十分である．しかしながら，メモリ容量の増加だけでなく，コンピュータが扱うデータのサイズ自体が大きくなっており，いまだに外部ソートの必要性も失われたわけではない．

内部ソートの中で，O(n log n)の高速なアルゴリズムとしては，クイックソート，ヒープソートがある．外部ソートの高速なアルゴリズムとしては，マージソートがある．

単純なソート

実用性はないものの，ソートの考え方を学ぶために，単純なソートから説明する．

単純なソートには，ソートを行う3つの基本操作を元にしている．「交換」「選択」「挿入」である．これから単純交換ソート(別名:バブルソート)，単純選択ソート，単純挿入ソート(別名:シャトルソート)がある．

単純交換ソート

ソートの対象として，整数値の配列データを考える．配列の末尾(n-1)とその一つ前(n-2)の要素を比較して，大小関係が逆であれば入れ替える．次にn-2とn-3番目を比較して同じく大小関係が逆なら入れ替える．以下この操作を繰り返し，配列の先頭すなわち配列0まで交換を行う．すると，配列先頭の要素は必ず最小値が格納されることになる．次にまた末尾n-1から今度は2番目の配列1まで同じ操作を繰り返せば，配列1には二番目に小さい値が格納される．末尾からのスキャンをひとつずつ少なくしながら繰り返し，最後にn-1とn-2の比較して必要なら交換を行えば，最終的にソートが完成することとなる．

void bubble_sort(int a[],int n)
{
  int i,j,t;
  for(i=0;i<n-1;i++)
    for(j=n-1; j>i; j--)
      if(a[j-1] >&[j])
      {
         t=a[j];
         a[j]=a[j-1];
         a[j-1]=t;
      }
}

単純選択ソート

配列全部の[0]から[n-1]までの中から最小要素を探し，[0]と交換する．次に，[1]から[n-1]までの中から最小要素(全体では2番目に小さい値)を探し，[1]と交換する．以下同様に[n-1]まで繰り返す．

void selection_sort(int a[], int n)
{
  int i,j,t, position, min;
  for(i=0;i<n-1;i++)
  {
     position=i;
     min=a[i];
     for(j=i+1;j<n;j++)
     {
        if(a[j]<min)
        {
          min=a[j];
          position=j;
        }
     }
     t=a[i];
     a[i]=a[position];
     a[position]=t;
   }
}

単純挿入ソート

これは，人間の並べ替え方法に一番近い発想である．配列の一番目[0]はそのまま，二番目[1]を見て，[0]と比較して逆なら入れ替え，三番め[2]を見て，[0][1]と比較して適切な位置へ挿入，挿入した後ろ位置の要素は一つ後ろへ順送り，四番目[3]は，[0][1][2][3]と順次比較して適切な位置に挿入し後ろは一つ後ろに順送り，という操作を最後まで繰り返すものである．

void shuttle_sort(int a[], int n)
{
  int i,j,t;
  for(i=1;i<n;i++)
  {
    for(j=i; j>=1&&a[j-1]>a[j]; j--)
    {
      t=a[j];
      a[j]=a[j-1];:;
      a[j-1]=t;
    }
  }
}

高速なソート

クイックソート

クイックソートは，C言語のライブラリにもある代表的なソート手法である．その考え方は，配列を分割して個別にソートする手法である．

適当な位置の要素を枢軸(pivot)と設定する．枢軸の値よりも小さい値をすべて配列中の枢軸よりも前におき，枢軸の値よりも大きい要素をすべて枢軸の位置より後ろに配することができれば，このとき枢軸は最終的な整列位置に存在することがいえる．後は，前側の部分配列を個別にソートし，後ろ側の部分配列も個別にソートできる．この部分ソートもクイックソートによって再帰的にソートすることが可能である．

配列を分割するための部分を詳しく解説すると，配列末尾を枢軸とする．(先頭でもよい．)配列残りの部分の先頭要素に対するインデックス(ポインタ)をi，末尾をjとする．位置iを末尾に向けて移動し，iが指す要素の値が枢軸より大きい地点で停止する．逆に位置jを先頭に向けて移動し，jが指す要素の値が枢軸より小さい地点で停止する．この時のiとjの要素を交換する．そしてまたiを末尾に向け移動しjを先頭に向け移動しそれぞれ交換を行いながら，最終的にiとjがぶつかるまで続行する．最後ににiの位置の要素と枢軸を交換する．これで枢軸を中心とした配列の分割が完了する．

int partition(int a[], int l, int r)
{
  int i,,j,pivot,t;
  i=l-1;
  j=r;
  pivot=a[r];
  for(;;)
  {
    while(a[++i]<pivot);
    while(i< --j&&pivoid<a[j]);
    if(i>=j) break;
    t=a[i];
    a[i]=a[j];
    a[j]=t;
  }
  t = a[i];
  a[i] = a[r];
  a[i] = t;
  return i;
}

void quick_sort(int a[], int l, int r)
{
  int v;
  if(l >= r) return;
  v=partition(a,l,r);
  quick_sort(a,l,v-1);
  quick_sort(a,v+1,r);
}