Uses Divide and Conquer strategy like QuickSort. It divides the array of numbers into sub-arrays (from middle) until there is only one element in each sub-array. These sub-arrays are then merged into sorted sub-arrays until we obtain a sorted merged array. Stable Best Case Time Complexity: O(n log n) Worst Case Time Complexity: O(n log n) Space Complexity: O(n) public class MergeSortInJava { void sort(int arr[], int l, int r) { if (l < r) { // Find mid int m = (l+r)/2; // Sort first and second halves with recursion sort(arr, l, m); sort(arr , m+1, r); // Merging ...
Read more
Divide and Conquer Strategy Space required is less as compared to other sorting algorithms Not Stable Best Case Time Complexity: O(n log n) Worst Case Time Complexity: O(n^2) Space Complexity: O(n log n) class QuickSortInJava { /* The main function that implements QuickSortInJava() arr[] --> Array to be sorted, low --> Starting index (min. is 0), high --> Ending index (max. is n-1)*/ void sort(int arr[], int low, int high) { if (low < high) { /* correctPivotPos is index of pivot at its correct position i.e. arr[correctPivotPos] */ int correctPivotPos = partition(arr, low, high); // Recursively sort numbers sort(arr, ...
Read more
0,1,…, n-1 index numbers are exchanged with smallest number from index numbers: 1,2,…,n Best Case Time Complexity: O(n^2) Worst Case Time Complexity: O(n^2) Space Complexity: O(1) Stable public class SelectionSortInJava { public static void SelectionSort(int[] arr){ for (int i = 0; i < arr.length - 1; i++) // excludes last element { int index = i; for (int j = i + 1; j < arr.length; j++){ // excludes first element if (arr[j] < arr[index]){ // find index of element smaller than key && smallest in the group of numbers to the right of key index = j; // searching ...
Read more
Sorts by shifting elements. All, but first element, are made as key once. Efficient for sorting few numbers. Insertion Sort is better than Selection Sort and Bubble Sort. Stable i.e. order of same numbers is maintained. /* 1. All elements other than 1st are considered as key 2. The key is compared with all previous elements until key is put at right place */ //Best Case: O(n) //Worst Case: O(n^2) //Space Complexity : O(1) public class InsertionSortInJava { public static void InsertionSort(int array[]) { int n = array.length; for (int j = 1; j < n; j++) { int key ...
Read more
Header: java.util.LinkedList<E> (where E denotes the type of elements in the collection) Some of the useful methods: addFirst(E e) addLast(E e) clear() clone() – returns a shallow copy of the Linked List contains(Object o) – returns true if list contains the object get(int position) getFirst() getLast() indexOf(Object o) remove() – retrieves and removes the head of the list remove(Object o) – removes first occurrence of the object o. removeFirst() removeLast() set(int position, E e) size() toArray() EXAMPLE import java.util.*; import java.io.*; class Book { int id; String name; public Book(int id, String name) { this.id = id; this.name = name; } ...
Read more
//************************* Manager.java ************************* public class Manager extends Employee { public Manager(int empId, String empName) { super(empId, empName); } public void salary(){} public void bonus(){} } //************************* Employee.java ************************* public class Employee { //Run Time Type Info int empId; String empName; public Employee(int empId, String empName) { this.empId = empId; this.empName = empName; } public void fun(){} public void test(){} @Override public String toString() { return "ID: " + empId + " Employee Name: "+empName ; } } //************************* Main.java ************************* import java.lang.reflect.Method; public class Main { public static void main(String[] args) { Employee employee1 = new Employee(111, "Patrick"); System.out.println(employee1); Employee ...
Read more
public class singleton { private static singleton obj; private singleton(){ System.out.println("Constructor is called only once."); } public static singleton getInstance(){ if(obj == null){ obj = new singleton(); } return obj; } public int add(int i, int j){ return (i + j); } public int sub(int i, int j){ return (i-j); } public static void main( String [] args){ singleton obj1 = singleton.getInstance(); singleton obj2 = singleton.getInstance(); singleton.getInstance(); singleton.getInstance(); singleton.getInstance(); // 'n' number of object creation won't call constructor 'n' times. This is singleton feature. System.out.println(singleton.getInstance().add(5, 6)); //it is object.function() call } } Output: Constructor is called only once. 11 View ...
Read more
//******************* Shape.java ******************* public class Shape { private int x; private int y; private String color; private String shape; Shape(){ //This is needed to be defined since we are going to work with inheritance x = 0; y = 0; color = " "; shape = "polygon"; } Shape(int x, int y, String color, String shape){ this.x = x; this.y = y; this.color = color; this.shape = shape; } public int getXCoordinate(){ return this.x; } public void setXCoordinate(int x){ this.x = x; } public int getYCoordinate(){ return this.y; } public void setYCoordinate(int y){ this.y = y; } public String getColor() ...
Read more
//******************* Vehicle.java ******************* public class Vehicle { private String PNo; private int CNo; Vehicle(){ System.out.println("Vehicle() "); PNo = "NA"; CNo = 0; } Vehicle(String PNo, int CNo){ System.out.println("Vehicle( String, int ) "); this.PNo = PNo; this.CNo = CNo; } public String getPNo(){ return this.PNo; } public void setPNo(String PNo){ this.PNo = PNo; } public int getCNo(){ return this.CNo; } public void setCNo(int CNo){ this.CNo = CNo; } } //******************* Car.java ******************* public class Car extends Vehicle{ private int type; private String color; Car(){ System.out.println(" Car() "); type = 0; color = "NA"; } Car(String PNo, int CNo, String color , ...
Read more
//******************* Employee.java ******************* public class Employee { private int ID; private int Salary; private String Name; public Employee(int ID, int Salary, String Name) throws NegativeSalaryException { this.ID = ID; this.Name = Name; if(Salary<0) throw new NegativeSalaryException(Salary, "You have entered negative salary"); this.Salary = Salary; } @Override public String toString() { // TODO Auto-generated method stub return "Name: "+ Name + " ID: "+ ID + " Salary: "+ Salary; } } //******************* Main.java ******************* public class Main { public static void main(String[] args) throws NegativeSalaryException { Employee employee = new Employee(111, -1000, "Pratik"); System.out.println(employee); } } //******************* NegativeSalaryException.java ******************* public ...
Read more