Wednesday 28 March 2018

Java Program to implement Selection Sort

         In previous post, we implemented the Bubble Sort algorithm. In this, we can implement the Selection Sort algorithm and it's time complexity.       
 
         The selection sort is a combination of searching and sorting. During each stage, the unsorted element with the smallest (or largest) value is moved to its proper position in the array. The number of times the sort passes through the array is one less than the number of items in the array. In the selection sort, the inner loop finds the next smallest (or largest) value and the outer loop places that value into its proper location.

See the below example explained with diagram,

Selection Sort

SelectionSort.java,

package com.test;

public class SelectionSort {

      public static int[] sortArray(int[] arr){
        
           for (int i = 0; i < arr.length - 1; i++) {
                int index = i;
                for (int j = i + 1; j < arr.length; j++) {
                     if (arr[j] < arr[index]) {
                        index = j;
                     }
                }
      
                int minNumber = arr[index];  
                arr[index] = arr[i];
                arr[i] = minNumber;
           }
           return arr;
      }
 
      public static void printArray(int[] arr) {
           for (int i=0; i<arr.length; i++) {
                System.out.print(arr[i]+" ");
           }
      }
     
      public static void main(String a[]){
         
             int[] arr1 = {8,10,2,43,12,92,58,62};
             System.out.println("Array before Sorting,");
             printArray(arr1);
             System.out.println("");
             int[] arr2 = sortArray(arr1);
             System.out.println("Array after sorting,");
             printArray(arr2);
      }
}

Output :-
Array before Sorting,
8 10 2 43 12 92 58 62
Array after sorting,
2 8 10 12 43 58 62 92


Complexity:--

         Selecting the lowest element requires scanning all n elements (this takes n - 1 comparisons) and then swapping it into the first position.

Finding the next lowest element requires scanning the remaining n - 1 elements and so on,
= (n - 1) + (n - 2) + ... + 2 + 1 = n(n - 1) / 2
= O(n^2) comparisons.

Best Case :    O(n^2) 
Worst Case :   O(n^2) 

Average Case : O(n^2)

     Note :--  Selection sort is faster and more efficient compared to bubble sort, because this sort performs less number of swaps compared to bubble sort process therefore even both the sorting methods are of O(n^2).

Related Post :-
1) Java Program for Bubble Sort in Ascending and Descending order
2) Java Program to Sort ArrayList of Custom Objects By Property using Comparator interface
3)  Difference between Comparable and Comparator Interface in Java

Thursday 15 March 2018

Hibernate One to One Mapping Example - Annotation based

              In previous post, we learned about Hibernate Annotations with explanation. In this we will see what is hibernate one to one relationship and how to implement it using Annotatons. We will demonstrate the relationship by taking two model classes Student  and  Address and try to establish a one to one relationship in between them.

              In this example, shown one to one relationship using foreign key association. Another way is using primary key association using @PrimaryKeyJoinColumn. In the below example Student table has foreign key column(address_id) references the primary key of Address Table (Primary key is address_id) .

onetoone mapping in hibernate
Create Database Tables :-

          Using MySQL database, creating two tables student and address. Student table has one foreign key constraint i.e address_id. (You can use any database as your wish).


create table STUDENT (
   student_id BIGINT NOT NULL AUTO_INCREMENT,
   address_id BIGINT NOT NULL,
   first_name VARCHAR(30) NOT NULL,
   last_name  VARCHAR(30) NOT NULL,
   section    VARCHAR(30) NOT NULL,
   PRIMARY KEY (student_id),
   CONSTRAINT student_address FOREIGN KEY (address_id) REFERENCES ADDRESS (address_id)
);

create table ADDRESS (
   address_id BIGINT NOT NULL AUTO_INCREMENT,
   street VARCHAR(30) NOT NULL,
   city  VARCHAR(30) NOT NULL,
   country  VARCHAR(30) NOT NULL,
   PRIMARY KEY (address_id)
);


