2

宿題の場合、QuickSortアルゴリズムの実装を作成し、これを使用して、ランダムな順序で10万個の数字を含むリストを並べ替える必要があります。

割り当ての最初の部分では、配列の最初の項目をピボット要素として使用する必要があります。これは確かにソートされたリストを返します。ただし、割り当ての2番目の部分では、最後の項目をピボットとして使用する必要があります。これにより、StackOverflowExceptionが発生します。8レコードの小さなコレクションで試してみると、正しく機能します。私は自分のコードを見てきましたが、どこで間違いを犯しているのかわかりません。どんな助けでも大歓迎です。私のコードは次のとおりです。

public class QuickSort {

    private QuickSortStrategyEnum quickSortStrategy;

    public QuickSort(QuickSortStrategyEnum quickSortStrategy) {

        this.quickSortStrategy = quickSortStrategy;
    }

    public List<Integer> sortIntegerArray(List<Integer> arrayList, int left, int right) {

        if ( left >= right ) {
            return arrayList;
        }

        int i = partition(arrayList, left, right);

        if (i <= right) {

            int pivotNew = partition(arrayList, i, right);
            int pivotIndex = arrayList.indexOf(pivotNew);

            arrayList = sortIntegerArray(arrayList, left , pivotIndex - 1);
            arrayList = sortIntegerArray(arrayList, pivotIndex + 1, right);
        }

        return arrayList;
    }

    private int partition(List<Integer> arrayList, int left, int right) {

        int pivot = getPivot(arrayList, left, right);
        int i = left + 1;

        for (int j = i; j <= right; j++) {

            if (arrayList.get(j) < pivot) {

                Collections.swap(arrayList, j, i);
                i++;
            }
        }

        Collections.swap(arrayList, left, i - 1);
        return i;
    }

    private int getPivot(List<Integer> arrayList, int left, int right) {

        int pivot = 0;

        switch (quickSortStrategy) {

            case FIRST:
            pivot = arrayList.get(left);
            break;

            case LAST:
            pivot = arrayList.get(right);
            break;
        }
        return pivot;
    }

}
4

3 に答える 3

5

ヒント：次の場合はどうなりright == left + 1ますか？

于 2012-04-15T18:12:14.363 に答える
1

David Harknessが指摘した事実に加えて、パーティションロジックに問題があります。これを試してみてください:(DavidHarknessが指摘したものを削除した後）

private int partition(List<Integer> arrayList, int left, int right) {

    int pivot = getPivot(arrayList, left, right);
    int i = left - 1; 

    for (int j = left; j < right; j++) {
        if (arrayList.get(j) <= pivot) {
            i++;
            Collections.swap(arrayList, j, i);
        }
    }

    Collections.swap(arrayList, i+1, right);
    return i+1;
}

ピボットが最後の要素である場合に機能します。最初の要素ではありません。

読んで、紙の作業を理解し、物事をドライランし、擬似コードを書いて、Eclipseに挨拶してください。急いで実装しないでください。

于 2012-04-15T19:25:13.907 に答える
1

これらの2つの線は怪しげに見えます：

int pivotNew = partition(arrayList, i, right);
int pivotIndex = arrayList.indexOf(pivotNew);

何partitionが返されるかを見て、その結果をどのように使用するかと比較してください。

于 2012-04-15T19:06:15.473 に答える