アルゴ演習15-4

Algo15_ex4.java

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * Created by owner on 2015/10/15.
 */
public class Algo15_ex4 {
    public static void main(String[] args) {
        TestSort2.main(args);
    }
}

abstract class SortableBase {
    protected int[] array;

    public SortableBase(String filename) {
        try (Stream<String> st = Files.lines(Paths.get(filename))) {
            array = st.mapToInt(Integer::parseInt).toArray();
        } catch (IOException | NumberFormatException e) {
            e.printStackTrace();
            System.exit(1);
        }
    }

    public abstract void sort();

    protected final void swapArray(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public void output(String filename) {
        List<String> outList = Arrays.stream(array).<String>mapToObj(String::valueOf).collect(Collectors.toList());

        try {
            Files.write(Paths.get(filename), outList);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

class QuickSort extends SortableBase {

    public QuickSort(String filename) {
        super(filename);
    }

    @Override
    public void sort() {
        quickSort(0, array.length - 1);
    }

    private void quickSort(int l, int r) {
        if (!(l < r)) return;

        int v = partition(l, r);

        quickSort(l, v - 1);
        quickSort(v + 1, r);
    }

    private int partition(int l, int r) {
        int i = l;
        int j = r - 1;

        while (true) {
            do if (array[i] > array[r]) break; while (++i < r);  // 1.ピボットよりも大きな要素が見つかるまで，ポインタiを右ヘ進める
            do if (array[j] < array[r]) break; while (--j >= l); // 2.ピボットよりも小さな要素が見つかるまで，ポインタjを左ヘ進める

            if (i > j) break;
            // 4.ポインタiとjが入れ替わっていたらやめる
            // i < r, j > 0 は反対側の初期値により自明(必ずこのifでbreakする)

            swapArray(i, j); // 3.ポインタiが指す要素とポインタjが指す要素を入れ替える
        }
        swapArray(i, r); // 5.最後に，ポインタiが指している要素をピボット（右端の要素）と交換する

        return i; // 入れ替えたためiがピボットになっているので返す
    }

    public static void main(String[] args) {

        String inFile = "rand2.txt";
        String outFile = "result_ex4-1_rand2.txt";

        QuickSort s = new QuickSort(inFile);
        s.sort();
        s.output(outFile);
    }
}

class MergeSort extends SortableBase {

    public MergeSort(String filename) {
        super(filename);
    }

    public void sort() {
        mergeSort(0, array.length - 1);
    }

    private void mergeSort(int l, int r) {
        if (!(l < r)) return;

        int v = (r + l) / 2; // 1.データ列を真ん中で2つの部分列に分割する
        mergeSort(l, v);     // 2.部分列をそれぞれソートする
        mergeSort(v + 1, r);

        int[] left  = Arrays.copyOfRange(array, l, v + 1);
        int[] right = Arrays.copyOfRange(array, v + 1, r + 1);
        int i = 0, j = 0;
        while (i < left.length || j < right.length) { // 3.ソート済になった部分列をマージする
            if (i >= left.length) {
                array[l + i + j] = right[j];
                j++;
            }
            else if (j >= right.length){
                array[l + i + j] = left[i];
                i++;
            }
            else if (left[i] < right[j]) {
                array[l + i + j] = left[i];
                i++;
            }
            else {
                array[l + i + j] = right[j];
                j++;
            }
        }
    }

    public static void main(String[] args) {

        String inFile = "rand2.txt";
        String outFile = "result_ex4-2_rand2.txt";

        MergeSort s = new MergeSort(inFile);
        s.sort();
        s.output(outFile);
    }
}

class TestSort2 {
    public static void main(String[] args) {
        String file1 = "rand2.txt";
        String file2 = "sorted2.txt";
        String file3 = "reverse2.txt";
        String file4 = "same2.txt";

        List<String> files = Arrays.asList(file1, file2, file3, file4);
        files.forEach(filename -> {
            List<SortableBase> sorts = Arrays.asList(
                    new BubbleSort(filename),
                    new SelectionSort(filename),
                    new InsertionSort(filename),
                    new QuickSort(filename),
                    new MergeSort(filename)
            );

            System.out.println(String.format("%sのソート", filename));

            sorts.forEach(sort -> {
                long start = System.currentTimeMillis();
                sort.sort();
                long stop = System.currentTimeMillis();
                System.out.println(String.format("%s : %d [ms]", sort.getClass().getSimpleName(), stop - start));
            });
        });
    }
}