Next step,
Create Model Classes:-

      Model class Student & Address are simple POJO class which is annotated with JPA annotations to map it to a database tables

Student.java,

package com.testapp.hibernate.model;
 
import javax.persistence.Column;
import javax.persistence.Entity;
import javax.persistence.GeneratedValue;
import javax.persistence.Id;
import javax.persistence.JoinColumn;
import javax.persistence.OneToOne;
import javax.persistence.Table;
 
@Entity
@Table(name = "student")
public class Student {
 
      @Id
      @GeneratedValue
      @Column(name = "student_id")
      private long id;
 
      @Column(name = "first_name")
      private String firstName;
 
      @Column(name = "last_name")
      private String lastName;
 
      @Column(name = "section")
      private String section;
 
      @OneToOne
      @JoinColumn(name="address_id")
      private Address address;
 
 
      public Student() {
 
      }
 
      public Student(String firstName, String lastName, String section) {
          this.firstName = firstName;
          this.lastName = lastName;
          this.section = section;
      }
 
      public long getId() {
          return id;
      }
 
      public void setId(long id) {
          this.id = id;
      }
 
      public String getFirstName() {
          return firstName;
      }
 
      public void setFirstName(String firstName) {
          this.firstName = firstName;
      }
 
      public String getLastName() {
          return lastName;
      }
 
      public void setLastName(String lastName) {
          this.lastName = lastName;
      }
 
      public String getSection() {
          return section;
      }
 
      public void setSection(String section) {
          this.section = section;
      }
 
      public Address getAddress() {
          return address;
      }
 
      public void setAddress(Address address) {
          this.address = address;
      }
 
      @Override
      public String toString() {
          return "Student [id=" + id + ", firstName=" + firstName + ", lastName="
                + lastName + ", section=" + section + ", address=" + address
                + "]";
      }
}

       In this example I used Unidirectional Mapping i.e it will provide navigational access only to one direction(i.e ). For this I didn't use @OneToOne annotation in Address entity.

Address.java,

package com.testapp.hibernate.model;

import javax.persistence.Column;
import javax.persistence.Entity;
import javax.persistence.GeneratedValue;
import javax.persistence.Id;
import javax.persistence.Table;

@Entity
@Table(name = "address")
public class Address {

        @Id 
        @GeneratedValue
        @Column(name = "address_id")
        private long id;

        @Column(name = "street")
        private String street;

        @Column(name = "city")
        private String city;

        @Column(name = "country")
        private String country;

        public Address() {

        }

        public Address(String street, String city, String country) {
              this.street = street;
              this.city = city;
              this.country = country;
        }

        public long getId() {
             return id;
        }

        public void setId(long id) {
             this.id = id;
        }

        public String getStreet() {
             return street;
        }

        public void setStreet(String street) {
             this.street = street;
        }

        public String getCity() {
             return city;
        }

        public void setCity(String city) {
             this.city = city;
        }

        public String getCountry() {
             return country;
        }

        public void setCountry(String country) {
             this.country = country;
        }

        @Override
        public String toString() {
             return "Address [id=" + id + ", street=" + street + ", city=" + city
              + ", country=" + country + "]";
        }
 
}



Next step,
Create Hibernate Configuration file:-

          We need to inform hibernate about how to connect to database, which database dialect we will be using so that hibernate can generate the instruction specific to that database.

We define all these information in hibernate.cfg.xml. Create this file with below content and save it in src/main/resources folder.

hibernate.cfg.xml,


<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE hibernate-configuration SYSTEM "http://www.hibernate.org/dtd/hibernate-configuration-3.0.dtd">
 
<hibernate-configuration>
    <session-factory>
        <property name="hibernate.dialect">org.hibernate.dialect.MySQLDialect</property>
        <property name="hibernate.connection.driver_class">com.mysql.jdbc.Driver</property>
        <property name="hibernate.connection.username">root</property>
        <property name="hibernate.connection.password">root</property>
        <property name="hibernate.connection.url">jdbc:mysql://localhost:3306/testapp</property>
        <property name="show_sql">true</property>
        <property name="format_sql">false</property>
        <mapping class="com.testapp.hibernate.model.Student"/>
        <mapping class="com.testapp.hibernate.model.Address"/>
    </session-factory>
