8.Sort

Contents

ソートとは

ソートとは,複数のデータを特定の順序に従うよう並べ替える作業のことです。順番の決め方には次の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){
        //ソート1パス
        onePassOfBubbleSort();
        //結果をプロット
        println("Count " + i);
        clear(); 
        for (int k=0; k < nums.size(); k++) {
          ellipse(k,nums.get(k),DIAMITER,DIAMITER);
        }
        ++i;
      }
    }
    

    2016-09-04 (2)