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){
        //ソート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)

    7.Recursive

    再帰とは

    再帰(Recursion)とは,再帰的な構造を持つアルゴリズムのことです。再帰的な構造とは,自分自身の定義の中に,自分自身を含む構造です。再帰の代表的な例として階乗やユークリッドの互除法の再帰的定義がよく用いられます。それぞれについて学習していきます。

    階乗

    整数nの階乗は記号!を用いてn!と書きます。実際の計算は次のように行われます。

    n! = n × (n-1) × (n-2) × ... × 2 × 1 

    この式を再帰的定義に書き換えると,次のようになります。

    n! = n × (n-1)!  (ただし,0!=1)

    次の階乗のsketch、Factorial.pdeは10の階乗を行う例

    1. 繰り返し構文を使ったメソッド factorial_for
    2. 再帰するメソッド factorial_recursive
    // 繰り返し構文を用いたメソッド
    long factorial_for(long i){
      if(i < 0){
        println("Error! Invarid input.<using for>");
        return -1;
      } else {
        long result = 1;
        for (int j = 1; j <= i; ++j){
          result *= j;
        }
        return result;
      }
    }
    // 再帰を用いたメソッド
    long factorial_recursive(long i){
      if(i < 0){
        println("Error! Invarid input.<using recursive>");
        return -1;
      } else if(i == 0){
        return 1;
      } else {
        return i * factorial_recursive(i - 1);
      }
    }
    
    void setup(){
      long num    = 0;
      // using for
      println("using for       : factorial(" + num + ") = "
               + factorial_for(num) );
      // using recursive
      println("using recursive : factorial(" + num + ") = "
               + factorial_recursive(num) );
      num    = 10;
      // using for
      println("using for       : factorial(" + num + ") = "
               + factorial_for(num) );
      // using recursive
      println("using recursive : factorial(" + num + ") = "
               + factorial_recursive(num) );
      num    = -10;
      // using for
      println("using for       : factorial(" + num + ") = "
               + factorial_for(num) );
      // using recursive
      println("using recursive : factorial(" + num + ") = "
               + factorial_recursive(num) );
    
    }

    ユークリッドの互除法

    8王妃問題を解く

    再帰を活用するメリットとデメリット

    再帰を活用するメリットは,「(場合によっては)問題をシンプルに記述できること」です。しかし,再帰は電子計算機で実行するアルゴリズムとしてはやっかいな問題,デメリットを抱えています。

    そのデメリットを話す前に,計算量の2つの種類について言及しておきます。計算量は「時間計算量」と「空間計算量」という2つに区別できます。時間計算量は,これまで何度か取り扱って来た計算量の考え方で,そのアルゴリズムの実行にどれだけ手数がかかるかを表す量です。これに対して空間計算量は,そのアルゴリズムの実行にどれだけの記憶容量が必要かを表す量です。

    再帰のアルゴリズムは,自分自身を1回呼ぶ度に,自分自身を実行するために必要なメモリを用意します。再帰の回数が多くなれば,必要なメモリ容量も多くなります。つまり,再帰のアルゴリズムのデメリットとは空間計算量が大きくなることです。再帰のアルゴリズムは潤沢にメモリがあることを前提とした手段なのです。

    かつて,コンピュータがごくわずかなメモリしか持っていなかった時代のプログラミング言語が,再帰を言語の仕組みとして用意しなかった理由の一つは,再帰が簡単にメモリを食いつぶす方法だったからでしょう。現在,パーソナルコンピュータのメモリは数ギガバイトを持つようになったため,この問題が大きく扱われることはあまりありません。ただ,再帰を使ったプログラムによってはメモリを圧迫しますので,利用にあたっては慎重になりましょう。

    そのため,再帰アルゴリズムを使用するべき場合とは,コードを劇的にシンプルにできる場合に限ると考えておくべきです。

    6.Stack and Queue

    キューとスタックは、古典的なデータ構造として広く知られているものですが、 実装上はリストの一種と考えることができます。

    キュー

    キュー (Queue) は「先入れ先出し (First-In First-Out, FIFO)」を表すデータ構造です。 データを取り出す際、先に格納したものから順に取り出します。

    • 銀行や病院やたい焼き屋の待ち行列 (先に並んだ人からサービスを受ける)
    • コンピューターでプリンタへの出力処理や、ウィンドウシステムのメッセージハンドラ、プロセスの管理など、データを入力された順番通りに処理する必要がある処理に用いられる。

    データを追加する操作をエンキュー(enqueue)。
    データを取り出す操作をデキュー(dequeue)という。

    スタック

    スタック(Stack)は、 「あと入れ先出し (Last-In First-Out, LIFO)」あるいは「先入れあと出し(First-In Last-Out, FILO)」を表すデータ構造です。 データを取り出す際、最も後に格納したものから順に取り出します。

    • 積ん読 (本を重ねて積んでいくと上からしか取れない)
    • コンピューターで割込みやサブルーチンを支援するために極めて有用である

     

     

    スタックにデータを入れる操作をプッシュ(push)という。
    スタックからデータを取り出す操作をポップ(pop)という。

    キューとスタックの実装

    オブジェクトの後入れ先出し(LIFO)スタックを表すStackクラスは、JDK 1.0から導入されていました。これに対して、オブジェクトの先入れ先出し(FIFO)を表す待ち行列(キュー)は、特に用意されていませんでしたが、JDK 5.0からQueueインターフェイスが新たに導入されました。

    一例として、LinkedListオブジェクトによるキューと、Stackクラスによるスタックを試すプログラムを作成しました。

    import java.util.*;
    
    String[] item = {"Apple", "Banana", "Cocoa"};
    Queue q = new LinkedList();
    Stack s = new Stack();
    for(String i: item) {
      q.offer(i); // enqueue
      s.push(i);  // push
    }
    while(q.size() > 0) {
      println("QUEUE:" + q.poll());
    }
    while(s.size() > 0) {
      println("STACK:" + s.pop());
    }
    

     

    2016-09-04 (5)

    キューがスタックに近い形で利用可能になっているのが、実感できます。

    参考:

    • http://www.atmarkit.co.jp/fjava/javatips/182java064.html ーーGenericsを用いたスタックとキューのサンプルプログラム

    5.Search

    サーチ(Search)とは,複数のデータの中から特定のデータを見つけ出す作業のことです。日本語では探索や検索と呼びます。

    サーチのアルゴリズムには,ランダムなデータを取り扱えるものと,ソート済みのデータを取り扱うものとがあります。

    リストサーチ(list search)

    データのリスト構造とはA, B, C, ……のように,データが次々と連続している構造のことを言います。代表例は配列です。

    そのようなリスト構造を持つデータの集合を探索するためのアルゴリズムを,ここではリストサーチと呼びます。

    探索のアルゴリズム

    • 線形探索
    • 二分探索
    • ハッシュ法

    線形探索

    線形探索という言葉は英語のLinear Searchの直訳です。線形探索はリストの先頭から終端に向かって目的の要素を探し出すアルゴリズムです。

    目的の要素であるという判定は比較によって行います。

    アルゴリズム分析

    1. リストの先頭から要素を取り出す
    2. 取り出した要素の値と探したい要素の値を比較する
      • 一致すれば探索完了
      • 一致しなければ 1. へ戻り次の要素を取り出す

    かなりシンプルで理解し易いアルゴリズムです。

    サンプルコード

    線形探索のアルゴリズムを実装したsketchは次のとおりです。

    線形探索のsketch。LinearSearch.pde

    // 線形探索   Linear Search
    // 番兵無し   No Sentinel
    
    final int    NUMBER_OF_RANDOM_DATA = 500;
    final String DATA_FILE_NAME        = "RandomData.txt";
    final int    DIAMITER              = 5;
    final int    SEARCHING_VALUE       = 37;
    
    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(60);
      stroke(255,0,0);
    }
    
    void loadData(){
      String lines[] = loadStrings(DATA_FILE_NAME);
      for(String val : lines){
        nums.add(int(val));
      }
    }
    
    
    void linearSearch(){
      if (SEARCHING_VALUE == nums.get(i)) {
        println("Hit!");
        ellipse(i,nums.get(i),DIAMITER*2,DIAMITER*2);
        exit();
      } 
    }
    
    void draw(){
      println("Searching value is " + SEARCHING_VALUE);
      if (i < NUMBER_OF_RANDOM_DATA){
        //サーチ1パス
        linearSearch();
        //結果をプロット
        println("Count " + i);
        clear(); 
        for (int k=0; k < nums.size(); k++) {
          if ( k == i ) {
            ellipse(k,nums.get(k),DIAMITER*2,DIAMITER*2);
          } else {
            ellipse(k,nums.get(k),DIAMITER,DIAMITER);
          }
        }
        ++i;
      }
    }

     

    参考:

    • http://www.codereading.com/algo_and_ds/algo/linear_search.html

    TinyWebDB API Tester HD

    AppInventorはAndoridのApp作りに簡単な環境です。WordPressをWebコンテンツを作るに最適な環境。

    WP-TinyWebDB-APIは、両者の長所を連携し、WordPressをAppInventorのTinyWebDBサービスとして利用するためのAPIを、WordPressのプラグインとして提供したもの。

    TinyWebDB API Tester (HD版) は設置しているAPIをテストするためのものである。

    https://play.google.com/store/apps/details?id=appinventor.ai_chen_waseda.TinyWebDB_API_HD

    TINIWEBDB-API5.2-512x512

    Education on Web