2014-01-22

明解 Javaによるアルゴリズムとデータ構造　6-7_マージソート

6-7　マージソート

配列を前半部と後半部に分けて、それぞれをソートしたものをマージ(併合)するのを繰り返す方法

ソート済み配列のマージ

各配列の着目要素の値に注目して、小さい方の値を取り出し、別の配列に格納する

ソースコード

import java.util.Scanner;


class MergeArray {
    static void merge(int[] a, int na, int[] b, int nb, int[] c) {
        int pa = 0;
        int pb = 0;
        int pc = 0;
        
        while (pa < na && pb < nb) {
            c[pc++] = (a[pa] <= b[pb]) ? a[pa++] : b[pb++];
        }
        
        while (pa < na) {
            c[pc++] = a[pa++];
        }
        while (pb < nb) {
            c[pc++] = b[pb++];
        }
    }
    
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        int[] a = {1, 3, 5, 7, 9, 10};
        int[] b = {0, 1, 2, 3, 8, 15, 19};
        int[] c = new int[13];
        
        System.out.println("2つの配列のマージ");
    
        merge(a, a.length, b, b.length, c);
        
        System.out.println("配列aとbをマージしてcに格納しました");
        System.out.println("配列a: ");
        for (int i =0; i < a.length; i++) {
            System.out.println("a[" + a[i] + "]: " + a[i]);
        }
        System.out.println("配列b: ");
        for (int i =0; i < b.length; i++) {
            System.out.println("b[" + b[i] + "]: " + b[i]);
        }
        System.out.println("配列c: ");
        for (int i =0; i < c.length; i++) {
            System.out.println("c[" + c[i] + "]: " + c[i]);
        }
    }
}

出力結果

2つの配列のマージ
配列aとbをマージしてcに格納しました
配列a: 
a[1]: 1
a[3]: 3
a[5]: 5
a[7]: 7
a[9]: 9
a[10]: 10
配列b: 
b[0]: 0
b[1]: 1
b[2]: 2
b[3]: 3
b[8]: 8
b[15]: 15
b[19]: 19
配列c: 
c[0]: 0
c[1]: 1
c[1]: 1
c[2]: 2
c[3]: 3
c[3]: 3
c[5]: 5
c[7]: 7
c[8]: 8
c[9]: 9
c[10]: 10
c[15]: 15
c[19]: 19

マージソート

ソート済み配列のマージを応用して、分割統治法によってソートを行う
配列の要素数が2以上であれば、以下の手続きを適用する
- 配列の前半部をマージソートによってソートする
- 配列の後半部をマージソートによってソートする
- 配列の前半部と後半部をマージする
安定である
時間計算量: [http://okwave.jp/qa/q4403802.html:title]
[tex: O(nlogn)]
- 総比較回数:
  [tex:\displaystyle \sum_{k=1}^{x}(n-2^{k-1})= \displaystyle \sum_{k=0}^{x-1}(n-2^{k}) = nx - n + 1 = nlog n - n + 1]
  - 要素数: n = 2^x
  - 分割数: k
- 簡単に言うならば、(2配列のマージのコスト)×(分割回数)で概算できる

ソースコード

import java.util.Scanner;

class MergeSort {
    static int[] buff;

    static void __mergeSort(int[] a, int left, int right) {
        if (left < right) {
            int i;
            int center = (left + right) / 2;
            int p = 0;
            int j = 0;
            int k = left;

            __mergeSort(a, left, center);
            __mergeSort(a, center + 1, right);

            for (i = left; i <= center; i++) {
                buff[p++] = a[i];
            }

            while (i <= right && j < p) {
                a[k++] = (buff[j] <= a[i]) ? buff[j++] : a[i++];
            }
            while (j < p) {
                a[k++] = buff[j++];
            }
        }
    }

    static void mergeSort(int[] a, int n) {
        buff = new int[n];
        __mergeSort(a, 0, n - 1);
        buff = null;
    }

    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        System.out.println("マージソート");
        System.out.print("要素数: ");
        int nx = stdIn.nextInt();
        int[] x = new int[nx];

        for (int i = 0; i < nx; i++) {
            System.out.print("x[" + i + "]: ");
            x[i] = stdIn.nextInt();
        }
        mergeSort(x, nx);
        System.out.println("昇順にソートしました");
        for (int i = 0; i < nx; i++) {
            System.out.println("x[" + i + "]" + x[i]);
        }
    }
}

Arrays.sort によるクイックソートとマージソート

基本型配列のソート(クイックソート)

基本型配列のソートについて、クイックソートベースのため、安定でない

ソースコード

import java.util.Arrays;
import java.util.Scanner;

class ArraysSortTester {
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        System.out.println("要素数: ");
        int num = stdIn.nextInt();
        int[] x = new int[num];
        
        for(int i= 0; i < num; i++){
            System.out.print("x[" + i + "]: ");
            x[i] = stdIn.nextInt();
        }
        
        Arrays.sort(x);
        
        System.out.println("昇順にソートしました");
        for(int i= 0; i < num; i++){
            System.out.println("x[" + i + "]: " + x[i]);
        }
    }
}

クラスオブジェクトの配列のソート(マージソート)

自然な順序に基づくソート
自然な順序ではなく、コンパレータ定義に基づくソート
ともにマージソート -> 安定

ソースコード

自然順序

import static java.util.Calendar.*;

import java.util.Arrays;
import java.util.GregorianCalendar;

class SortCalendar {
    public static void main(String[] args) {
        GregorianCalendar[] x = {
                new GregorianCalendar(2005, NOVEMBER, 1),
                new GregorianCalendar(1963, OCTOBER, 18),
                new GregorianCalendar(1985, APRIL, 5),
        };

        Arrays.sort(x);

        for (int i = 0; i < x.length; i++) {
            System.out.printf("%04d年%02d月%02d日\n", x[i].get(YEAR),
                    x[i].get(MONTH) + 1, x[i].get(DATE));
        }
    }
}

コンパレータ

import java.util.Arrays;
import java.util.Comparator;

class PhyscExamSort {

    static class PhyscData {
        String name;
        int height;
        double vision;

        PhyscData(String name, int height, double vision) {
            this.name = name;
            this.height = height;
            this.vision = vision;
        }

        public String toString() {
            return name + " " + height + " " + vision;
        }

        static final Comparator<PhyscData> HEIGHT_OPDER = new HeightOrderComparator();

        private static class HeightOrderComparator implements
                Comparator<PhyscData> {
            public int compare(PhyscData d1, PhyscData d2) {
                return (d1.height > d2.height) ? 1
                        : (d1.height < d2.height) ? -1 : 0;
            }
        }
    }

    public static void main(String[] args) {
        PhyscData[] x = { new PhyscData("赤坂", 162, 0.3),
                new PhyscData("赤坂", 162, 0.3),
                new PhyscData("加藤", 173, 0.7),
                new PhyscData("斉藤", 175, 2.0),
                new PhyscData("武田", 171, 1.5),
                new PhyscData("長浜", 168, 0.4),
                new PhyscData("はまだ", 174, 1.2),
                new PhyscData("松富", 169, 0.8),
        };

        Arrays.sort(x, PhyscData.HEIGHT_OPDER);

        System.out.println("■　身体検査一覧表　■");
        System.out.println("氏名　　身長　視力");
        System.out.println("--------------------");
        for (int i = 0; i < x.length; i++) {
            System.out.printf("%-8s%3d%5.1f\n", x[i].name, x[i].height,
                    x[i].vision);
        }
    }
}

コンパレータ2

       static final Comparator<PhyscData> VISION_ORDER = new VisionOrderComparator();

        private static class VisionOrderComparator implements
                Comparator<PhyscData> {
            public int compare(PhyscData d1, PhyscData d2) {
                return (d1.vision > d2.vision) ? -1
                        : (d1.vision < d2.vision) ? 1 : 0;
            }
        }

明解 Javaによるアルゴリズムとデータ構造

作者: 柴田望洋
出版社/メーカー: ソフトバンククリエイティブ
発売日: 2007/11/07
メディア: 単行本
購入: 5人クリック: 42回
この商品を含むブログ (19件) を見る

2014-01-21

JUnit 実践入門　体系的に学ぶユニットテストの技法 - 第3章テスティングフレームワークテストを支えるしくみ

コンピュータ Java 本

第3章テスティングフレームワークテストを支えるしくみ

テストでは、入力値の準備や、期待される結果の検証が重要

3.1 テスティングフレームワークとは

一定のフォーマットで書けるため、可読性に貢献
テストコードの記述に集中できる

xUnit フレームワーク

JUnit は xUnit フレームワーク
- SUnit(Smalltalk) -> xUnit -> JUnit

3.2 JUnit によるユニットテストの記法

public メソッド
oorg.junit.Test アノテーション
戻り値 void
引数なし

テストソッドの throw 句

記述は自由
通常は、expected 句に Exception クラスを記述する
Java では一般に、メソッドの throw 句に、Throwable や Exception などの基底クラスを指定できない
- JUnit では例外処理はフレームワークで行われるため、throw 句に各 Exception を詳細に書き込んだかどうかは、テストに影響を及ぼさない

テストメソッドを簡単に挿入する

Eclipse のテンプレート機能を利用

3.3 可読性の高いテストコードの書き方

テストコードは、プロダクションコード同様の整理をすべきではない
- 独立したテストケースに対して、可読性が高いことを優先する

テストケース

前提条件
入力値・操作
期待する値・動作
- アンチパターン『正しく表示されること』

テスト対象

SUT System Under Test: テスト対象となるクラスやオブジェクト
1 テストケースにつき、1 SUTを対象とする
テスト対象のインスタンス名を sut とかにするとわかりやすい

実測値と期待値

実測値 actual value: メソッドが返す値や、オブジェクトの変化する状態など
期待値 expected: 仕様として返すべき値や状態
- 仕様変更がない限り不変
テストコードの変数名は actual, expected などがおすすめ

メソッドと副作用

以下の様な精子のメソッドはテストが容易で、「関数的」という

メソッドが戻り値を持つ
メソッドの呼び出しの結果、副作用がない
同じ状態、同じパラメータで実行すれば、必ず同じ結果を返す

一方で ArrayList.add などは副作用があるものの代表。

size() や get() で状態を確認するしかない

テスト対象が乱数や時刻等で実測値が変化する場合、モックオブジェクトで状態を固定し、テストを実施する

4フェーズテスト

以下の4フェーズを意識して書かれたテストは可読性が高い。特に事前準備とテスト実行。
- 事前準備 set up
- 実行 exercize
- 検証 verify
- 後処理 tear down