</hibernate-configuration>

dialect - This property makes Hibernate generate the appropriate SQL for the chosen database.
driver_class - This defines the database specific driver hibernate will use to make connection.
show_sql - It will instruct hibernate to log all the statements on console.
format_sql - It will instructs it to display properly formatted sql.


Next step,
Create Hibernate Utility Class,

HibernateUtil.java,

package com.testapp.hibernate;
 
import org.hibernate.SessionFactory;
import org.hibernate.cfg.AnnotationConfiguration;
 
public class HibernateUtil {
     
    private static final SessionFactory sessionFactory;
     
    static{
        try{
            sessionFactory = new AnnotationConfiguration().configure().buildSessionFactory();
 
        }catch (Throwable ex) {
            System.err.println("Session Factory can not be created." + ex);
            throw new ExceptionInInitializerError(ex);
        }   
    }
     
    public static SessionFactory getSessionFactory() {
        return sessionFactory;
    }
     
}


Execute Main Class:--

Main Class to run and execute the insert and fetch operations,
HibernateApp.java,


package com.testapp.hibernate;
 
import java.util.List;
 
import org.hibernate.Session;
 
import com.testapp.hibernate.model.Address;
import com.testapp.hibernate.model.Student;
 
public class HibernateApp {
     
    @SuppressWarnings("unchecked")
    public static void main(String[] args) {
 
        Student student = new Student("Mahesh","Patil","A");
        Address address = new Address("#12, 12th E Main, Madiwala","Bangalore","India");
         
         
        Session session = HibernateUtil.getSessionFactory().openSession();
        session.beginTransaction();
 
        session.persist(address);
        student.setAddress(address);
        session.persist(student);
 
        List<Student> students = (List<Student>)session.createQuery("from Student ").list();
        for(Student st: students){
            System.out.println("Student Details : "+st);
        }
         
        session.getTransaction().commit();
        session.close();  
    }
 
}

Execute the above code,

Output :--Hibernate: insert into ADDRESS (CITY, COUNTRY, STREET) values (?, ?, ?)
                  Hibernate: insert into STUDENT (ADDRESS_ID, FIRST_NAME, LAST_NAME,                                    SECTION) values (?, ?, ?, ?)
               
                  Hibernate: select student0_.STUDENT_ID as STUDENT_1_1_,student0_.ADDRESS_ID as ADD5_1_, student0_.FIRST_NAME as FIRST_NA2_1_, student0_.LAST_NAME as LAST_NAM3_1_, student0_.SECTION as SECTION4_1_ from STUDENT student0_

                 Student Details : Student [id=1, firstName=Mahesh, lastName=Patil, section=A, address=Address [id=1, street=#12, 12th E Main, Madiwala, city=Bangalore, country=India]]


Related Post:--
1) Advantages of Hibernate over JDBC
2) What are the Core Interfaces of Hibernate framework ?
3) Hibernate - JPA Annotations with explanation
4) Spring MVC with Hibernate CRUD Example

Wednesday 14 March 2018

Thread join() method example in Java

           Java Thread(java.lang.Thread) join method can be used to pause the current thread execution until unless the specified thread is dead.

            There are three overloaded join methods as follows,

  • join()

          This java thread join method puts the current thread on wait until the thread on which it’s called is dead. If the thread is interrupted, it throws InterruptedException.

  • join(long milisecond)

          This java thread join method is used to wait for the thread on which it’s called to be dead or wait for specified milliseconds. Since thread execution depends on OS 
implementation, it doesn’t guarantee that the current thread will wait only for given time.

  • join(long millisecond, int nanosecond)

          This java thread join method is used to wait for thread to die for given milliseconds 
plus nanoseconds.

join example,

JoinExample.java,

