Fast stackoverflow sorting for large arrays

Question

So, I was instructed to implement a quick sorting algorithm and compare the runtime for arrays of sizes 500, 3500 and 80000. Arrays are filled with random numbers:

(integer) Math.random () * 1,000,000

My quicksort algorithm works for arrays of sizes 500 and 3500, but I always get a stackoverflow error when trying to sort a third array of size 80000. My other sorting algorithms do a great job with these arrays.

My quicksort method:

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

My separation method:

 private static int partition(int[] a, int p, int r) { int x = a[p]; int i = p; int j = r; while (true) { do { i++; } while (i < r && a[i] < x); do { j--; } while (j > p && a[j] > x); if (i < j) { int tmp = a[i]; a[i++] = a[j]; a[j--] = tmp; } else { return j; } } } 

I read that I can just change the stack size in the parameters of the virtual machine (not sure how to do this), but it just ignores the problem in my algorithm. What causes the error? Thanks!

EDIT: Here is my driver class:

 public class Driver { public static void main(String[] args) { int[] array1 = new int[500]; int[] array2 = new int[3500]; int[] array3 = new int[80000]; for(int i=0; i<array1.length; i++) { array1[i]=(int)(Math.random()*100000); } for(int i=0; i<array2.length; i++) { array2[i]=(int)(Math.random()*100000); } for(int i=0; i<array3.length; i++) { array3[i]=(int)(Math.random()*100000); } //~~~~~~~~~~~INSERTION~~~~~~~~~~~~~~~// System.out.println("INSERTION SORT:\n_______________"); System.out.println("500 Elements: "+SortTimes.runTime(SortTimes.INSERTION,array1)+" ms"); System.out.println("3500 Elements: "+SortTimes.runTime(SortTimes.INSERTION,array2)+" ms"); System.out.println("80000 Elements: "+SortTimes.runTime(SortTimes.INSERTION,array3)+" ms"); //~~~~~~~~~~~BUBBLE~~~~~~~~~~~~~~~// System.out.println("\n\nBUBBLE SORT:\n_______________"); System.out.println("500 Elements: "+SortTimes.runTime(SortTimes.BUBBLE,array1)+" ms"); System.out.println("3500 Elements: "+SortTimes.runTime(SortTimes.BUBBLE,array2)+" ms"); System.out.println("80000 Elements: "+SortTimes.runTime(SortTimes.BUBBLE,array3)+" ms"); //~~~~~~~~~~~MERGE~~~~~~~~~~~~~~~// System.out.println("\n\nMERGE SORT:\n_______________"); System.out.println("500 Elements: "+SortTimes.runTime(SortTimes.MERGE,array1)+" ms"); System.out.println("3500 Elements: "+SortTimes.runTime(SortTimes.MERGE,array2)+" ms"); System.out.println("80000 Elements: "+SortTimes.runTime(SortTimes.MERGE,array3)+" ms"); //~~~~~~~~~~~QUICK~~~~~~~~~~~~~~~// System.out.println("\n\nQUICK SORT:\n_______________"); System.out.println("500 Elements: "+SortTimes.runTime(SortTimes.QUICK,array1)+" ms"); System.out.println("3500 Elements: "+SortTimes.runTime(SortTimes.QUICK,array2)+" ms"); System.out.println("80000 Elements: "+SortTimes.runTime(SortTimes.QUICK,array3)+" ms"); } 

}

Here is my SortTimes class:

 public class SortTimes { public final static int MERGE = 1; public final static int QUICK = 2; public final static int BUBBLE = 3; public final static int INSERTION = 4; public static double runTime(int sortMethod, int[] array) { double startTime; double endTime; switch(sortMethod) { case MERGE: startTime = System.currentTimeMillis(); lab12.mergeSort(array); endTime = System.currentTimeMillis(); break; case QUICK: startTime = System.currentTimeMillis(); lab12.quickSort(array, 0, array.length-1); endTime = System.currentTimeMillis(); break; case BUBBLE: startTime = System.currentTimeMillis(); lab12.bubbleSort(array); endTime = System.currentTimeMillis(); break; case INSERTION: startTime = System.currentTimeMillis(); lab12.insertionSort(array); endTime = System.currentTimeMillis(); break; default: startTime = -1; endTime = 0; break; } return endTime-startTime; } 

}

Answer 1

If quickSort () still uses pivot x = a [p] rather than x = a [(p + r) / 2], then if the data is already sorted, quickSort () is likely to get a stack overflow (this will also happen if there will be many duplicates). Is there any chance that you are using quickSort () for data that has already been sorted by a previous sort?

Answer 2

Here is your quick sort:

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

It works, but in the worst case, it uses O (rp) stack space. This is too much for real implementations. The fix is ​​easy, however - you recurse to a smaller section, and then loop into a large section. Recursion on a smaller section means that you are only using O (log (rp)) stack space, regardless of whether:

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

EDIT: so, thus, implementing real quicksort ensures that in the worst case there are no stack overflows ...

BUT In the worst case, it never happens when you initialize an array with random numbers.

You said that you initialized the array with (int)Math.random()*1000000 . Check out the priority tables! The cast occurs before multiplication, so it is always 0, so you get worse behavior. You want (int)(Math.random()*1000000) .

EDIT: Your split function is also broken. It will always leave [p] at position p, even if it is the largest element in the array

Answer 3

You are reporting a stack overflow with an array of 80,000 items. Your code sorts an array of 80 million elements on my laptop in 10 seconds without problems. I see no errors ...

If you have random input, you should expect that the maximum recursion depth will be somewhere in the log step ₂ (n), which is less than 30 for n = 80,000,000. Quicksort wikipedia article contains a more detailed analysis. Basically, unless you hit a really pathological case (where all of your anchor points are terrible), you shouldn't expect to see so much recursion that the stack overflows.

However, I had to fix a couple of logical errors in the code to actually get the actual look (I did not get a fully sorted result).

---

Fix random number generation

(int)Math.random()*1000000 will always return zero . You need to add another set of brackets for truncation after multiplication: (int)(Math.random()*1000000) .

Correct section logic

Your splitting method is almost consistent with the logic of the Hoare circuit. However, you seem to have a few errors. If you compare your code with the code from Wikipedia, you will see several differences.

• You set i=p and j=r , but should be i=p-1 and j=r+1 .
• You must remove the increment and decrement in your swap logic, so a[i++] should only be a[i] , and a[j--] should be a[j] .

---

Here is the code I used to check:

 public class QSort { private static int partition(int[] a, int p, int r) { int x = a[p]; int i = p-1; int j = r+1; while (true) { while (++i < r && a[i] < x); while (--j > p && a[j] > x); if (i < j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } else { return j; } } } public static void quickSort(int[] a, int p, int r) { if(p<r) { int q=partition(a,p,r); quickSort(a,p,q); quickSort(a,q+1,r); } } public static void main(String args[]) { int n = Integer.valueOf(args[0]); int[] xs = new int[n]; for (int i=0; i<n; i++) { xs[i] = (int)(Math.random()*1000000); } quickSort(xs, 0, xs.length-1); for (int i=0; i<n-1; i++) { if (xs[i] > xs[i+1]) { System.out.println("ERROR"); System.exit(-1); } } System.out.println("SORTED"); } } 

Answer 4

Since this program is recursive and java is not efficient in terms of memory in recursions, which goes a little deep, try increasing the amount of memory allocated for your program using the IDE.

Since you are using Intellij, try increasing the memory capacity as follows.

Additional information: https://www.jetbrains.com/idea/help/run-debug-configuration-application.html

Answer 5

The recursive QuickSort algorithm on large arrays raises a StackOverflow error.

Try the non-recursive link from this link . The following Java code is converted from c source code, hope this helps.

 static final int MAX_LEVELS = 1000; public static boolean quickSort(int[] arr, int elements) { int i=0,L,R,pivot; int[] beg = new int[MAX_LEVELS], end = new int[MAX_LEVELS]; beg[0]=0; end[0]=elements; while(i>=0) { L=beg[i]; R=end[i]-1; if(L<R) { pivot=arr[L]; if(i==MAX_LEVELS-1) return false; while(L<R) { while(arr[R]>=pivot&&L<R) R--; if(L<R) arr[L++]=arr[R]; while(arr[L]<=pivot&&L<R) L++; if(L<R) arr[R--]=arr[L]; } arr[L]=pivot; beg[i+1]=L+1; end[i+1]=end[i]; end[i++]=L; } else { i--; } } return true; } // an example public static void main(String[] args) { // construct the integer array int[] arr = new int[80000]; for(int i=0;i<arr.length;i++) { arr[i]=(int)Math.random()*100000; } // sort the array quickSort(arr, arr.length); } 

It saves time and protection against stackoverflow.

Answer 6

Are your arrays entered sorted? Have you sent a sorted array for quick sorting?

 public class quickSortTest { public static void main(String[] args) { int max = 800000; int[] array = new int[max]; for (int i = 0; i < max; ++i) { array[i] = (int) Math.random() * 1000000; } long start = System.currentTimeMillis(); quickSort(array, 0, max - 1); System.out.println("time:"+(System.currentTimeMillis()-start)); System.out.println(testSortResult(array)); } public static boolean testSortResult(int[] array){ for(int i=1;i<array.length;++i){ if(array[i]<array[i-1]){ return false; } } return true; } public static void quickSort(int[] a, int p, int r) { if (p < r) { int q = partition(a, p, r); quickSort(a, p, q); quickSort(a, q + 1, r); } } private static int partition(int[] a, int p, int r) { int x = a[p]; int i = p; int j = r; while (true) { do { i++; } while (i < r && a[i] < x); do { j--; } while (j > p && a[j] > x); if (i < j) { int tmp = a[i]; a[i++] = a[j]; a[j--] = tmp; } else { return j; } } } } 

I am testing your code, it is fine even when the length of the array is 800000.