8.Sort

ソートとは

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

並べ替えは、主にデータベースなどの大量のデータを処理する必要のあるプログラムで有用です。試験の点数の高い順番に並べ替えて、上位1000人を合格にするなどの場合は、点数による並べ替えが行われます。また、住所録のデータを住所毎にまとめて参照したい場合は、住所（文字列）による並べ替えが行われます。

ソートアルゴリズム

ソートの処理は、さまざまなプログラムの中で頻繁に使われ、そのゆえ、古くからいろいろなアルゴリズムが考案されてきました。

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

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

バブルソート

バブルソート (bubble sort) は、ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間がと遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことから、しばしば用いられる。安定な内部ソート。基本交換法、隣接交換法ともいう。（単に交換法と言う場合もある）

バブルソートサンプル

final int    NUMBER_OF_RANDOM_DATA = 500;
final String DATA_FILE_NAME        = "RandomData.txt";
final int    DIAMITER              = 5;

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

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

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

void onePassOfBubbleSort(){
  for ( int j = NUMBER_OF_RANDOM_DATA - 1; j > i; j--){
    if ( nums.get(j) < nums.get(j-1) ){
      int temp = nums.get(j);
      nums.set(j,nums.get(j-1));
      nums.set(j-1,temp);
    }
  }
}

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