Stackoverflow when arrays get too big

Question

I am trying to implement a version of quicksort with test classes that takes float. When i try to generate arrays with the size of 10⁸ I get stack overflow when running my testclass.

I tried with array size of 10⁷ and that worked fine

In my testclass i generate two arrays that are exactly the same, one is sorted with my algoritm and one is sorted with javas Arrays.sort().

Here is how my testclass looks like.

package Quicksort;

import org.junit.Before;
import org.junit.Test;
import java.util.Arrays;
import static org.junit.Assert.*;

public class QuickSortTest {

private static float[] quickSort, javaSort;
private final static int SIZE = (int) 1e7;

@Before
public void init(){
    System.gc();
    quickSort = new float[SIZE];
    javaSort = new float[SIZE];
    for(int i = 0; i < SIZE; i++){
        int temp = (int) (Math.random() * 1000) + 1;
        quickSort[i] = temp;
    }

    javaSort = quickSort;
}

@Test
public void testQuickSort(){
    QuickSort.sort(quickSort);
    Arrays.sort(javaSort, 0, SIZE);
    assertArrayEquals(quickSort, javaSort, .0f);
}

}

Quicksort implementation:

private static void quickSort(float[] table, int first, int last){
        if(first < last){
            int pivotIndex = partition(table, first, last);
            quickSort(table, first, pivotIndex - 1);
            quickSort(table, pivotIndex + 1, last);
        }
    }

public static int partition(float[] table, int first, int last){
        sort3(table, first, last);
        swap(table, first, (first + last) / 2);
        float pivot = table[first];
        int up = first;
        int down = last;
        do{
            while((up < last) && table[up] <= pivot){
                up++;
            }
            while(table[down] > pivot){
                down--;
            }
            if(up < down){
                swap(table, up, down);
            }
        }while(up < down);
        swap(table, first, down);
        return down;
    }

I like your test assertion: in the test preparation you make sure that `javaSort` and `quickSort` reference the same array - therefore `assertArrayEquals(quickSort, javaSort, .0f);` will always succeed — Thomas Kläger, Jan 24 '18 at 14:01
The problem is that your input data is a bad fit for the quick sort algorithm. The way you prepare your input data (`int temp = (int) (Math.random() * 1000) + 1;`) means that your input contains only the values from 1 to 1000, but these values many times (each one about 1e8/1000 = 100'000 times). This is one of the worst scenarios for the quick sort algorithm (see https://en.wikipedia.org/wiki/Quicksort#Repeated_elements) — Thomas Kläger, Jan 24 '18 at 19:04

Mohamed Taher Alrefaie · Accepted Answer · 2018-01-24T14:02:09.203

A StackOverflowError is usually caused by a bad recursive call. Your QuickSort class has a recursive functions that keeps calling itself beyond the stack size when you pass in an array of length 10^8.

A way to solve this is to switch your implementation to iterative approach rather than a recursive one.

based on your last update, it seems like partition() method calls itself recursively beyond the limitations of the Java heap space.

In this post, you can find an iterative partition() implementation. It's slightly more complicated but will be able to handle the size of your array.

import java.util.Arrays;
import java.util.Random;

// Java program for implementation of QuickSort
class QuickSort
{
    public static void main(String[] args) {
        QuickSort sort=new QuickSort();
        int[] randomArray = createRandomArray((int) Math.pow(2, 20));

        sort.qSort(randomArray);
        //System.out.println(Arrays.toString(randomArray));
    }

    private void qSort(int[] arr) {
        this.qSort(arr, 0, arr.length-1);
    }

    /* This function takes last element as pivot,
       places the pivot element at its correct
       position in sorted array, and places all
       smaller (smaller than pivot) to left of
       pivot and all greater elements to right
       of pivot */
    int partition(int arr[], int low, int high)
    {
        int pivot = arr[high];
        int i = (low-1); // index of smaller element
        for (int j=low; j<=high-1; j++)
        {
            // If current element is smaller than or
            // equal to pivot
            if (arr[j] <= pivot)
            {
                i++;

                // swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // swap arr[i+1] and arr[high] (or pivot)
        int temp = arr[i+1];
        arr[i+1] = arr[high];
        arr[high] = temp;

        return i+1;
    }

    /* The main function that implements QuickSort()
      arr[] --> Array to be sorted,
      low  --> Starting index,
      high  --> Ending index */
    void qSort(int arr[], int low, int high)
    {
        if (low < high)
        {
            /* pi is partitioning index, arr[pi] is
              now at right place */
            int pi = partition(arr, low, high);

            // Recursively sort elements before
            // partition and after partition
            qSort(arr, low, pi-1);
            qSort(arr, pi+1, high);
        }
    }


    private static int[] createRandomArray(int size){
        Random randNumGenerator = new Random();
        int[] arr = new int[size];
        for (int i=0; i<arr.length; i++)
        {
            arr[i] = (randNumGenerator.nextInt(100)+1);
        }
        return arr;
    }
}

It seems like you want to keep the following in your mind;

maximum heap size (changeable at JVM initiation),
maximum stack size (changeable at JVM initiation) and,
maximum array size in Java (mostly 2^31, some new JVMs limits it to 2^31-5).

Stackoverflow when arrays get too big

1 Answers1