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;
}
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;