テストフィクスチャ test fixture

テスト実行時に必要なすべてのデータや状態
- DB 初期化や複雑なデータは注意が必要で、準備部分が長くなって、テスト自体のコードが不鮮明になる
テストフィクスチャり準備のためのコードは簡潔に
- 外出し(外部クラス、外部ファイルなど)

3.4 比較検証を行うアサーション

実測・期待の比較のこと
JUnit では主に、org.junit.Assert クラスの assertThat メソッドと、Matcher API を利用してアサーションを記述する

JUnit のアサーション

assertThat -> arg[1]:actual arg[2]: expected を含む Matcher オブジェクト
is メソッドで生成される Matcher オブジェクトはオブジェクトの同値性(equalsメソッドと同等)を検証する

3.5 JUnit が提供するアノテーション

アノテーション: Java 5 からの言語仕様。クラス、メソッド、変数などに補助的な情報を宣言するための機能。
JUnit では、@Test により、フレームワークが実行するテストメソッドを認識させている

@Test - テストメソッドを宣言する

expected
timeout
- テスト失敗までの待ち時間を指定。一部分の実行がテスト全体を止め内容にするための保険
- 性能テスト用ではない
要求: 戻り値なし、引数なし、publicメソッド

@Ignore - テストの実行から除外する

テストクラスに付与すると、クラス単位で無視

@Before - テスト実行前に処理を行う

テストメソッド間で重複した初期化処理を定義する
メソッド名: setUp
同一クラス内限定
複数のクラスに適用したい場合は、『ルール』を使うこと
- 継承は好ましくない
要求: 返り値なし、引数なし、publicメソッド

@After - テスト実行後の後処理を行う

テストの成功失敗に関わらず必ず実行される
メソッド名: tearDown
要求: 返り値なし、引数なし、publicメソッド

@BeforeClass - テスト実行前に一度だけ処理を行う

テストクラスがクラスローダに読み込まれたあと、そのテストが含まれる最初のテストが実行される前に一度だけ実行される
あまり使わない
- テストメソッドは基本的に独立しているべきで、テストクラス単位ではなく、テスト単位でリソースの作成/開放を行うべきだから
要求: 返り値なし、引数なし、static な publicメソッド

3.6 JUnit のテストパターン

標準的な振る舞いを検証するテスト
- ほとんどがこのパターンの4フェーズテスト
例外の送出を検証するテスト
- 送出される例外の型を Test アノテーションの expected 属性に記載
- JUnit の例外検証では、例外の型以外は検証できない
  - より詳しくやりたければ、org.junit.rules.ExpectedException を利用する
コンストラクタを検証するテスト
- インスタンスの生成(コンストラクタ)のテスト
- 初期値が妥当か検証する
- インスタンスはテスト対象オブジェクト(sut)でもあり、実測値でもある
- 変数名 instance とかにするといいよ

JUnit実践入門 ~体系的に学ぶユニットテストの技法 (WEB+DB PRESS plus)

作者: 渡辺修司
出版社/メーカー: 技術評論社
発売日: 2012/11/21
メディア: 単行本（ソフトカバー）
購入: 14人クリック: 273回
この商品を含むブログ (65件) を見る

2014-01-21

JUnit 実践入門　体系的に学ぶユニットテストの技法 - 第2章ユニットテスト何のためにテストするのか

コンピュータ Java 本

第2章ユニットテスト何のためにテストするのか

2.1 ソフトウェアテストとは

検証する内容を定義し、ソフトウェアが期待通りに動作するのかを確認すること
- テストを作るのは、テスを行うテスター自身であり、ソフトウェアの仕様や要件を基に、テスト項目を抽出する
- 検証項目が明確でなく、人間の感覚に依存するテストもある

ソフトウェアテストの特徴

設計段階で徹底的に検証して品質を高める手法は、効果的でない
- プログラム上の問題や制約などが実際に作ってみなければわからないことが多い
- 一度作ったプログラムを破棄して作りなおすことが比較的容易
作りながら同時にテストを行ったり、実施したテストから得られたフィードバックからテストを追加したりする方法が有効

テストケースとテストスイート

テストケース: 1つのテスト項目のこと
- テストの前提条件、実行する操作、期待される値、状態などを含む
- 『どのような条件でどのような操作をしたら、どういう結果が期待されるか』
テストスイート: いくつかのテストケースをまとめたもの

ソフトウェアテストの目的

品質向上だけじゃない
機能テストは、進捗確認にも使える
- 『設計された全機能のうち、どこまでテストグリーンになるか』
ユニットテストは、設計妥当性の確認にも使える

ソフトウェアテストの限界

全パターンをテストすることは不可能
『完璧にテストは不可能である』
テスト方針合意の重要性が生じる

2.2 テスト技法

ホワイトボックステストとブラックボックステスト

ホワイトボックステスト: 内部ロジックや仕様に基づいてテストケースを設計。すべてのロジックを実行する。したがってプログラマがテストを実施。
ブラックボックステスト: 外部仕様のみからテストケースを設計。業務知識が重要。
本書は、ホワイトボックス寄りな内容

同値クラスに対するテスト

代表値に対するテストで全パターンテストすることを代替する

境界値に対するテスト

不具合が混入する可能性の高い、プログラムの挙動をわける境界値近辺の2値でテストを実施する

