第 12 回 ソート

本日の内容

このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。

12-1. ソート

順番にデータを並び替えることをソートと言います。 今回はソートのアルゴリズムを紹介します。 始めに前回示した順序木によるソートの分析をし、そのあと、配列変数に対す るソートのアルゴリズムを示します。

計算量

プログラムの効率を評価する時、入力の長さを n とした時にプログラムが 実行するステップ数を関数の形で計算します。 そして、関数が複数の項の足し算になっている時、もっとも増え方が速い項を 取り出し、係数を除いたものを考えます。 例えば、次のプログラムの効率を評価します。 


#include <stdio.h>
main(){
  int i,j,s;
  scanf("%d",&i);
  s=0;
  for(j=1;j<=i;j++){
    s+=j;
  }
  printf("%d\n",s);
}
  1. main, int などの手間はとりあえず 1 ずつとします。
  2. scanf では、入力される長さ程度の手間が必要なので n とします。 ここで、 i と n の関係は i = 2n または log i = n となること に注意して下さい(i は高々 n 桁で表現できる数)。
  3. s=0 の手間は 1 とします。
  4. for のカッコの中の手間は j=1 が 1 、 j<i は i の桁数程度の手間 になるので n 、 j++ も最大値は i 位なので n とします。 但し、繰り返し回数は i 回 = 2n回です。
  5. s+=j の手間ですが、 s の最大値は大体 i2 なので、その桁 数は log i2 = 2 log i = 2 n とします。これを 2n 回繰り返します。
  6. printf の手間は s の桁数程度なので、 2 n とします。

すると全部の手間は 1+1+n+1+(1+2n(n+2n+n))+2n = 2n・4n + 3n + 3 となります。 この中でもっとも増え方の速い項は 2n・4n です。そして、係数を取り除くと 2n・n と なります。 この時、このプログラムの実行時間はオーダー2n・n だと言います。 式で書くと O(2n・n)となります。 プログラムの計算時間の評価はこのように関数の形で行います。 どうしてこのような雑な関数の取り扱いになるかは 1部データ構造とアルゴリズム第6回アルゴ リズムに関する数学 3. 計算量を参照して下さい(Internet Explorer ver.6 では見られません)。

順序木の計算量

前回示した順序木の処理の計算量を求めます。 深さ k の木にはおおよそ 2k個のデータを詰め込めます。従って、 データ数が n 個の順序木の深さはおおよそ log n になります。

add 関数は新しく頂点を付け加える作業をします。 そのためには木の端まで木をたどり、そこに頂点を新しくつくって接続します。 木の端までたどるには木の深さ程度の手間 O(log n) 程度かかります。 新しく頂点を作る作業はO(1)程度かかるとします。 従って、add 関数一回の手間は O(log n)です。 これをデータ数 n だけ繰り返す必要があるので 与えられたデータから順序木を作るには O( n log n ) の手間がかかります。

一方 show 関数は全データを表示するだけですから O(n) の手間がかかります。

従って順序木を使用した並べ替えにかかる手間は O(n log n + n ) = O(n log n) となります。

効率の悪い並び替え

これから示すのは良く知られている効率のわるい並び替えアルゴリズムです。 これらをレポートに使用してはいけません。 なおこれからは配列変数に対してソートを行うことを考えます。

バブルソート

挿入法

クイックソート

配列に対して、順序木を使ったソートに匹敵する効率でソートするにはどうす ればいいでしょうか? そのためには、順序木にデータを入れるようにデータを動かす必要があります。 順序木の性質により根の頂点に入るデータに対して、左に接続する木に含まれ るデータは全て値が小さく、右に接続する木に含まれるデータは全て値が大き くなります。 そこで、配列に対して、根に入る値、左側に入る値、右側に入る値を分類する ことを考えます。 この作業を行う関数を partition と呼ぶことにします。 すると、左側に入る値に対しても partition 、右側に入る値に対しても partition を行うことにより最終的に全てのデータを順序木のどこに配置すれ ば良いかを決めることができます。

配列の中身をソートするには、左側に入る値を前に、右側に入る値を後ろに移 動させる必要があります。 そして、左側に入る値を前半部分、右側に入る値を後半部分に移動させられれ ば、こんどはその部分に対して partition を実行させます。 従って、 partition の引数にはどこからどこまでを対象にするかを与える必 要がありますので、関数宣言は次のようになります。 


void partition(int s, int t);

そして、内部では次のようにします。

  1. 配列の名前を a とします。
  2. s=t ならば何もせずに終了します。
  3. a[s] を勝手に根に入る値と定めてしまいます。
  4. 変数 i=s, j=t とします。
  5. a[s]<a[i]となる a[i] を i を増やしながら探します。(範囲外に出な いように注意)
  6. a[s]> a[j]となるa[j] を j を減らしながら探します。(範囲外に出な いように注意)
  7. a[i] と a[j] を交換します。
  8. i と j が一致したら終了します。
  9. partition(s,i) と partition(j,t) を実行します。

このようにすると O( n log n ) でデータをソートできます。 このようなソートをクイックソートと言います。

演習12-1

  1. クイックソートのプログラムを作りなさい。
  2. int a[10]={4,6,3,1,9,7,5,0,2,6,8} に対して作ったプログラムを使い、 値をソートし出力させなさい。

演習12-2

大きい順にソートするプログラムを書き、上記のデータをソートし出力させな さい。

坂本直志 <sakamoto@c.dendai.ac.jp>
東京電機大学工学部情報通信工学科