Почему возникает ошибка переполнения стека?

Question

Вот код .. Мне нужно отсортировать уже отсортированный массив и рассчитать время его выполнения ... для quicksort это n^2, потому что это худший случай. но для больших входных данных, скажем, 7500, это дает мне ошибку переполнения: S, что я могу сделать, чтобы вычислить время работы?

public class Provo { 

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

    public static int HoarePartition(int m, int d, int[] a) { 
     int pivot = a[m]; 
     int i = m + 1; 
     int j = d; 

     while (i < j) { 
      while (a[i] < pivot) { 
       i = i + 1; 
      } 

      while (a[j] > pivot) { 
       j = j - 1; 
      } 

      if (i < j) 
       swap(a, i, j); 
     } 
     swap(a, m, j); 

     return j; 
    } 

    public static void quicksort(int m, int d, int[] a) { 
     if (m < d) { 
      int s = HoarePartition(m, d, a); 
      quicksort(m, s - 1, a); 
      quicksort(s + 1, d, a); 
     } 
    } 
} 

и здесь является основным классом

import javax.swing.*; 

public class ascending { 


public static void main(String[] args){ 
    String input=JOptionPane.showInputDialog("Shkruani nr e te dhenave"); 
    int size=new Integer(input).intValue(); 

    int[] r= new int[size]; 
    int[] p = new int[size]; 
    int majtas=0; 
    int djathtas=size; 

    for(int i=majtas;i<djathtas;i++) 
    {r[i]=i;} 
    for(int i=majtas;i<djathtas;i++) 
    {p[i]=r[i];} 

    long average; 
    int n=100; 
    long result=0; 
    for(int j=1;j<=n;j++) 
    { 
     long startTime = System.nanoTime(); 
     Provo.quicksort(majtas,djathtas-1,p); 
    long endTime = System.nanoTime(); 
    result = result+(endTime-startTime); 
    long a = endTime-startTime; 
     System.out.println(j+": " +a); 
     for(int i=majtas;i<djathtas;i++) 
     {p[i]=r[i];} 
    } 
    average=result/n; 
    System.out.println("Koha e ekzekutimit te insertion sort eshte " + average + " nanosekonda "); 
} 

}

Answer 1

Изменение int djathtas = size - 1; в int djathtas = size; и change quicksort(majtas, djathtas, p); к quicksort(majtas, djathtas - 1, p);

В противном случае это не выделение 10 цифр, только 9.

Похоже, вы просто используете слишком большой номер. Ваша программа может работать правильно и генерировать ошибку переполнения стека. Вы можете попробовать реализовать другую версию quicksort, которая не полагается на стек или что-то в этом роде.

Кроме этого, я не уверен, зачем вам нужен такой большой вход.

Answer 2

Ну, если вы застряли, вы можете, возможно, Ищут итерационного сортировки в Интернете, чтобы получить некоторую помощь.

Я нашел это article. Он посвящен C#, но перевод его на Java не должен быть большой проблемой.