2.3 ユニットテスト

クラスやメソッドを対象とする、最も小さい粒度のテスト
対象が仕様どおりかを確認する

ユニットテストの特徴

プログラムとして実行できる仕様書となるところ
- ユニットテストが成功する限り。正しい仕様書であることが保証される
あいまいさや、実行誤りがない
再実行のコストが低い

ユニットテストの目的

直接の目的は、品質向上ではない
目的は、仕様を明確にし、仕様を保証すること
テストコードを先に記述する、テスト駆動開発などもある

ユニットテストのフレームワーク

JUnit
TestNG
両者に機能面で大きな差異はない
テストフレームワークを使うことで、テストケースの設計と実装に専念できる

2.4 ユニットテストのパターン

xUnit Test Patterns から重要なパターンを引用

自動化されたテスト - 繰り返しいつでも実行できる
不安定なテスト - 結果が一定でないテストを避ける
- テスト失敗の状態を放置しない
ドキュメントとしてのテスト - 仕様書として読める
- テストケースの可読性が高いと、プロダクションコードのコントが減る。
問題の局在化 - テスト失敗時に問題特定しやすい
- テストケースは「小さく」「たくさん」
不明瞭なテスト - 可読性の低いテストコードは避ける
- リファクタリング大事
- データクラスの検証は、フィールドごとにするか、カスタムmatcherが吉
独立したテスト - 実行順序に依存しないこと
- シングルトンなリソースとかでは起こりがち
- テスト後に、テスト前状態に戻すのがミソ
- 全テストボリュームが大きくなってきた時に、分散実行できるように！
- ハードコーディングされた設定ファイル読み込み、ミュータブルオブジェクトをシングルトンにする、などで発現しがちなので、注意

シングルトンオブジェクトの注意点

テストの独立性を破壊する
テストの後処理と初期化処理を複雑にする
テストを不安定にする
- テストを並列実行できない
モック/スタブとの関係
- テスト用モックやスタブを作成できない
  - シングルトンパターン
    - コンストラクタ: private
    - インスタンス取得: staticメソッド経由
- シングルトンオブジェクトを利用しているコードをテスト用コードに置き換えて実行することも、難しい

JUnit実践入門 ~体系的に学ぶユニットテストの技法 (WEB+DB PRESS plus)

作者: 渡辺修司
出版社/メーカー: 技術評論社
発売日: 2012/11/21
メディア: 単行本（ソフトカバー）
購入: 14人クリック: 273回
この商品を含むブログ (65件) を見る

2014-01-20

JUnit 実践入門　体系的に学ぶユニットテストの技法 - 第1章 JUni tチュートリアル

コンピュータ Java 本

第1章 JUnit チュートリアル

1.3 JUnitテストを始めよう

"junit-tutorial" プロジェクトを作成
JUnit の JAR ファイルを追加
- [JAR ファイルをプロジェクトにコピペ] -> [(右クリックから)Build Path] -> [Add to Build Path]
"Calculator" クラス作成
- Package: junit.tutorial
テストクラス作成
- プロジェクトのコンテキストメニュー から、[Build Path] -> [New Source Folder]
  - Folde Name: test
- ソースフォルダのコンテキストメニューから、[New] -> [JUnit Test Case]
  - "New JUnit 4 test" を選択
  - Package: junit.tutorial
  - Name: CalculatorTest
  - Class under test: junit.tutorial.Calculator
テストクラス JUnitテスト実施 -> 未実装につき失敗

1.4 テストコードの記述

JUnit テストコードのルール
- テストクラスは public クラス
- テストメソッドは、org.junit.Test アノテーションを付与した、public メソッドてする
- テストメソッドは、戻り値が　void であり、引数を持たない
- throw 句は自由に定義可能
日本語メソッド名でわかりやすくする
- Javadoc にもメソッドの一覧は出力されるので、テスト項目の一覧として閲覧できる
- テストクラスのアウトラインを参照すれば、テストクラスで実施しているテストが簡単に把握できる
- テスト失敗時のレポートも、より理解しやすくなる
  - 句読点使用不可
  - 先頭文字として数字を使用不可
ユニットテストは、「あるテスト対象クラスのメソッドを実行した時に、戻り値などで取得された実際の値と、期待される値が一致する(しない)はずである」という宣言で構成される
- 値を比較検証する宣言のことを、アサーションという
- JUnit では、org.junit.Assert クラスの、assertThat メソッドを使用する
- Java に組み込まれている assert とは別物なので注意
ユニットテストを作り、具体的な値を当てはめることで、プログラムの潜在的な問題を見つけられる
テスト対象クラスが完璧に設計されていることを前提とせずに、「何を検証すべきか？」を強く意識する
このような考え方を強く意識する開発手法をテスト駆動開発と呼ぶ

プロダクションコード

package junit.tutorial;

public class Calculator {
    public int multiply(int x, int y) {
        return x * y;
    }
    public float divide(int x, int y) {
        if (y == 0) {
            throw new IllegalArgumentException("divide by zero");
        }
        return (float) x/ (float) y;
    }
}

テストコード

package junit.tutorial;

import static org.junit.Assert.*;
import static org.hamcrest.CoreMatchers.*;
import org.junit.Test;

public class CalculatorTest {

