Переполнение стека QuickSort на большой вход

Реализация QuickSort вызывает ошибку StackOverflow, если я предоставляю массив с обратным сортировкой. Он работает нормально около 1000 элементов, но для 10000+ я получаю ошибку StackOverflow. Если я получу ошибку, глубина рекурсии составит около 9000. Я знаю, что мой алгоритм всегда выбирает последний элемент подмассива в качестве точки опоры, что не является оптимальным, но я бы не изменил его, потому что я хочу заставить его работать так. Вот код:Переполнение стека QuickSort на большой вход

private int partition(int[] numbers, int begin, int end) { 
    int pivot = numbers[end]; 
    int partitionIndex = begin; 
    for (int i = begin; i < end; ++i) { 
     comparisonCounter++; 
     if (numbers[i] <= pivot) { 
      if (i != partitionIndex) { 
       swapCounter++; 
       int temp = numbers[i]; 
       numbers[i] = numbers[partitionIndex]; 
       numbers[partitionIndex] = temp; 
      } 
      partitionIndex++; 
     } 
    } 
    if (partitionIndex != end) { 
     swapCounter++; 
     int temp = numbers[partitionIndex]; 
     numbers[partitionIndex] = numbers[end]; 
     numbers[end] = temp; 
    } 
    return partitionIndex; 
} 

private void quickSort(int[] numbers, int begin, int end) { 
    if (begin < end) { 
     int partitionIndex = partition(numbers, begin, end); 
     quickSort(numbers, begin, partitionIndex - 1); 
     quickSort(numbers, partitionIndex + 1, end); 
    } 
}

Есть ли что-то не так с моей реализацией? Как я могу это исправить? Спасибо!

источник

2015-05-22 marfoldi

Если список представляет собой массив с обратным сортировкой, и вы всегда выбираете последний элемент в качестве точки опоры, кажется, что вы получите глубину рекурсии примерно длины списка, поскольку один из ваши разделы будут пустыми. –

Из [Википедии] (http://en.wikipedia.org/wiki/Quicksort) «самый левый элемент раздела часто выбирается как свод ... Это вызывает худшее поведение на уже отсортированных массивах. " Поскольку вы используете последнее как свод и реверсивный массив, это худшее поведение. Таким образом, у вас действительно нет хорошей реализации, так как у вас будет O (n^2). Вместо этого вы должны использовать средний или другой элемент. – mbomb007

Спасибо вам обоим. Да, я проверил на худший случай, затем я получил ошибку. Теперь я могу переписать его на итеративный подход. – marfoldi

В коде нет ничего плохого, но имейте в виду, что это рекурсивная функция, и большинство языков имеет стеки с ограниченной глубиной, к которым вы обязательно привязаны, если у вас есть достаточно большой вход. Для Java, см:

Что вы можете сделать, это превратить ваш метод, с рекурсивным к итеративному подходу. Есть несколько способов сделать это. Я просто нашел пару примеров онлайн:

источник

2015-05-22 21:43:33

Большое вам спасибо за ваш быстрый ответ! Как вы видите, моя реализация в порядке? Мне просто нужно иметь дело с стеком java или переписать его на итеративный подход? – marfoldi

@marfoldi не заходил подробно в ваш код, но с быстрым взглядом он выглядел нормально. Опять же, ошибка, о которой вы сообщаете, является общей ошибкой во всех рекурсивных вызовах. Если вы хотите просто избавиться от него, попробуйте настроить память, выделенную для стека.Если вы хотите более долгосрочное решение или хотите попрактиковаться в своем кодировании, продолжайте и попытайтесь сделать свое решение итеративным. Однако для любой сортировки общего назначения встроенные методы сортировки Java обеспечивают наиболее разумную и стабильную оптимизацию. –

Есть несколько способов, чтобы уменьшить размер стека в Quicksort.

Вы можете помещать большую секцию в стек каждый раз, оставляя ее там, в то время как меньший раздел сортируется первым. Это удерживает слишком много небольших разделов от засорения стека одновременно.
Вы можете использовать другой метод, например сортировку вставки, для сортировки небольших разделов, а не Quicksort. Опять же, это содержит много небольших разделов со стека. Вы можете экспериментировать, но что-то в области 15-20 элементов обычно считается «маленьким» разделом.

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

источник

2015-05-22 22:14:52 rossum

Переполнение стека QuickSort на большой вход

ответ

Смежные вопросы