Java Program to Implement Selection Sort

          In the previous post, we implemented the Bubble Sort algorithm. In this post, we will implement the Selection Sort algorithm and discuss its time complexity.

Selection Sort is a simple comparison-based sorting algorithm. It works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the array and placing it in its correct position. In each pass, the unsorted portion of the array becomes smaller, while the sorted portion grows.

The algorithm performs n − 1 passes for an array containing n elements. During each pass, the inner loop finds the smallest (or largest) element in the unsorted portion of the array, and the outer loop swaps it with the first unsorted element, placing it in its correct position.

The following example illustrates how the Selection Sort algorithm works with the help of a diagram.

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 smallest element requires scanning all n elements, which takes n − 1 comparisons. The selected element is then swapped with the first element in the array.

Finding the next smallest element requires scanning the remaining n − 1 elements, and the process continues until the array is completely sorted.

The total number of comparisons is:

(n − 1) + (n − 2) + ... + 2 + 1
= n(n − 1) / 2
= O(n²)

Time Complexity

• Best Case: O(n²)

• Average Case: O(n²)

• Worst Case: O(n²)

Note: Although both Selection Sort and Bubble Sort have a time complexity of O(n²), Selection Sort is generally more efficient because it performs significantly fewer swaps. Selection Sort makes at most n − 1 swaps, whereas Bubble Sort may perform many more swaps, resulting in higher overhead.

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

Hibernate One-to-One Mapping Example Using Annotations

               In the previous post, we learned about Hibernate Annotations with detailed explanations. In this post, we will learn what a one-to-one relationship is in Hibernate and how to implement it using annotations.

To demonstrate this relationship, we will use two entity classes, Student and Address, and establish a one-to-one association between them.

In this example, we will implement the one-to-one relationship using a foreign key association. Another way to implement a one-to-one relationship is by using a primary key association with the @PrimaryKeyJoinColumn annotation.

In the example below, the Student table contains a foreign key column (address_id) that references the primary key (address_id) of the Address table.

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)
);

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 + "]";
        }
 
}

Create Hibernate Configuration file:-

           We need to configure Hibernate with the database connection details and specify the database dialect so that Hibernate can generate SQL statements specific to the selected database.

We define all of this configuration in the hibernate.cfg.xml file. Create this file with the following content and save it in the 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 – Specifies the database dialect that Hibernate uses to generate SQL statements specific to the selected database.

• driver_class – Specifies the JDBC driver class that Hibernate uses to establish a connection to the database.

• show_sql – Instructs Hibernate to log all generated SQL statements to the console.

• format_sql – Instructs Hibernate to format the generated SQL statements, making them easier to read.

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 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

Java Thread join() Method with Examples

           The join() method of the java.lang.Thread class is used to pause the execution of the current thread until the specified thread has finished executing.

The Thread class provides the following three overloaded join() methods:

• 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:--

1) Producer Consumer Problem - Solution using wait and notify In Java

2) Difference between the Runnable and Callable interface in Java

3) How many ways to create a thread in Java? Which one Prefer and why?

4) Explain Thread life cycle and difference between wait() and sleep() method.

5) Producer Consumer Problem - Solution using BlockingQueue in Java

Java Program to Check Whether a Binary Tree Is a Binary Search Tree (BST)

           In the previous post, we discussed the height of a Binary Search Tree (BST). In this post, we will learn how to write a Java program to validate whether a given binary tree is a Binary Search Tree (BST).

In a binary tree, each node can have at most two child nodes. For a binary tree to qualify as a Binary Search Tree (BST), the following conditions must be satisfied:

• All nodes in the left subtree of a node must have values less than or equal to the value of that node.

• All nodes in the right subtree of a node must have values greater than the value of that node.

If every node in the tree satisfies these conditions, then the binary tree is a valid Binary Search Tree (BST).

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

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

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

Java Program to Find the Maximum and Minimum Values in a Binary Search Tree (BST)

          In the previous post, we discussed how to delete a node from a Binary Search Tree (BST). In this post, we will learn how to find the minimum and maximum values in a Binary Search Tree.

Keep in mind: In a BST, the value of every node in the left subtree is less than or equal to the value of the root node, and the value of every node in the right subtree is greater than the value of the root node.

To find the minimum value in a BST, simply traverse the left child of each node until you reach the leftmost node. The leftmost node contains the minimum value.

Similarly, to find the maximum value, traverse the right child of each node until you reach the rightmost node. The rightmost node contains the maximum value.

Consider the following 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