package com.practice;

public class JoinExample {
     
      public static void main(String[] args) {
            Thread t1 = new Thread(new MyClass(), "thread1");
            Thread t2 = new Thread(new MyClass(), "thread2");
            Thread t3 = new Thread(new MyClass(), "thread3");
         
            t1.start();
            try {
                t1.join();
            } catch (InterruptedException ex) {
            }
      
            t2.start();
            try {
                t2.join();
            } catch (InterruptedException ex) {
            }
      
            t3.start();   
            try {
                 t3.join();
            } catch (InterruptedException ie) {
            }  
      }
}
 
class MyClass implements Runnable{
 
    @Override
    public void run() {
      Thread t = Thread.currentThread();
         System.out.println("Thread started:- "+t.getName());
         try {
              Thread.sleep(1000);
         } catch (InterruptedException ex) {
              ex.printStackTrace();
         }
         System.out.println("Thread ended:- "+t.getName());
        
    }
}

Output:--Thread started:- thread1
                 Thread ended:- thread1
                 Thread started:- thread2
                 Thread ended:- thread2
                 Thread started:- thread3
                 Thread ended:- thread3


Related Post:--

Saturday 10 March 2018

Java Program to check the given Binary Tree is Binary Search Tree(BST) or not ?

           In Previous Post, discussed about the height of the BST(Binary Search Tree)  In this post, we can discuss to write the java code to validate the given Binary Tree is a BST or not.

           In a Binary Tree, each node can have at most two nodes. For a binary tree to be a binary search tree (BST), the data of all the nodes in the left sub-tree of the root node should be less than or equals to the data of the root. The data of all the nodes in the right sub tree of the root node should be greater than the data of the root.

BSTValidation.java,

package com.practice;

class Node {
 
      int data;
      Node leftChild;
      Node rightChild;
 
      public Node(int data) {
           this.data = data;
           leftChild = null;
           rightChild = null;
      }
}

public class BSTValidation {
      Node root;
      public boolean isBinarySearchTree() {
   
            if(root == null) return Boolean.TRUE;
            return isBstValid(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
      }
 
      private boolean isBstValid(Node node, Integer minValue, Integer maxValue) {
 
            if(node == null) return Boolean.TRUE;
            if(node.data >= minValue && node.data < maxValue
                  && isBstValid(node.leftChild, minValue, node.data)
                  && isBstValid(node.rightChild, node.data, maxValue)) {
                    return Boolean.TRUE;
            } else {
                    return Boolean.FALSE;
            }
      }
    
      public static void main(String[] args) {
               
             BSTValidation tree = new BSTValidation();
        
             // first example, valid binary search tree
             tree.root = new Node(48);
             tree.root.leftChild = new Node(22);
             tree.root.rightChild = new Node(61);
             tree.root.leftChild.leftChild = new Node(12);
             tree.root.leftChild.rightChild = new Node(28);
             tree.root.rightChild.leftChild = new Node(54);
             tree.root.rightChild.rightChild = new Node(68);
             System.out.println(tree.isBinarySearchTree());
     
             // second example, not a valid bst
     
             tree.root = new Node(48);
             tree.root.leftChild = new Node(22);
             tree.root.rightChild = new Node(100);
             tree.root.leftChild.leftChild = new Node(12);
             tree.root.leftChild.rightChild = new Node(28);
             tree.root.rightChild.leftChild = new Node(54);
             tree.root.rightChild.rightChild = new Node(68);
             System.out.println(tree.isBinarySearchTree());
      }
}

Output : true
               false


Related Post:
1) Program to find the height of Binary Search Tree(BST) in Java
2) Program to find maximum and minimum value from Binary Search Tree in Java
3) Java Program to delete a node from Binary Search Tree(BST)
4) Java Program to Count the number of nodes and leaf nodes of Binary Tree
5) How to Remove duplicates from ArrayList in Java

Monday 5 March 2018

