Inconsistent Quicksort StackOverflowError

Question

Je travaille sur un problème de tri rapide pour les tableaux de nombres entiers croissants seulement. Le choix du pivot dans cette routine est toujours le premier élément du sous-tableau (tel que dicté par le problème), et à un certain point, je m'attendais à ce que cela provoque une erreur StackOverflowError. Ce qui est bizarre, c'est que ça ne marche pas pour des problèmes de taille n = ~ 25 000 ~ 404 300, mais ça marche pour n beaucoup plus que ça. Même lorsque je lance l'entrée du tableau, il fluctue pour parfois travailler pour n = 10 000 et parfois ne fonctionne pas.

Voici quelques résultats que j'ai eu (le temps est en secondes):

10000: 0,077

20 000: 0,282

~ 25 000 - ~ 404300: SOE

405000 - 3,169

410.000 - 1,632

450.000 - .098

500.000 - .059

5.000.000 - .634

10.000.000 - 1,337

100.000.000 - 18,613

Toutes les idées ce qui cause? Code ci-dessous.

Merci d'avance.

public static void main(String[] args) { 
    int arraySize = 1000000; 
    int[] a = new int[arraySize]; 
    Random gen = new Random(); 

    gen.setSeed(0); 
    a[0] = gen.nextInt(arraySize * 10); 
    for (int i = 1; i < arraySize; i++) { 
     a[i] = a[i - 1] + gen.nextInt(arraySize/10); 
} 


private static void quickSort(int[] a, int lo, int hi) { 
    if (hi <= lo) return; 
    int j = partition(a, lo, hi); 
    quickSort(a, lo, j - 1); 
    quickSort(a, j + 1, hi); 
} 

private static int partition(int[] a, int lo, int hi) { 
    int i = lo, j = hi + 1; 
    int pivot = a[i]; 
    while (true) { 
     while (a[++i] > pivot) if (i == hi) break; 
     while (pivot > a[--j]) if (j == lo) break; 
     if (i >= j) break; 
     int temp = a[i]; 
     a[i] = a[j]; 
     a[j] = temp; 
    } 
    int temp = a[lo]; 
    a[lo] = a[j]; 
    a[j] = temp; 
    return j; 
} 

Answer 1

Je pense que votre méthode de partition est incorrecte (mais je peux me tromper, j'ai qu'effleurer le code), de sorte que les données sont pas correctement résultant partitionné dans de nombreux appels récursifs plus provoquant la pile à déborder. Je suggère que vous ajoutiez une ligne d'impression à la méthode quicksort qui imprime ses arguments afin que vous puissiez le convertir en un graphe de lignes, où la valeur X est le numéro d'appel (la ligne 1 est pour le premier appel, la ligne 2 est pour l'appel suivant, etc.), et une ligne est tracée (X, Y1) - (X, Y2) où Y1 est la première valeur, et Y2 est la seconde. Je pense que vous allez très facilement voir maintenant ce qui ne va pas (peut-être réduire le montant à trier).