Javaによるマージソート

Question

前提・実現したいこと

マージソートをしたいです

発生している問題・エラーメッセージ

エラーはなく実行されるのですが、結果がソートされていません
どこを直すべきか教えてください

以下実行結果

{3, 2, 8, 4, 5, 7, 1, 0, 6, 9} // ソート前
{3, 2, 7, 1, 0, 6, 8, 4, 5, 9} // ソート後

該当のソースコード

public class testMeregeSort {
	private final int n = 10;
	private int[] a = { 3, 2, 8, 4, 5, 7, 1, 0, 6, 9 };

	public testMeregeSort() {
	}

	private void mergesort(int low, int high) {
		int xSize = (high - low + 1) / 2;
		int ySize = (high + 1) - xSize;
		int[] x = new int[xSize];
		int[] y = new int[ySize];
		int[] z = new int[n];
		int xIndex = 0;
		int yIndex = 0;

		if (high - low + 1 <= 1) {
			return;
		}

		// ここから分割
		for (int i = 0; i < xSize; i++) {
			x[i] = a[i];
		}

		for (int i = 0; i < ySize; i++) {
			y[i] = a[i + xSize];
		}

		mergesort(0, xSize - 1);
		mergesort(0, ySize - 1);

		// ここからマージ
		while (xIndex < xSize && yIndex < ySize) {
			if (x[xIndex] <= y[yIndex]) {
				z[xIndex + yIndex] = x[xIndex];
				xIndex++;
			} else {
				z[xIndex + yIndex] = y[yIndex];
				yIndex++;
			}
		}

		if (xIndex >= xSize) {
			for (int i = yIndex; i < ySize; i++) {
				z[i + xIndex] = y[i];
			}
		} else {
			for (int i = xIndex; i < xSize; i++) {
				z[i + yIndex] = x[i];
			}
		}

		for (int i = 0; i < n; i++) {
			a[i] = z[i];
		}

	}

	public void sort() {
		mergesort(0, a.length - 1);

		for (int i = 0; i < n; i++) {
			System.out.println(a[i]);
		}
	}

	public static void main(String[] args) {
		testMeregeSort ms = new testMeregeSort();
		ms.sort();
	}
}

Answer 1

とりあえず、クラスの名前はtestMergeSortに直すべきだと思います。
(課題などで指定がある場合は仕方ないです(丸投げはやめてほしいですが))。

けっこういっぱい間違いがありましたので、下記の修正したソースコードに、コメントで直接間違っていた内容を記入しておきました( !-- --! で囲まれたコメントの部分が間違いです。それ以外はお節介だと思ってください)。

基本的に使用する直前に変数宣言は移動してあります。
古い教科書などでは最初にまとめて変数宣言するのもありがちですが、
どこで使っているのかが追いかけ辛くなります。

あと、マージソートは引数の扱いが微妙に違うものがありまして、

• low から high をソートするもの(今回)
• low から high - 1 をソートするもの(mergesort(0, a.length)のように呼び出せて便利)

などがあります。
どこからどこまでをソートする、などの要件は次回から明確に記していただけるとありがたく思います。

実行時にログが出るようにしておきましたので、動作のイメージを掴んでみてください。

public class testMeregeSort {
    private int[] a = { 3, 2, 8, 4, 5, 7, 1, 0, 6, 9 };
    private final int n = a.length;

    public testMeregeSort() {
    }

    /**
     * 配列の low ~ high をソートする
     * 
     * @param low  ソートしたい要素の先頭を指す
     * @param high ソートしたい要素の一番最後の要素を指す
     */
    private void mergesort(int low, int high) {
        // いくつかログを出すsysoutを追加したので、消したければ消してください
        System.out.println("関数呼び出し >>> low: " + low + " high: " + high);

        // high - low + 1 <= 1 でもいいのですが、
        // こちらのほうが意味も明快で、シンプルで良いと思います
        // 計算式系を維持するなら high - low <= 0 でもよいと思います
        if (low >= high) {
            return;
        }

        final int len = high - low + 1; // low ~ high までの長さ
        final int xSize = len / 2;
        final int ySize = len - xSize; // !-- yの長さは high - low + 1 - xSize です --!
        int[] x = new int[xSize];
        int[] y = new int[ySize];

        // !-- 再帰先が間違っていました --!
        // 分割点をxとyの分割サイズと合わせる必要があります
        int mid = low + xSize;
        mergesort(low, mid - 1); // xと同じ長さ分呼び出す
        mergesort(mid, high); // yと同じ長さ分呼び出す

        // !-- コピーするのはソート後の配列なので、呼び出し後に分割しましょう --!
        // ここから分割
        for (int i = 0; i < xSize; i++) {
            x[i] = a[low + i];
        }

        for (int i = 0; i < ySize; i++) {
            y[i] = a[low + i + xSize];
        }

        // ここからマージ
        System.out.println("マージ開始 >>> low: " + low + " high: " + high);

        // zのサイズを全体ではなくxとyの合計分のみに変更しました
        // xとyからaへ直に書き込んだり、
        // aから直接zを生成し、マージ処理後にzからaに書き戻すような方法もありますが、
        // オフセットが必要ないのでこのほうがわかりやすいかなと思います
        int[] z = new int[len]; // x と y を合計したサイズの一時領域
        int xIndex = 0;
        int yIndex = 0;
        while (xIndex < xSize && yIndex < ySize) {
            if (x[xIndex] < y[yIndex]) {
                z[xIndex + yIndex] = x[xIndex];
                xIndex++;
            } else {
                z[xIndex + yIndex] = y[yIndex];
                yIndex++;
            }
        }

        if (xIndex >= xSize) {
            for (int i = yIndex; i < ySize; i++) {
                z[i + xIndex] = y[i];
            }
        } else {
            for (int i = xIndex; i < xSize; i++) {
                z[i + yIndex] = x[i];
            }
        }

        System.out.println("処理内容: " + intArrayToStr(x) + " + " + intArrayToStr(y) + " => " + intArrayToStr(z));
        // !-- aにlow基準で書き込むようにしました --!
        // z[0]から使っている様子でしたので、こういう意図だと思いましたがどうでしょうか。
        for (int i = 0; i < len; i++) {
            a[i + low] = z[i];
        }
        System.out.println("書き込み結果: " + intArrayToStr(a));
    }

    public void sort() {
        mergesort(0, a.length - 1);

        for (int i = 0; i < n; i++) {
            System.out.println(a[i]);
        }
    }

    /**
     * intの配列をいい感じに文字列化するヘルパーメソッドです
     * 実行中のログ出力の必要がないのであれば削除しても問題ありません
     * @param array 任意のintの配列
     * @return 配列の中身を文字列化したもの
     */
    public static String intArrayToStr(int[] array) {
        String s = "[";
        for (int i = 0; i < array.length; i++) {
            s += array[i];
            if (i != array.length - 1) {
                s += ", ";
            }
        }
        s += "]";
        return s;
    }

    public static void main(String[] args) {
        testMeregeSort ms = new testMeregeSort();
        ms.sort();
    }
}

Comments

[meltySAGAWA]

回答ありがとうございます
コメントやログのおかげで動作がよく理解できました
testMeregeSortもスペルミスを放置してただけなのですぐ直そうと思います
本当にありがとうございました

Answer 2

mergesort は配列 a の low から high までをソートするんですよね。
a の一部を x や y にコピーしても、それらをソートすることはできません。

追記
a や x や y など、複数の配列をソートしたいのなら、
mergesort にそれらを引数で渡す必要があります。
次の修正が必要です。

-    private void mergesort(int low, int high) {
+    private void mergesort(int[] a, int low, int high) {
         int xSize = (high - low + 1) / 2;
-        int ySize = (high + 1) - xSize;
+        int ySize = (high - low + 1) - xSize;
 
-        mergesort(0, xSize - 1);
-        mergesort(0, ySize - 1);
+        mergesort(x, 0, xSize - 1);
+        mergesort(y, 0, ySize - 1);
 
-        for (int i = 0; i < n; i++) {
-            a[i] = z[i];
+        for (int i = 0; i < high - low + 1; i++) {
+            a[low + i] = z[i];

-        mergesort(0, a.length - 1);
+        mergesort(a, 0, a.length - 1);

ySize の求め方を間違っていますし、z から a に戻すところも間違っています。

x や y を使わないで書くなら、

public class Main {
    private int[] a = { 3, 2, 8, 4, 5, 7, 1, 0, 6, 9 };
    private int[] z = new int[a.length];

    private void mergesort(int low, int high) {
		int n = high - low + 1;
		if (n <= 1) return;
		int mid = low + n/2;
		mergesort(low, mid - 1);
		mergesort(mid, high);
		int i, j, k;
		for (i = low; i < mid; i++) z[i] = a[i];
		for (j = high; i <= high; i++) z[j--] = a[i];
		for (k = i = low, j = high; k <= high; k++)
			a[k] = z[i] < z[j] ? z[i++] : z[j--];
    }

    public void sort() {
        mergesort(0, a.length - 1);
        for (int i = 0; i < a.length; i++)
            System.out.print(" " + a[i]);
        System.out.println();
    }

    public static void main(String[] args) {
        new Main().sort();
    }
}

mergesort は再帰的に何度も呼び出されるので、毎回 z を new するのは非効率です。
一度だけ new して、それを使えば問題ありません。

Comments

[meltySAGAWA]

xやyにコピーしたものをzに並び替えて、最終的に
for (int i = 0; i < n; i++) {
a[i] = z[i];
}
のようにしてaに入れなおしたつもりだったんですけどこれじゃダメなんですか？

[meltySAGAWA]

追記ありがとうございます
xやyを使わない方のコードの
for (j = high; i <= high; i++) z[j--] = a[i];
for (k = i = low, j = high; k <= high; k++)
a[k] = z[i] < z[j] ? z[i++] : z[j--];
の部分がよくわかりません
どういう意図でこのようなコードになっているか教えていただけると助かります

[kazuma-s]

a[low]～a[mid-1] と a[mid]～a[high] はどちらもソート済みです。これらを
z[low]～z[mid-1] にはそのままコピー、z[mid]～z[high] には逆順にコピーします。
z[low]～z[high] の両端から一つずつ取り出して小さいほうを a[low] から順に入れていき
マージを完了させます。2つの領域のうち先に無くなった領域の添字は、もう一つの領域の
最大値の添字となるので、残った領域は順番に a に移されます。
マージする2つの領域の終わりをチェックせずにマージが完了します。
具体的なデータで考えても分かりませんか？

[meltySAGAWA]

実際にプログラム通りにソートをしたら流れがわかりました
数日に渡ってコメントをしてくださりありがとうございました