Sorting Objects in java using insertion sort



Contents of page >
  • Full Program/SourceCode/Example of Sorting Objects in java  >
  • Complexity of Insertion Sort for sorting objects in java>
  • Complexity of Insertion Sort for sorting object in graph >


In this post we are going to sort Employee on basis of his name.
It may the possibility that you have stored object somewhere  sorted on the basis of date or any other field, but,
later on you would like to sort Employee on the basis of name for some reason.
This program uses Insertion Sort for sorting Employee


but, we may use Bubble Sort, Selection Sort, merge Sort, quick Sort for sorting objects which may offer you different time complexity(as per requirement).


                       Single circular LinkedList - Find intersection point.


Full Program/SourceCode/Example of Sorting Objects in java  >
/**
* Employee class
*/
class Employee {
   private String id;
   private String name;
   private int salary;
  
   /**
   * Employee constructor
   */
   public Employee(String id, String name, int salary) { // constructor
          this.id = id;
          this.name = name;
          this.salary = salary;
   }
   /**
   * Return name of employee
   */
   public String getName()
   {
          return name;
   }
  
   /**
   * Display employee
   */
   public void display() {
          System.out.print("Name=" + name);
          System.out.print(", Id=" + id);
          System.out.println(", Salary=" + salary);
   }
  
}
/**
* This class will hold reference to Employee Array
*/
class InsertionSortEmployeeArray {
   private Employee[] ar;
   private int index; // holds current position of array, by default it is initialized with 0
  
   /**
   * Constructor for initializing Employee Array
   */
   public InsertionSortEmployeeArray(int maxSize) // constructor
   {
          ar = new Employee[maxSize]; // creation of Employee array
          index = 0;
   }
   /**
   * This method inserts elements in Employee Array.
   */
   public void insert(String id, String name, int salary) {
          ar[index++] = new Employee(id, name, salary);
   }
   /**
   * This method Display Employee Array
   */
   public void display()
   {
          for (int i = 0; i < index; i++)             
                 ar[i].display();
          System.out.println("");
   }
   /**
   * This method Sort Employee Array using Insertion Sort
   */
   public void sortEmployee() {
          int inner, outer;
          Employee tempValue;
          for (outer = 1; outer < index; outer++) // outer is dividing line
          {
                 tempValue = ar[outer]; // remove the marked Employee
                 inner = outer; // shifting starts at outer
                 while (inner > 0 && ar[inner - 1].getName().compareTo(tempValue.getName()) > 0) { // until we found smaller Employee(employee with smaller name),
                       ar[inner] = ar[inner - 1]; // shift Employee to the right
                       --inner; // go one position left
                 }
                 ar[inner] = tempValue; // insert marked Employee at inner position
          }
   }
         
}
 
 
 
/** Copyright (c), AnkitMittal www.JavaMadeSoEasy.com */
/**
* Main class
*/
public class ObjectSortApp {
   public static void main(String[] args) {
          int size = 10; // Initial Employee array size
          InsertionSortEmployeeArray sortEmployeeArray;
         
          sortEmployeeArray = new InsertionSortEmployeeArray(size); // creation of Employee array
          sortEmployeeArray.insert("01", "Sam", 100000);
          sortEmployeeArray.insert("02", "Kat", 100000);
          sortEmployeeArray.insert("03", "Amy", 200000);
          sortEmployeeArray.insert("04", "Rick",200000);
          sortEmployeeArray.insert("05", "Ab", 200000);
          sortEmployeeArray.insert("06", "Sym", 300000);
          sortEmployeeArray.insert("07", "John", 400000);
          sortEmployeeArray.insert("08", "Henry", 200000);
         
          System.out.println("Display Employee before sorting: ");
          sortEmployeeArray.display();
         
          sortEmployeeArray.sortEmployee();;
         
          System.out.println("Display Employee after sorting(on basis of name): ");
          sortEmployeeArray.display();
   }
}
/** OUTPUT
Display Employee before sorting:
Name=Sam, Id=01, Salary=100000
Name=Kat, Id=02, Salary=100000
Name=Amy, Id=03, Salary=200000
Name=Rick, Id=04, Salary=200000
Name=Ab, Id=05, Salary=200000
Name=Sym, Id=06, Salary=300000
Name=John, Id=07, Salary=400000
Name=Henry, Id=08, Salary=200000
Display Employee after sorting(on basis of name):
Name=Ab, Id=05, Salary=200000
Name=Amy, Id=03, Salary=200000
Name=Henry, Id=08, Salary=200000
Name=John, Id=07, Salary=400000
Name=Kat, Id=02, Salary=100000
Name=Rick, Id=04, Salary=200000
Name=Sam, Id=01, Salary=100000
Name=Sym, Id=06, Salary=300000
*/


So, we wrote program to do Sorting of Objects in java.


Complexity of Insertion Sort for sorting objects in java>
Best,average and worst case >


Best Case :         O(n) [When input is already sorted]
Average Case :  O(n2).
Worst Case :      The worst case too is O(n2), even though the code inside the if statement will not get executed in this case. The quadratic complexity is due to the fact that the one for loop and other while loop will execute completely in all the three cases irrespective of the content of the list.


>No. of comparisons : O(n) in best case
O(n2) in average/worst case
>No. of swaps : O(n2) in average/worst case
& 0 in best case(When array is already sorted)

Complexity of Insertion Sort for sorting object in graph >



Summary >
So in this data structure tutorial we learned program/Example of Sorting Objects in java. Complexity of Insertion Sort for sorting objects in java. Complexity of Insertion Sort for sorting object in graph.


Having any doubt? or you you liked the tutorial! Please comment in below section.
Please express your love by liking JavaMadeSoEasy.com (JMSE) on facebook, following on google+ or Twitter.


RELATED LINKS>
eEdit
Must read for you :