sort objects

Sort objects in Java using Insertion Sort

In our Java program below we use insertion sort to sort Student objects based on the lastName key values.

The doInsertionSort() method in this example is similar to doInsertionSort() method in the insertion sort example, but the only difference is we are comparing the lastName key values instead of a primitive type and we use compareTo() method of the String class for comparisons.

1. Sort objects using insertion sort

In our previous article we had learnt about insertion sort. At each iteration, insertion sort removes one element from the input array and insert that element in a location it belongs within the sorted list. And this is repeated until there are no elements remaining in the input array.

package com.sneppets.dsalgo;

/**
 * The student objects are sorted based on the last name
 * We have used insertion sort in our java program to sort students objects
 * 
 * @author sneppets
 *
 */
class Student{
	
	private String firstName;
	
	private String lastName;
	
	private int age;	
	
	public Student(String fName, String lName, int age){
		
		this.firstName = fName;
		this.lastName = lName;
		this.age = age;
	}	
	
	public void printStudentDetails()
	{
		System.out.print("First Name: " + firstName);
		System.out.print(", Last Name: " + lastName);
		System.out.println(", Age: " + age);
	}
	
	public String getLastName()
	{
		return lastName;
	}
	
}

class StudentsArrayInObj {
	
	private Student[] studentsArray;
	
	private int nElements;
	
	public StudentsArrayInObj(int max)
	{
		//create student array
		studentsArray = new Student[max]; 

		// no elements yet in the array
		nElements = 0;	
	}
	
	public void insert(String fName, String lName, int age)
	{
		studentsArray[nElements] = new Student(fName, lName, age);
		
		nElements++;
		
	}
	
	public void printStudentsArrayElements()
	{
		for (int i=0; i<nElements; i++)
		{
			studentsArray[i].printStudentDetails();
		}
	}
	
	//Insertion sort starts here ................................
	public void doInsertionSort(){
		
		int in, out;	
		
		//Divide the array of elements by marking an element
		for (out=1; out< nElements; out++)
		{
			//remove marked student
			Student temp = studentsArray[out];

			//start shifting at out
			in = out;

			//until smaller one is found, shift element to the right 
			//and go one position left
			while(in > 0 && 
					studentsArray[in -1].getLastName().compareTo(temp.getLastName()) > 0)
			{
				//shift element to the right
				studentsArray[in] = studentsArray[in-1];

				//go one position left
				--in;
				
			}
			//insert marked element
			studentsArray[in] = temp;
		}
	}
	//Insertion sort ends here .....................................
	
}

public class SortObjectsInsertionSortExample {
	
	public static void main(String[] args)
	{
		//create student array
		StudentsArrayInObj studArray = new StudentsArrayInObj(10);

		//insert items
		studArray.insert("John", "Smith", 15);
		studArray.insert("Ram", "Kumar", 11);
		studArray.insert("Mohan", "Prakash", 14);
		studArray.insert("Paul", "John", 16);

		//display items
		System.out.println("Before sorting student objects");
		studArray.printStudentsArrayElements();

		//insertion sort
		studArray.doInsertionSort();

		//display items after sorting using insertion sort
		System.out.println("After sorting student objects");
		studArray.printStudentsArrayElements();		
		
	}	

}

Output

Before sorting student objects
First Name: John, Last Name: Smith, Age: 15
First Name: Ram, Last Name: Kumar, Age: 11
First Name: Mohan, Last Name: Prakash, Age: 14
First Name: Paul, Last Name: John, Age: 16
After sorting student objects
First Name: Paul, Last Name: John, Age: 16
First Name: Ram, Last Name: Kumar, Age: 11
First Name: Mohan, Last Name: Prakash, Age: 14
First Name: John, Last Name: Smith, Age: 15

2. Sort objects using Comparator

package com.sneppets.dsalgo;

import java.util.Arrays;
import java.util.Comparator;

class Student implements Comparable<Student>{
	
	private String firstName;
	
	private String lastName;
	
	private int age;	
	
	public Student(String fName, String lName, int age){
		
		this.firstName = fName;
		this.lastName = lName;
		this.age = age;
	}	
	
	public void printStudentDetails()
	{
		System.out.print("First Name: " + firstName);
		System.out.print(", Last Name: " + lastName);
		System.out.println(", Age: " + age);
	}
	
	public String getFirstName()
	{
		return firstName;
	}
	
	public String getLastName()
	{
		return lastName;
	}
	
	public int getAge(){
		return age;
	}

	@Override
	public int compareTo(Student compareStudent) {
		
		int compareAge = ((Student)compareStudent).getAge();
		
		return this.age - compareAge;
	}
	
	public static Comparator<Student> StudentLastNameComparator
				= new Comparator<Student>(){
		public int compare(Student stud1, Student stud2)
		{
			String lastName1 = stud1.getLastName().toUpperCase();
			String lastName2 = stud2.getLastName().toUpperCase();
			
			return lastName1.compareTo(lastName2);
		}
		
	};
	
}

class StudentsArrayInObj {
	
	private Student[] studentsArray;
	
	private int nElements;
	
	public StudentsArrayInObj(int max)
	{
		//create student array
		studentsArray = new Student[max]; 
		// no elements yet in the array
		nElements = 0;	
	}
	
	public void insert(String fName, String lName, int age)
	{
		studentsArray[nElements] = new Student(fName, lName, age);
		
		nElements++;
		
	}
	
	public void printStudentsArrayElements()
	{
	
		for (int i=0; i<nElements; i++)
		{
			studentsArray[i].printStudentDetails();
		}
	}
	
	public void sortArrayByAge(){
		
		Arrays.sort(studentsArray);
	}
	
	public void sortArrayByLastName(){
		Arrays.sort(studentsArray, Student.StudentLastNameComparator);
	}
	
}


public class SortObjectsComparatorExample {
	
	public static void main (String args[])
	{
		StudentsArrayInObj studArray;
		studArray = new StudentsArrayInObj(4);
		
		studArray.insert("John", "Smith", 15);
		studArray.insert("Ram", "Kumar", 11);
		studArray.insert("Mohan", "Prakash", 14);
		studArray.insert("Paul", "John", 16);
		
		System.out.println("Before sorting student objects");
		studArray.printStudentsArrayElements();
				
		studArray.sortArrayByAge();
		System.out.println("Sort student objects by age");
		studArray.printStudentsArrayElements();
		
		studArray.sortArrayByLastName();
		System.out.println("Sort student objects by last name");
		studArray.printStudentsArrayElements();
	}

}

Output

Before sorting student objects
First Name: John, Last Name: Smith, Age: 15
First Name: Ram, Last Name: Kumar, Age: 11
First Name: Mohan, Last Name: Prakash, Age: 14
First Name: Paul, Last Name: John, Age: 16
Sort student objects by age
First Name: Ram, Last Name: Kumar, Age: 11
First Name: Mohan, Last Name: Prakash, Age: 14
First Name: John, Last Name: Smith, Age: 15
First Name: Paul, Last Name: John, Age: 16
Sort student objects by last name
First Name: Paul, Last Name: John, Age: 16
First Name: Ram, Last Name: Kumar, Age: 11
First Name: Mohan, Last Name: Prakash, Age: 14
First Name: John, Last Name: Smith, Age: 15

3. Sort objects using Comparable

package com.sneppets.dsalgo;

import java.util.Arrays;

class Student implements Comparable<Student>{
	
	private String firstName;
	
	private String lastName;
	
	private int age;	
	
	public Student(String fName, String lName, int age){
		
		this.firstName = fName;
		this.lastName = lName;
		this.age = age;
	}	
	
	public void printStudentDetails()
	{
		System.out.print("First Name: " + firstName);
		System.out.print(", Last Name: " + lastName);
		System.out.println(", Age: " + age);
	}
	
	public int getAge(){
		return age;
	}

	@Override
	public int compareTo(Student compareStudent) {
		
		int compareAge = ((Student)compareStudent).getAge();
		
		return this.age - compareAge;
	}
	
}

class StudentsArrayInObj {
	
	private Student[] studentsArray;
	
	private int nElements;
	
	public StudentsArrayInObj(int max)
	{
		//create student array
		studentsArray = new Student[max]; 
		// no elements yet in the array
		nElements = 0;	
	}
	
	public void insert(String fName, String lName, int age)
	{
		studentsArray[nElements] = new Student(fName, lName, age);
		
		nElements++;
		
	}
	
	public void printStudentsArrayElements()
	{
	
		for (int i=0; i<nElements; i++)
		{
			studentsArray[i].printStudentDetails();
		}
	}
	
	public void doArraySort(){
		
		Arrays.sort(studentsArray);
	}
	
}

public class SortObjectsComparableExample {
	
	public static void main (String args[])
	{
		StudentsArrayInObj studArray;
		studArray = new StudentsArrayInObj(4);
		
		studArray.insert("John", "Smith", 15);
		studArray.insert("Ram", "Kumar", 11);
		studArray.insert("Mohan", "Prakash", 14);
		studArray.insert("Paul", "John", 16);
		
		System.out.println("Before sorting student objects");
		studArray.printStudentsArrayElements();
				
		studArray.doArraySort();
		System.out.println("After sorting student objects");
		studArray.printStudentsArrayElements();
	}

}

Output

Before sorting student objects
First Name: John, Last Name: Smith, Age: 15
First Name: Ram, Last Name: Kumar, Age: 11
First Name: Mohan, Last Name: Prakash, Age: 14
First Name: Paul, Last Name: John, Age: 16
After sorting student objects
First Name: Ram, Last Name: Kumar, Age: 11
First Name: Mohan, Last Name: Prakash, Age: 14
First Name: John, Last Name: Smith, Age: 15
First Name: Paul, Last Name: John, Age: 16

References

  1. Wikipedia sorting algorithm
  2. Comparator Oracle Documentation
  3. Comparable Oracle Documentation
guest
0 Comments
Inline Feedbacks
View all comments