0

ArrayList に QuickSort アルゴリズムを実装しようとしています。しかし、私は

Exception in thread "main" java.lang.StackOverflowError
    at sorting.QuickSort.quickSort(QuickSort.java:25)
    at sorting.QuickSort.quickSort(QuickSort.java:36)
    at sorting.QuickSort.quickSort(QuickSort.java:36)
    at sorting.QuickSort.quickSort(QuickSort.java:36)
    at sorting.QuickSort.quickSort(QuickSort.java:36)
    ...

なぜオーバーフローがあるのか​​ わかりません。以下は私の実装です：

public static void quickSort(ArrayList<Integer> al, int fromIdx, int toIdx) {
    int pivot, pivotIdx;

    if (fromIdx < toIdx) {
        pivot = al.get(fromIdx);
        pivotIdx = fromIdx;

        for (int i = 0; i != (fromIdx + 1); i++) {
            if (al.get(i) <= pivot) {
                pivotIdx += 1;
                swap(al, pivotIdx, i);
            }
        }

        swap(al, fromIdx, pivotIdx);
        quickSort(al, fromIdx, pivotIdx - 1);
        quickSort(al, pivotIdx + 1, toIdx);
    }
}

public static void swap(ArrayList<Integer> al, int xIdx, int yIdx) {
    Integer temp = al.get(xIdx);
    al.set(xIdx, al.get(yIdx));
    al.set(yIdx, temp);
}
4

1 に答える 1

0

fromIdx配列のチャンクを からまでソートしようとしている場合toIdx、要素 0 がそのチャンク内にない限り、要素 0 を見ないでください。しかし、あなたの実装はそうです。

途中のインデックス作成のトリックもちょっと..奇妙です。アルゴリズムをトレースできるように、配列用に小さな紙を切り取り、追跡情報を紙に書き出すという演習を行うことを強くお勧めします。物理的にやっても意味がないと思うなら、コンピュータでも意味がありません。物理的な紙片を持つという行為はばかげているように思えるかもしれませんが、自分が何をしているかを正確に視覚化するのに非常に役立ちます。(コードが実際に何を行っているかをより正確に視覚化できるほど、コードが何か間違ったことを行っているかどうかを判断できる可能性が高くなります。)

于 2013-10-27T05:46:02.427 に答える