Stack overflow
I am using the following code to do a quick sort on different data sizes. When I increase the data size frm 1000 to 10000 or above I get stack over flow message at line 41.
public static void quickSort(int [] array)
{
q_sort(array, 0, array.length - 1);
}
public static void q_sort(int [] array, int left, int right)
{
int pivot, l_hold, r_hold;
l_hold = left;
r_hold = right;
pivot = array[left];
while (left < right)
{
while ((array[right] >= pivot) && (left < right))
right--;
if (left != right)
{
array[left] = array[right];
left++;
}
while ((array[left] <= pivot) && (left < right))
left++;
if (left != right)
{
array[right] = array[left];
right--;
}
}
array[left] = pivot;
pivot = left;
left = l_hold;
right = r_hold;
if (left < pivot)
q_sort(array, left, pivot-1);
if (right > pivot)
q_sort(array, pivot+1, right); //Line 41
}
[1093 byte] By [
tashi2a] at [2007-9-28 11:23:41]
Here's tashi2's code, formatted a little nicer. Use the [ code ] ... [ / code ] tags (no space within the square brackets though) to surround your code.
public static void quickSort(int[] array) {
q_sort(array, 0, array.length - 1);
}
public static void q_sort(int[] array, int left, int right) {
int pivot, l_hold, r_hold;
l_hold = left;
r_hold = right;
pivot = array[left];
while (left < right) {
while ((array[right] >= pivot) && (left < right))
right--;
if (left != right) {
array[left] = array[right];
left++;
}
while ((array[left] <= pivot) && (left < right))
left++;
if (left != right) {
array[right] = array[left];
right--;
}
}
array[left] = pivot;
pivot = left;
left = l_hold;
right = r_hold;
if (left < pivot)
q_sort(array, left, pivot - 1);
if (right > pivot)
q_sort(array, pivot + 1, right); //Line 41
}
Probably using an iterative algorithm would be the best solution. It is almost guaranteed to be faster in a case like this where the stack/method invocation overhead is so huge.
If you just want to make it work now, you could try increasing the Java thread stack size with the java -Xss<size> option (replace <size> with something like 128k, 1m, etc.). I'm not sure what the default is, so you'll just have to experiment.
Hi,
This is a standard problem with quick sort and it has a versy easy solution. Change the lines
if (left < pivot)
q_sort(array, left, pivot-1);
if (right > pivot)
q_sort(array, pivot+1, right); //Line 41
to somthing along the lines of
if ((pivot - left) < (right - pivot))
{
if (left < pivot)
q_sort(array, left, pivot-1);
if (right > pivot)
q_sort(array, pivot+1, right); //Line 41
}
else
{
if (right > pivot)
q_sort(array, pivot+1, right); //Line 41
if (left < pivot)
q_sort(array, left, pivot-1);
}
This chooses to sort the shortest half first and results in a maximum stack size of about log base 2 n . In your case about 13! Without this, the worst case stack size is 9999!
I prefer 'heap sort'. On average it takes twice as many comparisons as 'quick sort' but but it is always an 'n log n' process.
Roger
