当前位置: 动力学知识库 > 问答 > 编程问答 >

java - How to get rid off the stackoverflows in my quicksort implementation?

问题描述:

everybody!

I have got some stackoverflow problems with my quicksort implementation in Java with randomized pivot element for every recursive call for the quicksort as seen in the codes down below. My problem is that I have got stackoverflow at three (!) places in my codes:

import java.util.Random;

/**

* Write a description of class QuickSort1 here.

*

* @author (your name)

* @version (a version number or a date)

*/

public class QuickSort1 implements IntSorter

{

private int[] v;

private Random randomGenerator;

public QuickSort1()

{

randomGenerator = new Random();

}

public void sort(int[] v)

{

this.v = v;

if(this.v.length > 0) {

quickSort(this.v, 0, this.v.length-1);

}

else {

return;

}

}

private void quickSort(int[] v, int first, int last)

{

if(v.length < 2)

return;

else {

int First = first;

int Last = last;

int pivot = v[randomGenerator.nextInt(v.length)];

while(First <= Last) {

while(v[First] < pivot) {

First++;

}

while(v[Last] > pivot) {

Last--;

if(Last==0)

break;

}

if(First<=Last) {

int temp = v[First];

v[First] = v[Last];

v[Last] = temp;

First++;

Last--;

}

}

if(first < Last)

quickSort(v, first, Last);

if(First < last)

quickSort(v, First, last);

}

}

}

The error messages I get when calling sort(int[] v) is as follows:

java.lang.StackOverflowError

at java.util.Random.nextInt(Random.java:307)

at QuickSort1.quickSort(QuickSort1.java:37)

at QuickSort1.quickSort(QuickSort1.java:60)

at QuickSort1.quickSort(QuickSort1.java:58)

These messages indicate stackoverflow at the lines both when the pivot element gets decided by the random generator in range between 0 (inclusive) and v.length (exclusive) and at the two recursive method calls at the end of the quickSort method.

The strange thing is that when I want to sort a few elements, then the implementation works fine. The problems with this implementation begins to come when I want to sort, for example, 1000 elements, then the StackOverflowExceptions occur and the error at line 58 and 60 gets repeated a lot of times in the terminal.

I would appreciate a lot with some help here :)

Thanks in advance!

/Confused dude

网友答案:
if(first < Last)
  quickSort(v, first, Last);
if(First < last)
  quickSort(v, First, last);

v is the complete array. It never will reach a length smaller than 2. Either partition v, or adjust the base case condition to

last - first < 2
分享给朋友:
您可能感兴趣的文章:
随机阅读: