Непоследовательная быстрая сортировка StackOverflowError - PullRequest
Новая
       8

Непоследовательная быстрая сортировка StackOverflowError

1 голос
/ 06 марта 2011

Я работаю над проблемой быстрой сортировки для массивов только целых чисел. Выбор сводки в этой подпрограмме всегда является первым элементом подмассива (как продиктовано проблемой), и в определенный момент я ожидал, что это вызовет StackOverflowError. Странно то, что он не работает для задач размером n = ~ 25000 ~ 404,300, но он работает для n гораздо больше, чем это. Даже когда я заполняю вход массива, он иногда работает при n = 10000, а иногда не работает.

Вот некоторые результаты, которые я получил (время в секундах):

10000: .077

20000: .282

~ 25 000 - ~ 404 300: SOE

405 000 - 3,169

410 000 - 1,632

450 000 - .098

500 000 - .059

5 000 000 - .634

10 000 000 - 1,373

100 000 000 - 18,613

Есть идеи, что могло бы вызвать это? Код ниже.

Заранее спасибо. 

public static void main(String[] args) {
    int arraySize = 1000000;
    int[] a = new int[arraySize];
    Random gen = new Random();

    gen.setSeed(0);
    a[0] = gen.nextInt(arraySize * 10);
    for (int i = 1; i < arraySize; i++) {
        a[i] = a[i - 1] + gen.nextInt(arraySize / 10);
}


private static void quickSort(int[] a, int lo, int hi) {
    if (hi <= lo) return;
    int j = partition(a, lo, hi);
    quickSort(a, lo, j - 1);
    quickSort(a, j + 1, hi);
}

private static int partition(int[] a, int lo, int hi) {
    int i = lo, j = hi + 1;
    int pivot = a[i];
    while (true) {
        while (a[++i] > pivot) if (i == hi) break;
        while (pivot > a[--j]) if (j == lo) break;
        if (i >= j) break;
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    int temp = a[lo];
    a[lo] = a[j];
    a[j] = temp;
    return j;
}

1 Ответ

0 голосов
/ 06 марта 2011

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

Я бы предложил добавить строку метода печати в метод быстрой сортировки, которая выводит его аргументы, чтобы вы могли преобразовать его в график строк, где значение X - это номер вызова (т. Е. Строка 1 - для первого вызова, строка 2 -для следующего вызова и т. д.) и рисуется линия (X, Y1) - (X, Y2), где Y1 - первое значение, а Y2 - второе.

Я предполагаю, что вы очень легкотеперь посмотрим, что идет не так (возможно, уменьшите сумму для сортировки).

...