マージソート

安定ソートの実装を確認する。

環境

Javaによるマージソートの実装

package org.tea4miki.util;

import java.util.ArrayList;
import java.util.List;

/**
 * このクラスはソートを扱うユーティリティです。
 */
public final class SortUtils {
    
    /**
     * 安定ソートを行います。
     * 
     * リスト内のオブジェクトのtoString().compareTo()を使用して
     * 昇順にソートします。
     * 
     * @param list ソートされるリスト
     */
    public static <T> void sortStable(List<T> list) {
        MergeSort<T> sorter = new MergeSort<>();
        sorter.sort(list);
    }
    
    /**
     * マージソートを行うクラスです。
     * 
     * この実装は、奥村晴彦氏によるC言語用のマージソートをJava言語に移植したものです。
     * 奥村晴彦『C言語による最新アルゴリズム辞典』(技術評論社)(1991年2月25日 初版 第1刷発行)の
     * 267-268ページに記載されている内容をもとにしています。
     * 
     * 『C言語による最新アルゴリズム事典』のサポートページ
     * https://oku.edu.mie-u.ac.jp/~okumura/algo/
     * 
     * @param <T> リスト内のオブジェクトのクラス
     */
    private static class MergeSort<T> {
        /**
         * ソートされるリスト。
         */
        List<T> src = null;
        /**
         * ソートの作業領域のリスト。
         */
        List<T> work = null;
        
        /**
         * マージソートを行います。
         * 
         * リスト内のオブジェクトのtoString().compareTo()を使用して
         * 昇順にソートします。
         * 
         * @param list ソートされるリスト
         */
        public void sort(List<T> list) {
            if ((list == null) || (list.size() < 2)) {
                return;
            }
            
            src = list;
            
            int workSize = list.size() / 2 + 1;
            work = new ArrayList<T>(workSize);
            for (int i = 0; i < workSize; i++) {
                work.add(null);
            }
            
            sortImpl(0, list.size() - 1);
            
            src = null;
            work = null;
        }
        
        /**
         * マージソートを行います。
         * 
         * @param first ソートする範囲の開始位置
         * @param last ソートする範囲の終了位置
         */
        private void sortImpl(int first, int last) {
            if (first < last) {
                int middle = (first + last) / 2;
                
                sortImpl(first, middle);
                sortImpl(middle + 1, last);
                
                int p = 0;
                for (int i = first; i <= middle; i++) {
                    work.set(p, src.get(i));
                    p++;
                }
                
                int i = middle + 1;
                int j = 0;
                int k = first;
                
                while ((i <= last) && (j < p)) {
                    if (work.get(j).toString().compareTo(src.get(i).toString()) <= 0) {
                        src.set(k, work.get(j));
                        k++;
                        j++;
                    }
                    else {
                        src.set(k, src.get(i));
                        k++;
                        i++;
                    }
                }
                
                while (j < p) {
                    src.set(k, work.get(j));
                    k++;
                    j++;
                }
            }
        }
    }
    
}
    

Javaによるマージソートの実装の動作確認

package org.tea4miki.test;

import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import org.tea4miki.util.SortUtils;

public final class SortUtilsSortStableTest {
    /**
     * ソートされるリストのサイズ。
     */
    private static final int LIST_SIZE = 90;
    
    /**
     * マージソートの動作確認を行います。
     * @param args コマンドライン引数
     */
    public static void main(String[] args) {
        Random rand = new Random();
        
        List<Item> list = new ArrayList<>();
        for (int i = 0; i < LIST_SIZE; i++) {
            Item listItem = new Item();
            listItem.key = rand.nextInt(10);
            listItem.info = i;
            
            list.add(listItem);
        }
        
        show(list);
        SortUtils.sortStable(list);
        
        System.out.println("マージソートは安定です。");
        show(list);
        
        //ソートの確認。
        for (int i = 0; i < list.size(); i++) {
            if (i > 0) {
                Item prev = list.get(i - 1);
                Item next = list.get(i);
                
                if (prev.key > next.key) {
                    throw new RuntimeException("not sorted!");
                }
            }
        }
        
        //安定の確認。
        for (int i = 0; i < list.size(); i++) {
            if (i > 0) {
                Item prev = list.get(i - 1);
                Item next = list.get(i);
                
                if (prev.key == next.key) {
                    if (prev.info >= next.info) {
                        throw new RuntimeException("not stable!");
                    }
                }
            }
        }
        
        System.out.println("end.");
    }
    
    /**
     * ソートされるリストをコンソールに表示します。
     * @param list ソートされるリスト
     */
    private static void show(List<Item> list) {
        for (int i = 0; i < 10; i++) {
            for (int m = i; m < LIST_SIZE; m += 10) {
                System.out.printf("%5d:%2d", list.get(m).info, list.get(m).key);
            }
            System.out.println();
        }
    }
    
    /**
     * ソートされるリスト内のオブジェクトのクラス。
     */
    private static class Item {
        /**
         * ソートするランダムな値。
         */
        public int key;
        /**
         * 安定ソートであることを確認するために
         * オブジェクトの生成時に設定した連番。
         */
        public int info;
        /**
         * key値がこのオブジェクトのtoString().compareTo()で
         * 昇順になるように固定幅にする。
         */
        private DecimalFormat df = new DecimalFormat("0000000000");

        /**
         * このメソッドはkey値を固定幅にした文字列を返します。
         */
        @Override
        public String toString() {
            return df.format(key);
        }
    }
}
    

ダウンロード

ソートを扱うユーティリティクラス

SortUtils.java

マージソートの動作確認

SortUtilsSortStableTest.java

関連情報

2015, AfternoonTea