---

Hej,

Jeg forsøger at implementere en QuickSort algoritme der skal sortere et
array af strings, men det går ikke helt som forventet. Teorien bag koden
burde være fin nok, men alligevel får jeg en StackOverflowErrror fejl i
følgende tre linie når jeg forsøger at køre skidtet:

i = s1.compareTo(s2);

while((l<r) && (compareStrings(t[r],split) == 1)){

sortStringArray(t,start,r);

Klassen ser ud som følger (klassen der kalder denne klasse følger
umiddelbart efter):

public class IntStringQuicksort {

public static void quicksort(String[] a)
{
System.out.print("Array before sorting: ");
printArray(a);
System.out.println(" ");

sortStringArray(a, 0, a.length-1);

System.out.print("Array after sorting: ");
printArray(a);
}

// Private function that does the sorting
private static void sortStringArray(String[] t, int start, int ende)
{
int span = ende - start + 1;
if(span > 1){
String split = t[start];
String help;
int l = start;
int r = ende;
while(l < r){
while((l<r) && (compareStrings(t[r],split) == 1)){
r--;
}
while((l<r) && (compareStrings(t[l],split) == 0)){
l++;
}
if(l < r){
help = t[l];
t[l] = t[r];
t[r] = help;
r--;
l++;
}
}//while
//recursive calls
sortStringArray(t,start,r);
sortStringArray(t,r+1,ende);
}//if
}

/* Private function that compares two strings
* Returns 1 if s1 is larger than s2
* Returns 0 if s1 is smaller than s2
*/
private static int compareStrings(String s1, String s2)
{
int i, j = 0;
i = s1.compareTo(s2);

if (i > 0)
{
j = 1;
}
else if (i < 0)
{
j = 0;
}

return j;
}

// Private function that prints out the array if it's shorter than or equal
to 20
private static void printArray(String[] a)
{
if (a.length <= 20)
{
System.out.print(a[0]);
for (int i = 1; i < a.length; i++)
{
System.out.print("," + a[i]);
}
}
else
{
System.out.println("Array length is less than 20 and is thus not
printed.");
}
}
}

public class IntStringQuicksortTest {

public static void main(String[] args) {
String[] a = {"1203","007","008","0123","00123"};
IntStringQuicksort.quicksort(a);
}
}

Nogle der kan se hvad jeg gør galt?

Mvh. Jacob

---

Jacob Nielsen wrote:

> Hej,
>
> Jeg forsøger at implementere en QuickSort algoritme der skal sortere et
> array af strings, men det går ikke helt som forventet. Teorien bag koden
> burde være fin nok, men alligevel får jeg en StackOverflowErrror fejl i
> følgende tre linie når jeg forsøger at køre skidtet:

Jeg har ikke sat mig ind i din kode, men en StackOverflowError tyder på at
der mangler en termineringsregel i din rekursive funktion.

--
Jonas Kongslund

---

"Jacob Nielsen" <jacob.nielsenREMOVE@REMOVEget2net.dk> writes:

> Jeg forsøger at implementere en QuickSort algoritme der skal sortere et
> array af strings, men det går ikke helt som forventet. Teorien bag koden
> burde være fin nok, men alligevel får jeg en StackOverflowErrror fejl i
> følgende tre linie når jeg forsøger at køre skidtet:

....
> // Private function that does the sorting
> private static void sortStringArray(String[] t, int start, int ende)

Enderne er inklusive.
....
> int span = ende - start + 1;
> if(span > 1){
> String split = t[start];
....
> sortStringArray(t,start,r);
> sortStringArray(t,r+1,ende);

hvad sker der hvis alle strengene ligger i den ene af disse?
(Hint: Man skal ikke tage pivot'en med når man kalder rekursivt :)

/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'

---

"Lasse Reichstein Nielsen" <lrn@hotpop.com> wrote in message
news:eksl4sr9.fsf@hotpop.com...
> "Jacob Nielsen" <jacob.nielsenREMOVE@REMOVEget2net.dk> writes:
>
> > Jeg forsøger at implementere en QuickSort algoritme der skal sortere et
> > array af strings, men det går ikke helt som forventet. Teorien bag koden
> > burde være fin nok, men alligevel får jeg en StackOverflowErrror fejl i
> > følgende tre linie når jeg forsøger at køre skidtet:
>
> ...
> > // Private function that does the sorting
> > private static void sortStringArray(String[] t, int start, int ende)
>
> Enderne er inklusive.
> ...
> > int span = ende - start + 1;
> > if(span > 1){
> > String split = t[start];
> ...
> > sortStringArray(t,start,r);
> > sortStringArray(t,r+1,ende);
>
> hvad sker der hvis alle strengene ligger i den ene af disse?
> (Hint: Man skal ikke tage pivot'en med når man kalder rekursivt :)

Tak :)