1. Member Join Date
Nov 2011
Posts
21
Rep Power
0

## Quicksort

Here is my quicksort method:
Java Code:
```private static void myQuickSort(int []arr, int start, int end)
{
if (start>=end)
{
return;
}
else
{
int i = start-1, j = end+1;
int pivot = arr[start + (end-start)/2];
while (i <= j)
{
do{
i++;
} while(arr[i] < pivot);

do{
j--;
} while(arr[j] > pivot);

if (i<=j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}

if (start < j)
myQuickSort(arr,start, j);
if (i < end)
myQuickSort(arr, i, end);
}

}

}```
I need to test the runningtime of this on randomly generated integer arrays with size 100, 1000, 10000, 100000, and 1000000 however when i get up to very large numbers I get a stack overflow, which is understandable because of the amount of recursion. What I am wondering is if there is a better way I can implement quicksort to not have this error for large arrays, I assume picking a different pivot(rather than the middle) may help. Thanks.  Reply With Quote

2. ## Re: Quicksort

That's why I dislike the quicksort method so much; the pivot selection is critical in this process; the best pivot is the median of the values in the array; finding a median is a nasty process too (google is your friend); if I were you I'd use another sorting method (heap sort?) that doesn't suffer from those recursive steps.

kind regards,

Jos  Reply With Quote

3. Member Join Date
Nov 2011
Posts
21
Rep Power
0

## Re: Quicksort

I wish I could but the project is to compare the runtime of heap sort merge sort and quick sort so I need to do quicksort  Reply With Quote

4. ## Re: Quicksort

Does increasing the maximum stack size help? (see "java -help")

kind regards,

Jos  Reply With Quote

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•