Java - What is wrong with this sorting code?

Question

I had help from someone but the code isn't working. It compiles, but when executed I get this:
Exception in thread "main" java.lang.Array IndexOutOf BoundsException: 20 at sort.main(sort.java:14)
(NOTE: I added some spaces to make it easier to read)

This is the code:

import java.util.Scanner;
import java.io.File;

class sort
{
public static void main(String[]args) throws Exception
{
Scanner sc = new Scanner(new File("file.input"));
obj[] list = new obj[20];

int count=0;
while(sc.hasNext())
{
list[count] = new obj(sc.nextDouble(), sc.next());
count++;
}
sort(list);

for(int i=0;i System.out.println(list[i].getS());

}

public static class obj
{
private double d;
public String s;
public obj(double dd, String ss)
{
d = dd;
s = ss;
}
double getD()
{
return d;
}
String getS()
{
return s;
}
}
static void sort(obj a[])
{
for (int i = a.length; --i>=0; )
{
boolean flipped = false;
for (int j = 0; j {
if (a[j].getD() > a[j+1].getD())
{
obj T = a[j];
a[j] = a[j+1];
a[j+1] = T;
flipped = true;
}
}
if (!flipped)
{
return; }
}
}
}

This is what the program is supposed to do:
There is a file that consists of a sequence r1 s1 r2 s2 r3 s3 ..., where ri is a real number of type double, and si is a String of symbols (that does not include empty spaces in the string its self). If one constructs a pair out of elements ri and si, for each index i, and then sorts these pairs in such a way that first elements of the pairs will be in monotonically increasing order, then the second components of the pairs, separated by empty spaces, form a text to create a paragraph.

So the first thing I have to do is scan the file, and make pairs out of the ri and si, but then I have to sort them by the doubles, ri. Once sorted, I have to print out the text, just the si.

The first few lines of this file look like this:
.3670360229982874 be 2.1758656832275705 of 7.558754198292892 in 7.414471768174697 behind 1.8838317339124944 know 1.20303007486753 hearing 7.734195638483449 and 7.1822892709521495 carried 6.53492389798644 other, 7.237144368426898 of
(note, the text above is all on one line. The word wrap is just breaking it up)

Thanks for your help!

Answer 1

You're running past the end of the "list" array. You've declared it to have 20 elements (0-19) but your input file would seem to have more than 20 elements. Either declare the "list" array to have more elements or trim down the input. I'm not saying that's all that's wrong with that program, but that's why it's crashing.



You may also want to separate this line:



list[count] = new obj(sc.nextDouble(), sc.next());



into something more like this:



double d = sc.nextDouble();

String s = sc.next();

list[count] = new obj(d,s);



to ensure that the double is scanned first. Some languages do not guarantee any order of execution among actual parameters, offhand I forget what Java does but it's better to be safe than sorry.

Answer 2

To cure that IndexOutOfBoundsException of yours, you have to change the size of the array to a higher number. You are probably reading more than 20 lines and that makes you list to go out of bounds.



As I see it, you have two options. The first one is to specify exactly how many elements you are going to store. That is, you have to change 20 to the exact value of lines in the data.input.



The second option is to change the container from the primitive array to java.util.Vector. That way you do not have to limit the input and your code will be more flexible. Here are the changes that you have to make:



First, import java.util.Vector and change the declaration of list to the following:

Vector list = new Vector();



So now you have a vector, it is empty though. You have to change the adding-part from

list[count] = new obj(sc.nextDouble(), sc.next());



To this:

list.add(new obj(sc.nextDouble(), sc.next()));



Now, one crazy thing about Vector is that it does not have support for []-operator, thus, you have to change all places where you want to access the list and use the elementAt function in Vector. An example would be in the final loop of the program:

for (int i = 0; i < list.size(); i++)

System.out.println(list.elementAt(i).getS());



Note that Vector does not have a length field, you have to use the size-function as shown above.



Ok, next, modify the sorting function to accept a vector instead of an array:

static void sort(Vector a)



Again, fix the vector access with the elementAt function and change length to size function. To set an element in the vector, use the set function. The proper sort function will look like this when you are done:



static void sort(Vector a)

{

for (int i = a.size(); --i >= 0;)

{

boolean flipped = false;

for (int j = 0; j < i; j++)

{

if (a.elementAt(j).getD() > a.elementAt(j + 1).getD())

{

obj T = a.elementAt(j);

a.set(j, a.elementAt(j+1));

a.set(j+1, T);

flipped = true;

}

}

if (!flipped)

return;

}

}

Answer 3

Look at the parameters of your binary search method ... Also, instead of writing a custom binary search method, you can use the one that comes with Array objects, that is, Arrays.binarySearch(double[] a, double key).