    @Test
    public void multiplyで3と4の乗算結果が取得できる() {
        Calculator calc = new Calculator();
        int expected = 12;
        int actual = calc.multiply(3, 4);
        assertThat(actual, is(expected));
    }

    @Test
    public void multiplyで5と7の乗算結果が取得できる() {
        Calculator calc = new Calculator();
        int expected = 35;
        int actual = calc.multiply(5, 7);
        assertThat(actual, is(expected));
    }

    @Test
    public void divideで3と2の除算結果が取得できる() {
        Calculator calc = new Calculator();
        float expected = 1.5f;
        float actual = calc.divide(3, 2);
        assertThat(actual, is(expected));
    }

    @Test(expected = IllegalArgumentException.class)
    public void divideで5と0のときIlegalArgumentExceptionを送出する() {
        Calculator calc = new Calculator();
        float actual = calc.divide(5, 0);
    }
}

JUnit実践入門 ~体系的に学ぶユニットテストの技法 (WEB+DB PRESS plus)

作者: 渡辺修司
出版社/メーカー: 技術評論社
発売日: 2012/11/21
メディア: 単行本（ソフトカバー）
購入: 14人クリック: 273回
この商品を含むブログ (65件) を見る

2014-01-20

JUnit 実践入門　体系的に学ぶユニットテストの技法　付録B Eclipse の便利機能と設定

コンピュータ Java 本

付録B　Eclipse の便利機能と設定

B.2 テキストファイルのエンコーディング

[General] - [workspace]
- [Text file encoding] を "UTF-8" に設定

B.3 static インポートのワイドカード

[Java] -> [Code Style] -> [Organize Imports]
- [Number of tatic import needed for .*] を "1" に設定

B.4 Quick JUnit

[Help] -> [Eclipse Marketplace]
- "Quick JUnit" を検索、インストール

B.6 テンプレート

[Java] -> [Editor] -> [Templates]
- サポートページからダウンロードした XML をインポート

B.7 次の注釈

CTRL + "." で飛べる

JUnit実践入門 ~体系的に学ぶユニットテストの技法 (WEB+DB PRESS plus)

作者: 渡辺修司
出版社/メーカー: 技術評論社
発売日: 2012/11/21
メディア: 単行本（ソフトカバー）
購入: 14人クリック: 273回
この商品を含むブログ (65件) を見る

2014-01-20

明解 Javaによるアルゴリズムとデータ構造　6-6_クイックソート

コンピュータ Java 本

6-6 クイックソート

クイックソートの概略

クイックソート quick sort は、最も高速なアルゴリズムの一つ。
C.A.R.Hoare が考案。
配列 a を枢軸 x pivot で分割することを繰り返す。

分割の手順

a[pl] >= x が成立する要素が見つかるまで pl を右方向に走査
a[pr] <= x が成立する要素が見つかるまで pr を左方向に走査
走査が共に止まったら、要素を入れ替える
配列は以下のように分類される
- 枢軸以下のグループ　…　a[0], …, a[pl - 1]
- 枢軸以上のグループ　…　a[pr + 1], …, a[n - 1]
- pl > pr + 1 の時に限り、
  - 枢軸と一致するグループ　…　a[pr + 1], …, a[pl - 1]

クイックソート

分割を繰り返していくのがクイックソート
要素数が 1 になるまで分割を続ける。すなわち、
- pr が先頭より右側に位置する (left < pr) のであれば(2つ以上の要素が存在するので)、左グループをさらに分割
- pl が末尾より左側に位置する (pl < right) のであれば(2つ以上の要素が存在するので)、→グループをさらに分割
- 中央グループが存在する場合、分割の対象から外れる(分割の必要が無いため)。
離れた 2 要素を交換するため、安定でない

ソースコード

quickSort(int[] a, int left, int right) 版

import java.util.Scanner;

class QuickSort {
    static void swap(int[] a, int idx1, int idx2) {
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }

    static void quickSort(int[] a, int left, int right) {
        int pl = left;
        int pr = right;
        int x = a[(pl + pr) / 2];

        do {
            while (a[pl] < x) {
                pl++;
            }
            while (a[pr] > x) {
                pr--;
            }
            if (pl <= pr) {
                swap(a, pl++, pr--);
            }
        } while (pl <= pr);

        if (left < pr) {
            quickSort(a, left, pr);
        }
        if (pl < right) {
            quickSort(a, pl, right);
        }
    }

    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        System.out.println("クイックソート");
        System.out.print("要素数: ");
        int nx = stdIn.nextInt();
        int[] x = new int[nx];
        
        for (int i= 0; i < nx; i++) {
            System.out.print("x[" + i + "]: ");
            x[i] = stdIn.nextInt();
        }
        quickSort(x, 0, nx - 1);
        
        System.out.println("昇順にソートしました。");
        for (int i = 0; i < nx; i++) {
            System.out.println("x[" + i + "]: " + x[i]);
        }
    }
}

quickSort(int[] a, int n) 版
- 解答を見るに、現行メソッド活かして、オーバーロードで書いてねという趣旨らしい。先に言ってよ。

import java.util.Scanner;

class QuickSort2 {
    static void swap(int[] a, int idx1, int idx2) {
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }

    static void quickSort(int[] a, int n) {
        int pl = 0;
        int pr = n - 1;
        int x = a[(pl + pr) / 2];

        do {
            while (a[pl] < x) {
                pl++;
            }
            while (a[pr] > x) {
                pr--;
            }
            if (pl <= pr) {
                swap(a, pl++, pr--);
            }
        } while (pl <= pr);
        
        if (0 < pr) {
            int[] b = new int[pr + 1];
            for (int i = 0; i < pr + 1; i++) {
                b[i] = a[i];
            }
            quickSort(b, pr + 1);
            for (int i = 0; i < pr + 1; i++) {
                a[i] = b[i];
            }
        }
        if (pl < n - 1) {
            int[] b = new int[n - pl];
            for (int i = 0; i < n - pl; i++) {
                b[i] = a[pl + i];
            }
            quickSort(b, n - pl);
            for (int i = 0; i < n - pl; i++) {
                a[pl + i] = b[i];
            }
        }
    }

    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        System.out.println("クイックソート");
        System.out.print("要素数: ");
        int nx = stdIn.nextInt();
        int[] x = new int[nx];
        
        for (int i= 0; i < nx; i++) {
            System.out.print("x[" + i + "]: ");
            x[i] = stdIn.nextInt();
        }
        quickSort(x, nx);
        
        System.out.println("昇順にソートしました。");
        for (int i = 0; i < nx; i++) {
            System.out.println("x[" + i + "]: " + x[i]);
        }
    }
}

実行結果

クイックソート
要素数: 9
x[0]: 44
x[1]: 88
x[2]: 77
x[3]: 55
x[4]: 66
x[5]: 99
x[6]: 22
x[7]: 11
x[8]: 33
昇順にソートしました。
x[0]: 11
x[1]: 22
x[2]: 33
x[3]: 44
x[4]: 55
x[5]: 66
x[6]: 77
x[7]: 88
x[8]: 99

非再帰的クイックソート

Stack 使って、配列の左端と右端を保持していればよい。

ソースコード

   static void quickSort(int[] a, int left, int right) {
        IntStack lstack = new IntStack(right - left + 1);
        IntStack rstack = new IntStack(right - left + 1);
        lstack.push(left);
        rstack.push(right);

        while (lstack.isEmpty() != true) {
            int pl = left = lstack.pop();
            int pr = right = rstack.pop();
            int x = a[(pl + pr) / 2];

            System.out.printf("a[%d]~a[%d] : {", left, right);
            for (int i = left; i < right; i++) {
                System.out.printf("%d, ", a[i]);
            }
            System.out.printf("%d}\n", a[right]);

            do {
                while (a[pl] < x) {
                    pl++;
                }
                while (a[pr] > x) {
                    pr--;
                }
                if (pl <= pr) {
                    swap(a, pl++, pr--);
                }
            } while (pl <= pr);

            if (left < pr) {
                lstack.push(left);
                rstack.push(pr);
            }
            if (pl < right) {
                lstack.push(pl);
                rstack.push(right);
            }
        }
    }

スタックの容量

分割後の要素数が少ない方から、分割を実施する方針を採る
- スタックに積まれる数は、分割数に依存するから
- 一般に、要素数の少ない配列のほうが、要素数の大きい配列よりも、分割 / ソートが簡単だから
積まれる総計が減少するわけではない。同時に積まれる数が減少するのみ。
配列の要素数 n であれば、スタックに積まれるデータ数は log n となる。

枢軸の選択

2分割は、同じ数に分かれるのが、最も効率がよい。1 : n-1 とかは最悪。
- 枢軸の取り方が、効率に大きな影響を与える。
中央値がベストであるが、中央値算出にはそれなりのコストが必要。次善の策が求められる。
分割すべき配列の先頭要素/中央要素/末尾要素の3要素をソートし、さらに中央要素と末尾から2番目の要素を交換する。枢軸として、末尾から2番目の要素の値 a[right - 1] を採用し、分割の対象を a[left + 1] ～ a[right - 2] に絞り込む。
- これだと、3要素での中央値算出と、中央要素と末尾から2番目の要素のスワップ1回を代償として、partition のための走査が pl + 1, pr - 2 から始められる。

時間計算量

一般には
- パーティションでコスト n に加え、分割された小配列2つでのコストがそれぞれ・・・って再帰的に計算する
- 某スレの17さんがわかりやすい

反映したコード

再帰版

import java.util.Scanner;

class QuickSort4 {
    static void swap(int[] a, int idx1, int idx2) {
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }

    static int getMed(int a, int b, int c) {
        if (a >= b) {
            if (b >= c) {
                return b;
            } else {
                return c;
            }
        } else {
            if (a >= c) {
                return a;
            } else {
                return b;
            }
        }
    }
    
    static void insertionSort(int[] a, int n) {
        for (int i = 1; i < n; i++) {
            int j;
            int tmp = a[i];
            for (j = i; j > 0 && a[j - 1] > tmp; j--) {
                a[j] = a[j - 1];
            }
            a[j] = tmp;
        }
    }

