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