gihyo.jpサイトのロゴ

Processingで学ぶ 実践的プログラミング専門課程

第10回ソート

2015-02-12

導入

「データ構造とアルゴリズム」という大きなテーマの中から、次の4つのトピックをとりあげています。

  • 配列とコレクション
  • ソート
  • サーチ
  • 再帰

今回はその第2回目として「ソート」を学習します。前回の「配列とコレクション」で数多くのデータをコンピュータに保持する手段を確認しました。データを収集したら、その中から必要なデータを取り出します。その際、データが特定の順序に並んでいると便利です。この並べ替えを「ソート」と呼びます。これを間違いなく素早く行うことは、大切な仕事です。

実際のプログラミングでは、その道のプロフェッショナルが用意してくれたメソッドを活用するとしても、プログラミングを専門技術とする人であれば、中で何が行われているのか、どんな方法があるのかを知っておかなければなりません。少々手強い内容になりますが、投げ出さずに取り組んでください。

展開

ソートとは

ソートとは、複数のデータを特定の順序に従うよう並べ替える作業のことです。順番の決め方には次の2つがあります。

  • 昇順：小さいものから大きなものへ
  • 降順：大きなものから小さなものへ

この連載記事において、特に指定無く「ソートする」と言った場合は昇順のソートを意味するものとします。数値データなら小さな値から大きな値へ、文字データなら辞書順を意味します。

代表的なソートアルゴリズム

ソートを行うアルゴリズムの例として次のものが挙げられます。

  • 基本形
    • 基本交換法：バブルソート
    • 基本選択法：直接選択法
    • 基本挿入法
  • 応用形
    • 改良交換法：クイックソート
    • 改良選択法：ヒープソート
    • 改良挿入法：シェルソート

ここに紹介する分類は『改訂C言語によるはじめてのアルゴリズム入門』（⁠河西朝雄 著、技術評論社 P.119）に掲載されているものです。

基本選択法

アルゴリズムが単純で理解しやすいことから、最初の学習にはこの基本選択法が適しています。

基本選択法のアルゴリズムは次のとおりです。

基本選択法のアルゴリズム
  • 要素数nの配列aにランダムな整数データが代入されているものとする。
  • 添字のために整数変数iを用意する。初期値を0とする。
  • 次の手順をiの値がn-2の時まで繰り返す。
    1. a[i]を最小値であるとする。整数変数sにiの値を代入する。
    2. a[i+1]からa[n-1]まで巡回してa[s]と比較する。a[s]より小さい要素があれば、その添字の値を整数変数sに代入する（巡回用のカウンタ変数はjとする⁠）⁠。
    3. a[i]とa[s]の値を交換する。
    4. iの値を1つ増やす。

実際に手を動かし、このアルゴリズムを確認してください。

［作業］要素数5のデータに対して基本選択法のアルゴリズムを手作業で適用しましょう。アルゴリズム適用の流れをトレース表に書きましょう。ソートするデータはa = { 35, 20, 80, 5, 56 }とします。

基本選択法のトレース
画像

基本選択法のsketch

基本選択法ののアルゴリズムをProcessingで組んだものが次のsketchです。ソートの様子を画面に描くために、drawメソッド1回ごとにソート操作1回実行しています。

基本選択法のsketch。SelectionSort.pde
final int    NUMBER_OF_RANDOM_DATA = 500;
final String DATA_FILE_NAME        = "RandomData.txt";
final int    DIAMITER              = 5;

ArrayList<Integer> nums = new ArrayList<Integer>();
int i = 0; // ソート回数。drawする度にカウントアップ

void setup(){
  //ランダムなデータの読み込み
  loadData();
  //ディスプレイウインドウの設定
  size(NUMBER_OF_RANDOM_DATA,NUMBER_OF_RANDOM_DATA);
  background(0,0,0);
  frameRate(30);
  stroke(255,0,0);
}

void loadData(){
  String lines[] = loadStrings(DATA_FILE_NAME);
  for(String val : lines){
    nums.add(int(val));
  }
}

void onePassOfSelectionSort(){
  int s = i;
  for(int j = i + 1; j < NUMBER_OF_RANDOM_DATA; ++j){
    if(nums.get(j) < nums.get(s)){
      s = j;
    }
  }
  int t = nums.get(i); 
  nums.set(i,nums.get(s)); 
  nums.set(s, t);
}

void draw(){
  if (i < NUMBER_OF_RANDOM_DATA - 1){
    //ソート１パス
    onePassOfSelectionSort();
    //結果をプロット
    println("Count " + i);
    clear(); 
    for (int k=0; k < nums.size(); k++) {
      ellipse(k,nums.get(k),DIAMITER,DIAMITER);
    }
    ++i;
  }
}