    static void quickSort(int[] a, int left, int right) {
        if (right - left + 1 <= 9) {
            insertionSort(a, right - left + 1);
        } else {
            int pl = left;
            int pr = right;

            int x;
            // 要素数3以上なら枢軸を工夫する
            if (pr - pl >= 2 ) {
                x = getMed(a[0], a[(pl + pr)/2], a[pr]);
            // 3未満なら工夫しない
            } else {
                x = a[(pl + pr) / 2];
            }
            
            System.out.printf("a[%d]~a[%d] : {" , left, right);
            for (int i = left; i < right; i++) {
                System.out.printf("%d, ", a[i]);
            }
            System.out.printf("%d}\n", a[right]);
            
            // 高速化のおまじない
            swap(a, (pl+pr)/2, pr+1);
            pr = pr -2;
            pl = pl +1;
            
            do {
                while (a[pl] < x) {
                    pl++;
                }
                while (a[pr] > x) {
                    pr--;
                }
                if (pl <= pr) {
                    swap(a, pl++, pr--);
                }
            } while (pl <= pr);

            if (left < pr) {
                quickSort(a, left, pr);
            }
            if (pl < right) {
                quickSort(a, pl, right);
            }
        }
    }

    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        System.out.println("クイックソート");
        System.out.print("要素数: ");
        int nx = stdIn.nextInt();
        int[] x = new int[nx];

        for (int i= 0; i < nx; i++) {
            System.out.print("x[" + i + "]: ");
            x[i] = stdIn.nextInt();
        }
        quickSort(x, 0, nx - 1);

        System.out.println("昇順にソートしました。");
        for (int i = 0; i < nx; i++) {
            System.out.println("x[" + i + "]: " + x[i]);
        }
    }
}

非再帰版

import java.util.Scanner;


class QuickSortNotRecursive {
    static void swap(int[] a, int idx1, int idx2) {
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }

    static void insertionSort(int[] a, int n) {
        for (int i = 1; i < n; i++) {
            int j;
            int tmp = a[i];
            for (j = i; j > 0 && a[j - 1] > tmp; j--) {
                a[j] = a[j - 1];
            }
            a[j] = tmp;
        }
    }

    static int getMed(int a, int b, int c) {
        if (a >= b) {
            if (b >= c) {
                return b;
            } else {
                return c;
            }
        } else {
            if (a >= c) {
                return a;
            } else {
                return b;
            }
        }
    }
    
