Quicksort (Java) вызывает StackOverFlow на array.length> 60k

Question

Мой код работает должным образом (насколько мне известно) до тех пор, пока размер моего входного массива (a.length) не составит около 62 000, и тогда я последовательно получу StackOverFlowError.Ранее я использовал 2 рекурсивных вызова для quicksort (меньше и больше, чем пивот q), а затем переключился на хвостовую рекурсию.Как вы можете видеть, я выбираю пивот в качестве значения в конце массива.Я знаю, что это не лучший способ выбора точки, но я все еще не должен видеть StackOverFlowError с таким маленьким размером массива, верно?Что может быть причиной этого?Заранее спасибо!Вот мой код:

    public static void quicksort(int[] a, int p, int r)
    {
        int q;
        while (p < r)
        {
            q = partition(a, p, r);
            quicksort(a, p, q - 1);
            p = q + 1;
        }
    }

    public static int partition(int[] a, int p, int r)
    {
        int j = p - 1;
        int x = a[r];
        for (int i = p; i < r; i++)
        {
            if (a[i] <= x)
            {
                j++;
                swap(a, i, j);
            }
        }
        j++;
        swap(a, j, r);
        return j;
    }

    private static void swap(int[] a, int i, int j)
    {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

Answer 1

В наихудшем случае (отсортированный порядок) выполняется быстрая сортировка Θ (n ^ 2). Раздел всегда размещает один элемент на одной стороне раздела (Cormen et al.).Путем рандомизации сортировки (выбора случайного центра) никакой конкретный ввод не вызывает его наихудшего поведения .

import java.util.Random;

public class Quicksort
{
     private static Random rand = new Random();

     public static void quicksort(int[] arr, int left, int right)
     {
          if (left < right)
          {
               int pivot = randomizedPartition(arr, left, right);
               quicksort(arr, left, pivot);
               quicksort(arr, pivot + 1, right);
          }
     }

     private static int randomizedPartition(int[] arr, int left, int right)
     {
          int swapIndex = left + rand.nextInt(right - left) + 1;
          swap(arr, left, swapIndex);
          return partition(arr, left, right);
     }

     private static int partition(int[] arr, int left, int right)
     {
          int pivot = arr[left];
          int i = left - 1;
          int j = right + 1;
          while (true)
          {
               do
                    j--;
               while (arr[j] > pivot);

               do
                    i++;
               while (arr[i] < pivot);

               if (i < j)
                    swap(arr, i, j);
               else
                    return j;
          }
     }

     private static void swap(int[] arr, int i, int j)
     {
          int tmp = arr[i];
          arr[i] = arr[j];
          arr[j] = tmp;
     }

     // Sort 100k elements that are in reversed sorted order
     public static void main(String[] args)
     {
          int arr[] = new int[100000];
          for (int i = 0; i < arr.length; i++)
               arr[i] = arr.length - i;

          System.out.println("First 20 elements");
          System.out.print("Before sort: ");
          for (int i = 0; i < 20; i++)
               System.out.print(arr[i] + " ");
          System.out.println();

          quicksort(arr, 0, arr.length - 1);
          System.out.print("After sort: ");
          for (int i = 0; i < 20; i++)
               System.out.print(arr[i] + " ");
          System.out.println();
     }

}

Answer 2

При правильном вводе ваша реализация будет повторяться один раз для каждого элемента массива.60 000 рекурсивных вызовов может быть достаточно для переполнения стека в Java в конфигурации по умолчанию.