Гибридная сортировка QuickSort + вставка java.lang.StackOverflowError - PullRequest
Новая
       42

Гибридная сортировка QuickSort + вставка java.lang.StackOverflowError

0 голосов
/ 06 февраля 2019

Я пытаюсь рассчитать время работы гибридной быстрой сортировки - вставка сортировки.Однако при представлении массива большего размера (~ 500 тыс. Элементов) я получаю java.lang.StackOverflowError.Могу ли я как-то преодолеть это?Не использовать рекурсию не вариант.

Вот код: 

public class QuickSort2 {

private static void swap(int[] arr, int x, int y){
       int temp = arr[x];
       arr[x] = arr[y];
       arr[y] = temp;
    }

private static int partition(int[] arr, int lo, int hi){
    int pivot = arr[hi];
    int index = lo - 1;
    for(int i = lo; i < hi; i++){
        if(arr[i] < pivot){
            index++;
            swap(arr, index, i);
        }
    }
    swap(arr, index + 1, hi);
    return index + 1;
} 

public static void quickSort(int[] arr, int lo, int hi){
    if(lo < hi && hi-lo > 10){
        int q = partition(arr, lo, hi);
        quickSort(arr,lo,q-1);
        quickSort(arr,q+1,hi);
        }else{
            InsertionSort.insertSort(arr);
        }    
    }
}

, а также тип сортировки: 

public class InsertionSort {

static void insertSort(int[] arr){
    int n = arr.length;
    for (int j = 1; j < n; j++){
        int key = arr[j];
        int i = j-1;
        while ((i >= 0) && (arr[i] > key)){
            arr[i+1] = arr[i];
            i--;
        }
        arr[i+1] = key;
    }         
}

Строки, в которых возникает ошибка: 

quickSort(arr,lo,q-1);
quickSort(arr,q+1,hi);

а также телефонный код: 

public class RunningTime {

public static void main(String[] args) {
    int[] arr = ReadTest.readToArray("int500k");
    int lo = 0;
    int hi = arr.length - 1;

    long startTime = System.currentTimeMillis();
    QuickSort2.quickSort(arr, lo, hi);
    long stopTime = System.currentTimeMillis();
    long elapsedTime = stopTime - startTime;
    System.out.println("Running time: " + elapsedTime);
    System.out.println("Array is sorted: " + isSorted(arr));
}

}

1 Ответ

0 голосов
/ 06 февраля 2019

Вы должны ограничить сортировку вставками, чтобы она работала только с подмножеством массива.

Кроме этого, я не вижу других проблем с вашим кодом.

Является ли файл int500k отсортировано?Если это так, то это наихудший сценарий для быстрой сортировки, что означает, что рекурсия будет иметь глубину в 500 тыс. Уровней.

Чтобы исправить это, вы можете, например, выбрать случайный шарнир вместо arr[hi].

...