    static void quickSort(int[] a, int left, int right) {
        if (right - left + 1 <= 9) {
            insertionSort(a, right - left + 1);
        } else {
            
            IntStack lstack = new IntStack(right - left + 1);
            IntStack rstack = new IntStack(right - left + 1);
            lstack.push(left);
            rstack.push(right);
            while (lstack.isEmpty() != true) {
                int pl = left = lstack.pop();
                int pr = right = rstack.pop();
                
                int x;
                // 要素数3以上なら枢軸を工夫する
                if (pr - pl >= 2 ) {
                    x = getMed(a[0], a[(pl + pr)/2], a[pr]);
                // 3未満なら工夫しない
                } else {
                    x = a[(pl + pr) / 2];
                }

                System.out.printf("a[%d]~a[%d] : {", left, right);
                for (int i = left; i < right; i++) {
                    System.out.printf("%d, ", a[i]);
                }
                System.out.printf("%d}\n", a[right]);

                // 高速化のおまじない
                swap(a, (pl+pr)/2, pr+1);
                pr = pr -2;
                pl = pl +1;
                
                do {
                    while (a[pl] < x) {
                        pl++;
                    }
                    while (a[pr] > x) {
                        pr--;
                    }
                    if (pl <= pr) {
                        swap(a, pl++, pr--);
                    }
                } while (pl <= pr);

                if (pr - left > right - pl) {
                    if (left < pr) {
                        lstack.push(left);
                        rstack.push(pr);
                    }
                    if (pl < right) {
                        lstack.push(pl);
                        rstack.push(right);
                    }
                } else {
                    if (pl < right) {
                        lstack.push(pl);
                        rstack.push(right);
                    }
                    if (left < pr) {
                        lstack.push(left);
                        rstack.push(pr);
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        System.out.println("クイックソート");
        System.out.print("要素数: ");
        int nx = stdIn.nextInt();
        int[] x = new int[nx];

        for (int i = 0; i < nx; i++) {
            System.out.print("x[" + i + "]: ");
            x[i] = stdIn.nextInt();
        }
        quickSort(x, 0, nx - 1);

        System.out.println("昇順にソートしました。");
        for (int i = 0; i < nx; i++) {
            System.out.println("x[" + i + "]: " + x[i]);
        }
    }
}

明解 Javaによるアルゴリズムとデータ構造

作者: 柴田望洋
出版社/メーカー: ソフトバンククリエイティブ
発売日: 2007/11/07
メディア: 単行本
購入: 5人クリック: 42回
この商品を含むブログ (19件) を見る

2014-01-20

明解 Javaによるアルゴリズムとデータ構造　6-5_シェルソート

コンピュータ Java 本

6-5 シェルソート

単純挿入ソートの特徴

ソート済みあるいは、それに近い状態では高速である
挿入先が遠くはなれている場合、移動(代入)回数が多くなる

シェルソート

シェルソート shell sort は、単純挿入ソートの長所を活かしたまま、その短所を補う事によって、高速なソートを行うアルゴリズムである。
D.L.Shell が考案。
クイックソートが考案されるまで、最速だった。
最初に離れた要素をグループ化しておおまかなソートを行い、そのグループを縮小しながらソートを繰り返す
- このギャップの設定にはいくつかあるが、一般には Knuth の方法が取られる。
  $1,\ 4,\ 13,\ 40,\ 121,\ \cdots,\ \frac{3^{k}-1}{2}$
- 初期のギャップがあまり大きくても無駄とわかっているため、 n / 9 を超えないようにする。
- Knuth の方法の場合の時間計算量:
  $O(n^{1.25})$
  nが極めて小さい時以外は、
  $O(n^{2})$
  のソートアルゴリズムよりもコストが低い。
安定ではない

ソースコード

gap はただただ 1/2 していくだけ

import java.util.Scanner;

class ShellSort {
    static void shellSort(int[]a, int n) {
        int moveCnt = 0;
        for (int h = n / 2; h > 0; h /= 2) {
            for (int i = h; i < n; i++) {
                int j;
                int tmp = a[i];
                for (j = i - h; j >= 0 && a[j] > tmp; j -= h) {
                    a[j+h]=a[j];
                    moveCnt++;
                }
                a[j+h] = tmp;
                moveCnt++;
            }
        }
        System.out.println("交換回数: " + moveCnt);
    }

    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        System.out.println("シェルソート");
        System.out.print("要素数: ");

        int nx = stdIn.nextInt();
        int[] x = new int[nx];
        
        for (int i = 0; i < nx; i++) {
            System.out.print("x[" + i + "]: ");
            x[i] = stdIn.nextInt();
        }
        shellSort(x, nx);
        
        System.out.println("昇順にソートしました");
        for (int i = 0; i < nx; i++) {
            System.out.println("x[" + i + "]: " + x[i]);
        }
    }
}

gap は Knuth 式

import java.util.Scanner;

class ShellSort2 {
    static void shellSort(int[]a, int n) {
        int h;
        int moveCnt = 0;
        for (h = 1; h < n / 9; h = h * 3 + 1) {
            ;
        }
        
        for ( ; h > 0; h /= 3) {
            for (int i = h; i < n; i++) {
                int j;
                int tmp = a[i];
                for (j = i - h; j >= 0 && a[j] > tmp; j -= h) {
                    a[j+h]=a[j];
                    moveCnt++;
                }
                a[j+h] = tmp;
                moveCnt++;
            }
        }
        System.out.println("交換回数: " + moveCnt);
    }

    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        System.out.println("シェルソート");
        System.out.print("要素数: ");

        int nx = stdIn.nextInt();
        int[] x = new int[nx];
        
        for (int i = 0; i < nx; i++) {
            System.out.print("x[" + i + "]: ");
            x[i] = stdIn.nextInt();
        }
        shellSort(x, nx);
        
        System.out.println("昇順にソートしました");
        for (int i = 0; i < nx; i++) {
            System.out.println("x[" + i + "]: " + x[i]);
        }
    }
}

実行結果

降順に並んでいるような状態からだと、後者のほうがコストが高いように見えた。なぜ？

明解 Javaによるアルゴリズムとデータ構造

作者: 柴田望洋
出版社/メーカー: ソフトバンククリエイティブ
発売日: 2007/11/07
メディア: 単行本
購入: 5人クリック: 42回
この商品を含むブログ (19件) を見る

6-7 マージソート

ソート済み配列のマージ

出力結果

Arrays.sort によるクイックソートとマージソート

基本型配列のソート(クイックソート)

クラスオブジェクトの配列のソート(マージソート)

自然順序

コンパレータ

コンパレータ2

第3章 テスティングフレームワーク テストを支えるしくみ

3.1 テスティングフレームワークとは

xUnit フレームワーク

3.2 JUnit によるユニットテストの記法

テストソッドの throw 句

テストメソッドを簡単に挿入する

3.3 可読性の高いテストコードの書き方

テストケース

テスト対象

実測値と期待値

メソッドと副作用

4フェーズテスト

テストフィクスチャ test fixture

3.4 比較検証を行うアサーション

JUnit のアサーション

3.5 JUnit が提供するアノテーション

@Test - テストメソッドを宣言する

@Ignore - テストの実行から除外する

@Before - テスト実行前に処理を行う

@After - テスト実行後の後処理を行う

@BeforeClass - テスト実行前に一度だけ処理を行う

3.6 JUnit のテストパターン

第2章 ユニットテスト 何のためにテストするのか

2.1 ソフトウェアテストとは

ソフトウェアテストの特徴

テストケースとテストスイート

ソフトウェアテストの目的

ソフトウェアテストの限界

2.2 テスト技法

ホワイトボックステストとブラックボックステスト

同値クラスに対するテスト

境界値に対するテスト

2.3 ユニットテスト

ユニットテストの特徴

ユニットテストの目的

ユニットテストのフレームワーク

2.4 ユニットテストのパターン

シングルトンオブジェクトの注意点

第1章 JUnitチュートリアル

1.3 JUnitテストを始めよう

1.4 テストコードの記述

プロダクションコード

テストコード

付録B Eclipse の便利機能と設定

B.2 テキストファイルのエンコーディング

B.3 static インポートのワイドカード

B.4 Quick JUnit

B.6 テンプレート

B.7 次の注釈

6-6 クイックソート

クイックソートの概略

分割の手順

非再帰的クイックソート

スタックの容量

枢軸の選択

時間計算量

反映したコード

再帰版

非再帰版

6-5 シェルソート

単純挿入ソートの特徴

実行結果

6-7　マージソート

第3章テスティングフレームワークテストを支えるしくみ

第2章ユニットテスト何のためにテストするのか

第1章 JUnit チュートリアル

付録B　Eclipse の便利機能と設定