Problem Sorting an Array of Objects

[trantommyd]

Hi, I'm stuck figuring out where I went wrong with my code. I need to sort an array of objects called studentArray by the student's last name.

Here is the part of the code that sorts the array:
do{
check = true;
for(int s = 0; s < studentArray.length; s++){
String currentMin = studentArray[s].getLastName();
int currentMinIndex = s;
for(int n = 0; n < studentArray.length; n++){
Student temp = new Student();
if(currentMin.compareToIgnoreCase(studentArray[n].getLastName()) < 0){
temp = studentArray[s];
studentArray[s] = studentArray[n];
studentArray[n] = temp;
check = false;
}
}
}
}while(check = false);

Here is the way that code rearranges the array according to last name:
Christopher
Karr
McClurg
Noble
Cole
Rao
Stotz
Yi

Please help. This is for an assignment for my Java CS1 class. You'd think if an assignment was assigned over Spring Break, the prof would reply to emails over Spring Break asking for help...

I appreciate your time, thanks for looking.
Also, how do I display my code in text box like everyone else does? I'm new to the forum, and this is my first post.

[Fou-Lu]

It seems to be working for me, but I can tell you that the implementation of the selection sort is slightly incorrect, so it may just be the data you are using versus I.
The overall idea you are using is correct:

For each of the items in the array AS current
    For remaining items in the array AS next
        If next is less than current
           swap current, next
        endif
    endfor
endfor

Drop your do while. It will never iterate anyways since you assign check to false (and if its true it will infinite loop).

The incorrect part of the implementation is the nested for; you have created a variable called currentMinMax that you have not implemented. While this error does not impact on the sort's capability, it does destroy the (little) efficiency that the selection sort does have. There is no reason to look behind and check anything prior to this position as we know its already been sorted. Use a loop definition of for(int n = s + 1; n < studentArray.length; ++n) instead.

To display your code correctly, you wrap it in [code][/code] tags. PHP tags can be used as well for syntax highlighting, which mostly works in Java but falls apart on some scenarios so I'd suggest just the code tags.

Make those changes and post back the results. You can add the creation of studentArray as well so I can walk it through to see what I'm missing. Although sorting is a fundamental principal in programming and very necessary to learn, in the long run sorting becomes far more easier than this since in java you can use built in sort methods of Arrays and Collections classes with a provided Comparator (or just comparable will suffice for a .sort):

PHP Code:

Arrays.sort(studentArray, new Comparator<Student>(){
    public int compare(Student s0, Student s1)
    {
        int iResult = 0;
        if (s0 != null && s1 != null)
        {
            iResult = s0.getLastName().compareToIgnoreCase(s1.getLastName());
        }
        else
        {
            iResult = (s0 == null && s1 != null) ? 1 : -1;
        }
        return iResult;
    }
}); 


Don't use the above for an assignment on sorting. This is just an example of what you will do in the future when you need to sort.

[trantommyd]

Ok, I deleted the do while loop and the creation of the currentMinIndex variable. However, when I changed the nested for from "n = 0" to "n = s + 1", the array was no longer in (mostly) alphabetical order.

So this is what I have now:

				for(int s = 0; s < studentArray.length; s++)
				{
					String currentMin = studentArray[s].getLastName();
					for(int n = 0; n < studentArray.length; n++)
					{
						Student temp = new Student();
						if(currentMin.compareToIgnoreCase(studentArray[n].getLastName()) < 0)
						{
							temp = studentArray[s];
							studentArray[s] = studentArray[n];
							studentArray[n] = temp;
						}
					}
				}

And here is my Student class:

class Student
{
	String lastName, firstName, exam1, asg1, asg2, exam2, asg3, asg4;

	Student()
	{
	}
	
	Student(String a, String b, String c, String d, String e, 
			String f, String g, String h)
	{
		lastName = a;
		firstName = b;
		exam1 = c;
		asg1 = d;
		asg2 = e;
		exam2 = f;
		asg3 = g;
		asg4 = h;
	}
	
	double getNumberGrade()
	{
		double test1 = Double.parseDouble(exam1);
		double hwk1 = Double.parseDouble(asg1);
		double hwk2 = Double.parseDouble(asg2);
		double test2 = Double.parseDouble(exam2);
		double hwk3 = Double.parseDouble(asg3);
		double hwk4 = Double.parseDouble(asg4);
		
		return (((hwk1 + hwk2 + hwk3 + hwk4)/16) + (test1/4) + (test2/2));
	}
	
	char getLetterGrade()
	{	
		double test1 = Double.parseDouble(exam1);
		double hwk1 = Double.parseDouble(asg1);
		double hwk2 = Double.parseDouble(asg2);
		double test2 = Double.parseDouble(exam2);
		double hwk3 = Double.parseDouble(asg3);
		double hwk4 = Double.parseDouble(asg4);
		double numberGrade = (((hwk1 + hwk2 + hwk3 + hwk4)/16) + (test1/4) + (test2/2));
		
		if(numberGrade >= 90)
			return 'A';
		if(numberGrade >= 80)
			return 'B';
		if(numberGrade >= 70)
			return 'C';
		if(numberGrade >= 60)
			return 'D';
		else
			return 'F';
	}
	
	String getLastName()
	{
		return lastName;
	}
}

[Fou-Lu]

Between selection's unstable nature, the use of full iteration twice and the comparison, you end up with an intermittent search result.

Try to implement this algorithm, and post back results. This is close, but not quite right (as you can see):

for i = 0 to array.size
    for n = i + 1 to array.size
        // really important to pay attention to the order items are checked
        if array[n] < array[i] then // use comparison functions, this here is equivalent to arrayObj[n].compareTo(arrayObj[i]) < 0
            tmp = array[i]
            array[i] = array[n]
            array[n] = array[i]
        end if
    next n
next i

You'll notice that the comparison order is extremely important when using an n = i + 1 check. This is because you cannot go back to swap smaller items later, so you must check the comparison in the correct order.

[trantommyd]

When I tried using < instead of comparesTo, it gave me this error:

GradesVersion2.java:55: operator < cannot be applied to java.lang.String,java.lang.String
						if(studentArray[s].getLastName() < studentArray[n].getLastName())
						                                 ^
1 error

With a little bit of tinkering, I got my code to work.

for(int s = 0; s < studentArray.length; s++)
				{
					for(int n = s + 1; n < studentArray.length; n++)
					{
						Student temp = new Student();
						if(studentArray[s].getLastName().compareToIgnoreCase(studentArray[n].getLastName()) > 0 )
						{
							temp = studentArray[s];
							studentArray[s] = studentArray[n];
							studentArray[n] = temp;
						}
					}
				}

Thank you so much for your help. You've made my first experience on this forum a very positive one.

[Fou-Lu]

Yes, using < with strings won't work since Java doesn't include operator and comparison overloads for this kind of handling with objects. I made the comment there to say how its reflected in the object as a comparable type instead. Algorithm writing avoids most methods since they are language specific, although I can say any item is < another item, and leave the implementation to the language.
If it helps you, this is what I used during testing, and debugging when necessary:

PHP Code:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class Student
{
    String sLastName;
    String sFirstName;

    public Student()
    {
        this("", "");
    }

    public Student(String sFirstName, String sLastName)
    {
        this.sFirstName = sFirstName;
        this.sLastName = sLastName;
    }

    public String getLastName()
    {
        return this.sLastName;
    }
    
    public String toString()
    {
        return this.sLastName + ", " + this.sFirstName;
    }

    public static Student[] createStudentArray(int iSize)
    {
        ArrayList<String> aLastNames = new ArrayList<String>();
        ArrayList<String> aFirstNames = new ArrayList<String>();
        ArrayList<Student> aStudents = new ArrayList<Student>();
        Student[] studentArray = null;
        aLastNames.add("Doe");
        aLastNames.add("Smith");
        aLastNames.add("Johnson");
        aLastNames.add("Williams");
        aLastNames.add("Jones");
        
        aFirstNames.add("James");
        aFirstNames.add("John");
        aFirstNames.add("Robert");
        aFirstNames.add("Mary");
        aFirstNames.add("Patricia");
        aFirstNames.add("Linda");
        
        for (int i = 0; i < iSize; ++i)
        {
            Collections.shuffle(aLastNames);
            Collections.shuffle(aFirstNames);
            aStudents.add(new Student(aFirstNames.get(0), aLastNames.get(0)));
        }

        /*
         * Due to the order these are inserted, and the issues with the algorithm used for yourSort
         * these are guaranteed to cause issues with yourSort.  
         */
        /*
        aStudents.add(new Student("Mary", "Williams"));
        aStudents.add(new Student("Patricia", "Williams"));
        aStudents.add(new Student("Linda", "Smith"));
        aStudents.add(new Student("Robert", "Jones"));
        aStudents.add(new Student("Mary", "Williams"));
        aStudents.add(new Student("Mary", "Williams"));
        aStudents.add(new Student("Linda", "Johnson"));
        aStudents.add(new Student("James", "Doe"));
        aStudents.add(new Student("Patricia", "Doe"));
        aStudents.add(new Student("Patricia", "Smith"));
        */
        
        studentArray = new Student[aStudents.size()];
        aStudents.toArray(studentArray);
        
        return studentArray;
    }
    
    public static void mySort(Student[] studentArray)
    {
        for(int s = 0; s < studentArray.length; ++s)
        {
            for(int n = s + 1; n < studentArray.length; ++n)
            {
                if (studentArray[n].getLastName().
                        compareToIgnoreCase(studentArray[s].getLastName()) < 0)
                {
                    Student temp = studentArray[s];
                    studentArray[s] = studentArray[n];
                    studentArray[n] = temp;
                }
            }
        }
    }
    
    public static void yourSort(Student[] studentArray)
    {
        for(int s = 0; s < studentArray.length; s++)
        {
            String currentMin = studentArray[s].getLastName();
            for(int n = 0; n < studentArray.length; n++)
            {
                Student temp = new Student();
                if(currentMin.compareToIgnoreCase(studentArray[n].getLastName()) < 0)
                {
                    temp = studentArray[s];
                    studentArray[s] = studentArray[n];
                    studentArray[n] = temp;
                }
            }
        }
    }
    
    public static void yourNewSort(Student[] studentArray)
    {
        for(int s = 0; s < studentArray.length; s++)
        {
            for(int n = s + 1; n < studentArray.length; n++)
            {
                Student temp = new Student();
                if(studentArray[s].getLastName().compareToIgnoreCase(studentArray[n].getLastName()) > 0 )
                {
                    temp = studentArray[s];
                    studentArray[s] = studentArray[n];
                    studentArray[n] = temp;
                }
            }
        }
    }
    
    public static void main(String[] argv)
    {
        Student[] studentArray = createStudentArray(20);
        
        Student[] aYours = Arrays.copyOf(studentArray, studentArray.length);
        Student[] aMine = Arrays.copyOf(studentArray, studentArray.length);
        Student[] aYourNew = Arrays.copyOf(studentArray, studentArray.length);
        
        System.out.println("Before sort:");
        for (Student s : studentArray)
        {
            System.out.println(s);
        }
                
        mySort(aMine);
        System.out.println("\nAfter mySort:");
        for (Student s : aMine)
        {
            System.out.println(s);
        }
        
        yourSort(aYours);
        System.out.println("\nAfter yourSort:");
        for (Student s : aYours)
        {
            System.out.println(s);
        }
        
        yourNewSort(aYourNew);
        System.out.println("\nAfter yourNewSort:");
        for (Student s : aYourNew)
        {
            System.out.println(s);
        }    
    }
}