2

私はアルゴリズムのものをレビューしていて、Javaでの単純なクイックソートアルゴリズムの実装で立ち往生しています

import java.util.Arrays;
import java.util.Random;

public class QuickSort {
    int arr[];
    boolean randomPick;
    Random rand = null;

    public QuickSort(int[] inputArray) {
        arr = inputArray;
        randomPick = false;
    }

    public QuickSort(int[] inputArray, boolean random) {
        arr = inputArray;
        if (random) {
            randomPick = true;
            rand = new Random(System.currentTimeMillis());
        }
        else {
            randomPick = false;
        }
    }

    public int[] sort() {
        int start = 0;
        int end = arr.length - 1;
        try {
            _sort(start, end);
        }
        catch (StackOverflowError e) {
            System.out.println("StackOverflow: " + Arrays.toString(arr));
        }
        return arr;
    }

    private void _sort(int start, int end) {
        int i = start;
        int j = end;
        int pivotLoc;
        if (!randomPick) {
            pivotLoc = (j + i) / 2;
        }
        else {
            pivotLoc = rand.nextInt(j - i) + i;
        }
        int pivot = arr[pivotLoc];
        while (i < j) {   // swapping numbers around the pivot
            while (arr[i] < pivot) {
                i++;
            }
            while (arr[j] > pivot) {
                j--;
            }
            if (i < j) {
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                i++;
                j--;
            }
        }
        if (i - start > 1) {
            _sort(start, i);
        }
        if (end - i > 1) {
            _sort(i, end);
        }
    }
}

コードは、ピボットとして中央の数値を選択するか、ピボットとしてランダムに数値を選択し、_sort繰り返し呼び出すことによって配列を並べ替えることができます。最初のケースでは機能しますが、2番目のケースでは失敗します。

状況は次のとおりです。この{3,5,5}のようにサブ配列に到達すると、i == start==0およびj==end==2になります。最後に5と5が入れ替わり、iが2になり、jが1になります（i ++とj--）。その後、何度i - start>1も呼び出さ_sortれ、最終的にスタックオーバーフローエラーが発生するためです。ただし、エラーは最初のケース（固定ピボット）で発生するはずですが、これは今のところ発生していません...

コードの何が問題なのかわかりません。他の人が書いたコードを読むのは楽しいことではないことを私は知っていますが、何か助けはありますか？

4

1 に答える 1

1

再帰条件に小さな間違いを犯しました。startとのend比較はどちらも反対です。istartj

あなたが持っている：

    if (i - start > 1) {
        _sort(start, i);
    }
    if (end - i > 1) {
        _sort(i, end);
    }

する必要があります：

    if (j > start) {
        _sort(start, j);
    }
    if (end > i) {
        _sort(i, end);
    }

そして、あなたiとj比較は等しいことを可能にする必要があります：

   // here ----v
        if (i <= j) {
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
            i++;
            j--;
        }
于 2012-08-22T03:54:30.420 に答える