5つのデータをソートする場合、画面に描かなければ一瞬で終了します。setupメソッド内のframeRate(30)をframeRate(60)などとすると、より早く動く様子を確認できます。

基本選択法の計算量

基本選択法のアルゴリズムでは、データがn個ある場合、最初のループでn-1回の比較が行われ、発見した最小値を除くn-1個のデータが残ります。次のループではn-2回の比較が行われ、発見した最小値を除くn-2個のデータが残ります。こうして、すべてのデータをチェックして並べ替えるまでの手順は次のようになります。

1回目のループ n-1回比較
2回目のループ n-2回比較
3回目のループ n-3回比較

こうして検索回数は、次のようになります。T(n)はこのアルゴリズムの、データの個数nに応じた計算回数を表す関数です。

T(n) = (n-1) + (n-2) + (n-3) + ... + 2 + 1
     = n (n-1) / 2
     = (n2 - n) / 2

この式のオーダー、すなわちこの式の値の最も大きな部分をあらわす項はn2です。この項がnの変化に応じて急激に増加する形か、それともあまり増加しない形かを知ることは、プログラムの実行速度を推定するために大変役立ちます。この項のことを、そのアルゴリズムの計算量と呼びます。計算量は「その計算がどれだけ大変なことか」を表す量です。今回のような場合、計算量は次のように書けます。

O(n2)

これは計算量としては大きい部類です。実際にコンピュータを動かした場合に大変時間がかかるということです。

改良挿入法：シェルソート

次に、とても効率の良いソートの例としてシェルソートを学習しましょう。シェルソートの計算量はおおよそO(n1.5)となります。どのようなばらつきのデータに対しても効率良く動作すると言われています。

シェルソートのアルゴリズム
  • 要素数nの配列aにランダムな整数データが代入されているものとする。
  • 整数変数gapを用意する。初期値はn/2とする。
  • 次の手順をgapの値が1になるまで繰り返す。
    1. 次の操作をgap回繰り返す。すなわち整数変数jは初期値0、終了値gap-1でインクリメントする。
      1. a[j], a[j+gap], a[j+2gap], ……を基本挿入法でソートする。
      2. ++j
    2. gapを半分にする。

シンプルなことがよくわかります。このアルゴリズムを実装については演習の課題とします。

演習

演習1（難易度：easy）

ランダムな整数データを500個もつデータファイルを作成しましょう。データは最小値1、最大値1000とします。データはテキストファイルRandomData.txtに保存しましょう。このsketchのファイル名はGenerateRandomData.pdeにしてください。

演習2（難易度：middle）

SelectionSort.pdeのコードを参考に、シェルソートを実装してください。あまりに速くソートされるので、frameRateを10に変更しましょう。ファイル名はShellSort.pdeとしてください。

演習3（難易度：middle）

基本交換法であるバブルソートのアルゴリズムを調べて、演習1で作成したRandomData.txtをソートするsketchを作成しましょう。ファイル名はBubbleSort.pdeとしてください。

まとめ

  • 専門家として知っておくべきアルゴリズムの例として、ソートのアルゴリズムを学習しました。

学習の確認

それぞれの項目で、Aを選択できなければ、本文や演習にもう一度取り組みましょう。

  1. 基本選択法の仕組みが理解できましたか？
    1. 理解できた。気持ちよく納得した。
    2. 理解できた。しかし、今ひとつスッキリしない。
    3. 理解できない。
  2. シェルソートの仕組みが理解できましたか？
    1. 理解できた。気持ちよく納得した。
    2. 理解できた。しかし、今ひとつスッキリしない。
    3. 理解できない。
  3. バブルソートの仕組みが理解出来ましたか？
    1. 理解できた。気持ちよく納得した。
    2. 理解できた。しかし、今ひとつスッキリしない。
    3. 理解できない。

参考文献

  • 『改訂C言語によるはじめてのアルゴリズム入門』（⁠河西朝雄 著、技術評論社⁠）⁠
    • アルゴリズムの入門書。入門者に取っては十分に辞書的な内容である。丁寧に解説された良書。

演習解答

  1. GenerateRandomData.pde
    • このコードで作成したデータファイルRandomData.txtはスケッチフォルダGenerateRandomData内にあります。他のsketchで利用する場合は、そのsketchのスケッチフォルダにコピーしてください。
  2. ShellSort.pde
  3. BubbleSort.pde
    • 演習2と演習3のソートを実行した時、描画された画面の美しさにはほれぼれすることでしょう。

おすすめ記事

記事・ニュース一覧