Quicksort -Stack -Überlauf mit großen Arraygrößen und wenigen unterschiedlichen Werten ⇐ Java

[Anonymous]

Ich arbeite an der Implementierung eines Quicksort -Algorithmus, an dem ich mit Array -Größen bis zu 100.000 gut arbeiten muss. Sobald ich versuche, mit einer Größe von 1.000.000 zu sortieren, erhalte ich einen Stapelüberlauffehler (der mein bestes Verständnis aufgrund der rekursiven Funktionalität meines Algorithmus entspricht).

Ich weiß, dass diese Frage gestellt wurde Hier zuvor, aber keine dieser Antworten hat mir überhaupt geholfen. Ich habe meinen Code ausgiebig durchgesehen und ihn sogar von einem Java -Lehrbuch modelliert, um zu überprüfen, noch keine Lösung.

Ich habe hier mindestens eine Stunde lang versucht , und ich las, dass der Anrufstack je nach System bis zu 8 MB aufnehmen könnte. Ich frage mich, ob entweder: < /p>

Mein Algorithmus ist falsch < /li>
1.000.000 Elemente sind zu groß, um für eine Quicksort verwendet zu werden (Mit diesem Compiler). < /li>
< /ul>
Bearbeiten: An alle Interessierten: Ich habe festgestellt, dass mein Zufallsintervall von 1-9 auf 1-N erhöht wird ( n ist die Größe der Sortierung der Sequenz, z. B. 1-1000000), meine Quicksort lief extrem schneller und hatte natürlich keine Überlaufprobleme.
i Ich werde jetzt meinen Code mit dem Fahrer einreichen, und hoffentlich kann mir jemand schnell zeigen, wo ich falsch gelaufen bin. < /p>

Code: Select all

public class QuickSort {

public static void main(String[] args) {

//JUST TO TEST THAT IT WORKS
int[]A = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; //worst case

quickSort(A, 0, A.length-1);

//print the array
for (int a :A)
System.out.print(a+" ");
System.out.println();

}

/**
* Quicksort algorithm, O(n log n) best and average case, O(n^2) worst case
* @param S sequence to sort
* @param a the lower bound of sequence
* @param b upper bound of sequence
*/
public static void quickSort(int[]S, int a, int b) {
if (a >= b)
return;
int p = S[b]; //setting pivot to the last element in sequence
int l = a;
int r = b - 1;
int temp;

while (l