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.

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

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

4. ## Re: Quicksort

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

kind regards,

Jos

#### Posting Permissions

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