Program to find the height of Binary Search Tree(BST) in Java

           In previous post, discussed about to max and min value of BST. In this post, we will see how to find the height of binary search tree.

          Height of binary tree is number of edges from root  node to deepest leaf node. Height of empty tree is 0.

See the below BST,  Height of BST is 4.
Height of Binary Search Tree
Height of Binary Search Tree

BSTHeightCalc.java, Using recursion

package com.practice;

class Node {
 
      int data;
      Node leftChild;
      Node rightChild;
 
      public Node(int data) {
           this.data = data;
           leftChild = null;
           rightChild = null;
      }
}

public class BSTHeightCalc {
 
      Node root;
 
      int calcBSTHeight() {
            return calcBSTHeight(root);
      }
 
      int calcBSTHeight(Node node) {
            if (node == null) {
                  return 0;
            }
  
            return Math.max(calcBSTHeight(node.leftChild), calcBSTHeight(node.rightChild))+1;
      }
 
      public static void main(String[] args) {
              BSTHeightCalc height = new BSTHeightCalc();
              height.root = new Node(18);
              height.root.leftChild = new Node(12);
              height.root.rightChild = new Node(28);
              height.root.leftChild.rightChild = new Node(32);
              System.out.println("Height of the BST:-"+height.calcBSTHeight());
      }
}

Output :--  Height of the BST:-3



Related post:--
1)  Program to find maximum and minimum value from Binary Search Tree in Java
2) Java Program to delete a node from Binary Search Tree(BST)
3) Java Program to Count the number of nodes and leaf nodes of Binary Tree
4) Java Program to Reverse a Linked List using Recursion and Loops

Friday 2 March 2018

Program to find maximum and minimum value from Binary Search Tree in Java

         In previous post, discussed about to delete a node from Binary Search Tree. In this post, we will see how to find the max and min value of binary search tree.

          Keep in mind :-- In a BST, the data of all the nodes in the left sub-tree of the root node should be less than or equals to the data of the root and the data of all the nodes in the right sub tree of the root node should be greater than the data of the root.

        In this program, to find the min value just you can traverse a node to left to the end, Same thing for the max value also. Traverse a node to right to the end.

See the below BST,
Min and Max value in BST
Minimum and Maximum value in BST


MaxMinBSTNode.java

package com.test;

public class Node {

        Integer data;
        Node leftChild;
        Node rightChild;
 
        public Node(Integer data) {
              this.data = data;
              leftChild = null;
              rightChild = null;
        }
}


public class MaxMinBSTNode {
 
        Node root;

        private Integer getMaxNode() {
               return getMaxNode(root);
        }
 
        private Integer getMinNode() {
               return getMinNode(root);
        }
 
        private Integer getMaxNode(Node node) {
  
               if (node.rightChild != null) {
                      return getMaxNode(node.rightChild);
               } 
               return node.data;
        }
 
        private Integer getMinNode(Node node) {
               if(node.leftChild != null) {
                      return getMinNode(node.leftChild);
               }
               return node.data;
        }
 
        public static void main(String[] args) {
  
                 MaxMinBSTNode tree = new MaxMinBSTNode();
                 tree.root = new Node(22);
                 tree.root.leftChild = new Node(10);
                 tree.root.rightChild = new Node(30);
                 tree.root.leftChild.leftChild = new Node(6);
                 tree.root.leftChild.rightChild = new Node(14);
                 tree.root.rightChild.leftChild = new Node(27);
                 tree.root.rightChild.rightChild = new Node(32);
  
                 System.out.println("Max value:--"+tree.getMaxNode());
                 System.out.println("Min value:--"+tree.getMinNode());
        }
}

Output:-- Max value:-- 32
                 Min value:--6


Related Post:--
1) Java Program to delete a node from Binary Search Tree(BST)
2) Java Program to Count the number of nodes and leaf nodes of Binary Tree
3) Java Program to Reverse a Linked List using Recursion and Loops
4) How to Remove duplicates from ArrayList in Java
5) Java Program to Count Occurrence of Word in a Sentence