метод быстрой сортировки arrayOutofBounds Exception - PullRequest
Новая
       11

метод быстрой сортировки arrayOutofBounds Exception

0 голосов
/ 06 декабря 2011

Я пытаюсь получить метод быстрой сортировки для сортировки некоторых или частичных данных.Я думаю, что мой метод разбиения является правильным, и мой рекурсивный вызов быстрой сортировки левых и правых сегментов дает мне массив за пределами исключения, но я не могу понять это.Вот код, который я написал и получаю сообщение об ошибке в 

 private void quickSorter(String[] data, int firstIndex, int numberToSort) {
    if (numberToSort > 1) {
        int pivot = partition(data, firstIndex, numberToSort);
        int right = firstIndex + numberToSort -1;
        if (firstIndex < pivot -1)
        quickSorter(data, firstIndex, pivot -1);
        if (pivot  < right && right <data.length)
        quickSorter(data, pivot  , right);
    }
}
private void swap(String[] data ,int tooBigNdx, int tooSmallNdx) {
    String temp = data[tooBigNdx];
    data[tooBigNdx] = data[tooSmallNdx];
    data[tooSmallNdx] = temp;

}

@Override
public int partition(String[] data, int firstIndex, int numberToPartition) {
    int ndx = firstIndex;
    String pivot = data[ndx];
    int tooBigNdx = ndx;
    int tooSmallNdx = firstIndex + numberToPartition -1;
    while (tooBigNdx < tooSmallNdx) {
    while (tooBigNdx < tooSmallNdx && (data[tooBigNdx].compareTo(pivot) < 0 || data[tooBigNdx].equals(pivot)))
        tooBigNdx++;

    while (tooSmallNdx > ndx && (data[tooSmallNdx].compareTo(pivot) > 0 || data[tooSmallNdx].equals(pivot))) 
        tooSmallNdx--;
    if (tooBigNdx < tooSmallNdx ) {
        swap(data, tooBigNdx,tooSmallNdx);
    tooBigNdx++;
    tooSmallNdx--;
    }
    }
    if (pivot.compareTo(data[tooSmallNdx]) > 0 || pivot.equals(data[tooSmallNdx]) ) {
    swap(data, ndx,tooSmallNdx);
    return tooSmallNdx;
    } else return ndx;


}

РЕДАКТИРОВАТЬ:

Набор данных для тестирования создается случайным образом каждый раз и состоит из 5 буквенных слов.Я всегда получаю исключение arrayoutofBounds, но количество его за пределами меняется в зависимости от набора данных. 

java.lang.ArrayIndexOutOfBoundsException: -1
    at sortcomparison.BasicSorter.partition(BasicSorter.java:62)
    at sortcomparison.BasicSorter.quickSorter(BasicSorter.java:37)
    at sortcomparison.BasicSorter.quickSorter(BasicSorter.java:40)
    at sortcomparison.BasicSorter.quickSorter(BasicSorter.java:40)
    at sortcomparison.BasicSorter.quickSorter(BasicSorter.java:40)
    at sortcomparison.BasicSorter.quickSort(BasicSorter.java:31)
    at sbccunittest.BasicSorterTester.standardSortTest(BasicSorterTester.java:166)
    at sbccunittest.BasicSorterTester.testQuickSort(BasicSorterTester.java:56)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(Unknown Source)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(Unknown Source)
    at java.lang.reflect.Method.invoke(Unknown Source)
    at org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:44)
    at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:15)
    at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:41)
    at org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:20)
    at org.junit.internal.runners.statements.RunBefores.evaluate(RunBefores.java:28)
    at org.junit.internal.runners.statements.RunAfters.evaluate(RunAfters.java:31)
    at org.junit.runners.ParentRunner.runLeaf(ParentRunner.java:263)
    at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:69)
    at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:48)
    at org.junit.runners.ParentRunner$3.run(ParentRunner.java:231)
    at org.junit.runners.ParentRunner$1.schedule(ParentRunner.java:60)
    at org.junit.runners.ParentRunner.runChildren(ParentRunner.java:229)
    at org.junit.runners.ParentRunner.access$000(ParentRunner.java:50)
    at org.junit.runners.ParentRunner$2.evaluate(ParentRunner.java:222)
    at org.junit.runners.ParentRunner.run(ParentRunner.java:292)
    at org.eclipse.jdt.internal.junit4.runner.JUnit4TestReference.run(JUnit4TestReference.java:50)
    at org.eclipse.jdt.internal.junit.runner.TestExecution.run(TestExecution.java:38)
    at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.runTests(RemoteTestRunner.java:467)
    at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.runTests(RemoteTestRunner.java:683)
    at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.run(RemoteTestRunner.java:390)
    at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.main(RemoteTestRunner.java:197)

Ответы [ 2 ]

1 голос
/ 06 декабря 2011

Я думаю, что ваша проблема в приоритете оператора в цикле while между && , ||

Решить с круглыми скобками.

Для второй проблемы, я думаю, в третьей, пока заменить: 

while (tooSmallNdx > ndx && (data[tooSmallNdx].compareTo(pivot) > 0 || data[tooSmallNdx].equals(pivot)))

С: 

while (tooSmallNdx > ndx && data[tooSmallNdx].compareTo(pivot) > 0)
1 голос
/ 06 декабря 2011

Не должно 

 int right = firstIndex + numberToSort -1;

быть 

 int right = firstIndex + numberToSort - 1 - pivot;

Помните, что 2-й параметр - это не номер индекса, а счет.

Вы можете изменить его на порядковый номер (который, я думаю, будет более интуитивно понятным).

...