明解 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によるアルゴリズムとデータ構造

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