Внедрение QuickSort для использования Вставка Сортировка для коротких подмассивов

Question

Я пытаюсь реализовать quickSort, который использует сортировку Insertion для подмассивов, которые короче определенной длины. Я написал этот код, но проблема в том, что он работает для записей до 400 000 целых чисел, но мне нужно заставить его работать для 5000 000 целых массивов. Это дает мне трудное время, чтобы выяснить, почему я получаю ошибку StackOverflow для этого.

public int[] quickSort2(int[] arrayOfIntegers, int startIndex, int endIndex) { 
    if (startIndex < endIndex) { 
     if (endIndex - startIndex < INSERTION_SORT_THRESHOLD) { 
      InsertionSort(arrayOfIntegers, startIndex, endIndex); 
     } else { 
      int pivotIndex = partition2(arrayOfIntegers, startIndex, endIndex); 
      quickSort2(arrayOfIntegers, startIndex, pivotIndex - 1); 
      quickSort2(arrayOfIntegers, pivotIndex + 1, endIndex); 
     } 
    } 
    return arrayOfIntegers; 
} 

вставки Сортировать выглядит следующим образом:

public int[] InsertionSort(int[] arrayOfNumbers, int startIndex, int endIndex) { 
    for (int i = startIndex + 1; i <= endIndex; i++) { 
     int key = arrayOfNumbers[i]; 
     int pointer = i - 1; 
     while (pointer >= startIndex && arrayOfNumbers[pointer] > key) { 
      arrayOfNumbers[pointer + 1] = arrayOfNumbers[pointer]; 
      pointer -= 1; 
     } 
     arrayOfNumbers[pointer + 1] = key; 
    } 
    return arrayOfNumbers; 
} 

QuickSort раздел:

private int partition2(int[] arrayOfIntegers, int start, int end) { 
    int pivot = arrayOfIntegers[end]; 
    int pointer = start - 1; 
    for (int i = start; i <= end - 1; i++) { 
     if (arrayOfIntegers[i] <= pivot) { 
      pointer += 1; 
      int temporaryStorage = arrayOfIntegers[i]; 
      arrayOfIntegers[i] = arrayOfIntegers[pointer]; 
      arrayOfIntegers[pointer] = temporaryStorage; 
     } 
    } 
    arrayOfIntegers[end] = arrayOfIntegers[pointer + 1]; 
    arrayOfIntegers[pointer + 1] = pivot; 
    return (pointer + 1); 
} 

Кроме того, когда я код для запуска QuickSort на массив размера 5000.000 целых чисел и с помощью подмассива из длина 3, 6, 9 и т. д., чтобы отсортировать весь массив, это не дает мне ошибку «StackOverflow». Может кто-нибудь помочь

Answer 1

Вы правильно получаете Stackoverflow, потому что ваша реализация использует рекурсию. Вы вызываете quickSort2 из своего метода quickSort2, который увеличит стек при каждом вызове. Так как стек не может расти бесконечно, вы получаете Stackoverflow.

Если вы увеличите свой порог до 3, 6, 9 (и так далее), вы получите значительно меньше рекурсий (звонки quickSort2). Вот почему вы не получаете Stackoverflow в этом случае. Но это только вопрос размера вашего массива. Если он достаточно велик, вы все равно получите Stackoverflow.

Решение заключается в устранении рекурсии из вашего кода. Устранение рекурсии не только предотвратит Stackoverflow, но и увеличит скорость вашего кода, поскольку рекурсия намного медленнее по сравнению с итерациями (на Java).

Подробнее см., Например, http://www.geeksforgeeks.org/iterative-quick-sort/ или Google iterative quicksort.