Category Archives: Java

Mergesort using ArrayList in Java with example

So here is another sorting algorithm, “Merge Sort” which I have implemented it using ArrayList.

MergeSort follows the Divide and Conquer paradigm.

Divide part divides an unsorted array into 2 unsorted arrays till further division is not possible i.e there is only 1 element per array. So we need to divide an array of N element into N arrays of size 1 (Virtually).

Conquer part join 2 divided arrays into one array which is sorted. So we need to merge element from N array to 1 array having all element in sorted order.

Diving the array will take O(log n) time and will create log n level of sub arrays.
Conquer part at each level will merge 2 sorted arrays which takes O(n) at each level.
So worst case time taken by merge sort is O(n log n).
Merge sort is not considered to be a memory efficient as we need an extra memory at each level of merging. As you can see in the implementation example that is given here it needs an extra temporary array called : mergedSortedArray to store the temp sorted element.

Here is the source code and project structure for the MergeSort.

 

Project Structure

ProjectExporer

 

MergeSort.java

package daa;

import java.util.ArrayList;

public class MergeSort {
	private ArrayList<Integer> inputArray;
	
	public ArrayList<Integer> getSortedArray() {
		return inputArray;
	}

	public MergeSort(ArrayList<Integer> inputArray){
		this.inputArray = inputArray;
	}
	
	public void sortGivenArray(){		
		divide(0, this.inputArray.size()-1);
	}
	
	public void divide(int startIndex,int endIndex){
		
		//Divide till you breakdown your list to single element
		if(startIndex<endIndex && (endIndex-startIndex)>=1){
			int mid = (endIndex + startIndex)/2;
			divide(startIndex, mid);
			divide(mid+1, endIndex);		
			
			//merging Sorted array produce above into one sorted array
			merger(startIndex,mid,endIndex);			
		}		
	}	
	
	public void merger(int startIndex,int midIndex,int endIndex){
		
		//Below is the mergedarray that will be sorted array Array[i-midIndex] , Array[(midIndex+1)-endIndex]
		ArrayList<Integer> mergedSortedArray = new ArrayList<Integer>();
		
		int leftIndex = startIndex;
		int rightIndex = midIndex+1;
		
		while(leftIndex<=midIndex && rightIndex<=endIndex){
			if(inputArray.get(leftIndex)<=inputArray.get(rightIndex)){
				mergedSortedArray.add(inputArray.get(leftIndex));
				leftIndex++;
			}else{
				mergedSortedArray.add(inputArray.get(rightIndex));
				rightIndex++;
			}
		}		
		
		//Either of below while loop will execute
		while(leftIndex<=midIndex){
			mergedSortedArray.add(inputArray.get(leftIndex));
			leftIndex++;
		}
		
		while(rightIndex<=endIndex){
			mergedSortedArray.add(inputArray.get(rightIndex));
			rightIndex++;
		}
		
		int i = 0;
		int j = startIndex;
		//Setting sorted array to original one
		while(i<mergedSortedArray.size()){
			inputArray.set(j, mergedSortedArray.get(i++));
			j++;
		}
	}
}

 

MainPractise.java

 

import java.util.ArrayList;
import daa.MergeSort;

public class MainPractise implements Cloneable {	
	
	public static void main(String[] args) {		
		
		ArrayList<Integer> unsortedArray = new ArrayList<Integer>();
		
		unsortedArray.add(8);
		unsortedArray.add(7);
		unsortedArray.add(6);
		unsortedArray.add(5);
		unsortedArray.add(4);
		unsortedArray.add(0);
		unsortedArray.add(2);	
		MergeSort ms = new MergeSort(unsortedArray);
		
		System.out.println("---------Initial Unsorted Array---------");
		for(int i:ms.getSortedArray()){
			System.out.print(i+" ");
		}
		

		ms.sortGivenArray();
		
		System.out.println("\n------------Sorted Array------------");
		for(int i:ms.getSortedArray()){
			System.out.print(i+" ");
		}
	}
}

 

Output:

———Initial Unsorted Array———
8  7  6  5  4  0  2
————Sorted Array————
0  2  4  5  6  7  8

You can have above code from GIT.

GitHub-Mark-32px https://github.com/Niravkumar-Patel/SnippetExampleRepo.git


 

Selection Sort using ArrayList (Inplace) in Java

One more simple form of sorting algorithm is Selection Sort.

For in-place implementation in java, starting from 1st index, find the smallest element (takes O(n) ) and put it at the first index of unsorted sub array. So there will be 2 parts of main array, left one will have sorted element and right one will have unsorted. We choose smallest from the right one and will put it at the beginning of the unsorted sub array. Now Sorted array will have one more element and unsorted array will have one less. Continue this process till we reach the end of element. ( takes O(n)).
So finding smallest for one loop will take O(n) and there will be at most n loop so it total time in worst case will be O(n^2)

SelectionSort_ProjectStructure

 

SelectionSort.java

package daa;

import java.util.ArrayList;

public class SelectionSort {
	
	private ArrayList<Integer> inputArray = new ArrayList<Integer>();
	
	//Just To fetch display purpose
	public ArrayList<Integer> getSortedArray() {
		return inputArray;
	}

	public SelectionSort(ArrayList<Integer> inputArray){
		this.inputArray = inputArray;
	}	
	
	public void sortGivenArray(){
		
		int smallInt = 0;
		int j=0;
		int smallIntIndex = 0;		
		
		for(int i=1;i<inputArray.size();i++){
			
			smallInt = inputArray.get(i-1);
			smallIntIndex = i-1;
			
			for(j=i;j<inputArray.size();j++){
				if(inputArray.get(j)<smallInt){
					smallInt = inputArray.get(j);
					smallIntIndex = j;
				}
			}
		
			//Swap the smallest element with the first element of unsorted subarray
			swap(i-1, smallIntIndex);			
		}
	}
	
	public void swap(int sourceIndex,int destIndex){		
		int temp = inputArray.get(destIndex);
		inputArray.set(destIndex, inputArray.get(sourceIndex));
		inputArray.set(sourceIndex, temp);
	}

}

 

MainPractise.java

import java.util.ArrayList;
import daa.SelectionSort;

public class MainPractise implements Cloneable {	
	
	public static void main(String[] args) {		
		
		ArrayList<Integer> unsortedArray = new ArrayList<Integer>();
		
		unsortedArray.add(8);
		unsortedArray.add(7);
		unsortedArray.add(6);
		unsortedArray.add(5);
		unsortedArray.add(4);
		unsortedArray.add(0);
		unsortedArray.add(2);	
		SelectionSort ss = new SelectionSort(unsortedArray);
		
		System.out.println("---------Initial Unsorted Array---------");
		for(int i:ss.getSortedArray()){
			System.out.print(i+" ");
		}
		
		ss.sortGivenArray();
		
		System.out.println("\n------------Sorted Array------------");
		for(int i:ss.getSortedArray()){
			System.out.print(i+" ");
		}
	}
}

 

Output:

———Initial Unsorted Array———
8 7 6 5 4 0 2
————Sorted Array————
0 2 4 5 6 7 8

You can have above code from GIT.

GitHub-Mark-32px https://github.com/Niravkumar-Patel/SnippetExampleRepo.git


QuickSort implementation example using ArrayList in Java

So here is another sorting algorithm, “Quick Sort” which I have implemented it using ArrayList which is inplace sorting algorithm.
Worst case for quick sort to run is O (n^2).

Implementing Quick Sort using divide & conquer technique.
Our divide part will have partitioning of array into 2 array where each element from left side of array will be smaller then the each element from the right side of array. This partitioning will be based on one element that we choose in each iteration is called PIVOT element.

Our conquer part takes care of moving all element less than pivot at left and greater than pivot at right half of array and continue doing it recursively.

Below is the source code given with the project structure. And I have kept many System.out statement which is just for the understanding purpose. You may find it tedious but some time, for some people it might save time to understand the flow.

 

Project Structure:

QuickSort_projectStructure

 

QuickSort.java

package daa;

import java.util.ArrayList;
import java.util.Random;

public class QuickSort {
private static ArrayList<Integer> inputArray = new ArrayList<Integer>();
		
	public QuickSort(ArrayList<Integer> inputArray){
		QuickSort.inputArray = inputArray;
	}

	public void startQuickStart(int start,int end){
		int q;
		if(start<end){
			q = partition(start, end);
			startQuickStart(start, q);
			startQuickStart(q+1, end);
		}
	}

	public ArrayList<Integer> getSortedArray(){
		return QuickSort.inputArray;
	}

	int partition(int start,int end){
		System.out.println("\n---------Iteration Starts----------");
		System.out.println("\nSorting Window from index number:"+start+" to "+end);
		
		int init = start;
		int length = end;
		
		Random r = new Random();
		int pivotIndex = nextIntInRange(start,end,r);
		int pivot = inputArray.get(pivotIndex);
		
		System.out.println("Pivot Element "+pivot+" at index:"+pivotIndex);
				
		while(true){
			while(inputArray.get(length)>pivot && length>start){
				length--;
			}
			
			while(inputArray.get(init)<pivot && init<end){
				init++;
			}
			
			if(init<length){
				int temp;
				temp = inputArray.get(init);
				inputArray.set(init,inputArray.get(length));
				inputArray.set(length,temp);
				length--;
				init++;
				
				System.out.println("\nAfter Swapping");
				for(int i=start;i<=end;i++){
					System.out.print(inputArray.get(i)+" ");
				}
			}else{
				System.out.println("\n---------Iteration Ends---------");
				return length;
			}
		}
		
	}
	
	// Below method is to just find random integer from given range
	static int nextIntInRange(int min, int max, Random rng) {
		   if (min > max) {
		      throw new IllegalArgumentException("Cannot draw random int from invalid range [" + min + ", " + max + "].");
		   }
		   int diff = max - min;
		   if (diff >= 0 && diff != Integer.MAX_VALUE) {
		      return (min + rng.nextInt(diff + 1));
		   }
		   int i;
		   do {
		      i = rng.nextInt();
		   } while (i < min || i > max);
		   return i;
		}
}

 

MainPractise.java

import java.util.ArrayList;

import daa.QuickSort;


public class MainPractise implements Cloneable {	
	
	public static void main(String[] args) {
		
		ArrayList<Integer> unsortedArray = new ArrayList<Integer>();
		
		unsortedArray.add(2);
		unsortedArray.add(8);
		unsortedArray.add(6);
		unsortedArray.add(3);
		unsortedArray.add(12);
		unsortedArray.add(4);
		unsortedArray.add(7);
		
		QuickSort qsu = new QuickSort(unsortedArray);
		System.out.println("---------Initial Unsorted Array---------");
		for(int i:qsu.getSortedArray()){
			System.out.print(i+" ");
		}
		
		qsu.startQuickStart(0, unsortedArray.size()-1);
		
		
		System.out.println("\n\n---------Processed sorted Array---------");
		for(int i:qsu.getSortedArray()){
			System.out.print(i+" ");
		}
	}
}

 

 

Output:

 

———Initial Unsorted Array———
2 8 6 3 12 4 7
———Iteration Starts———-

Sorting Window from index number:0 to 6
Pivot Element 12 at index:4

After Swapping
2 8 6 3 7 4 12
———Iteration Ends———

———Iteration Starts———-

Sorting Window from index number:0 to 5
Pivot Element 8 at index:1

After Swapping
2 4 6 3 7 8
———Iteration Ends———

———Iteration Starts———-

Sorting Window from index number:0 to 4
Pivot Element 3 at index:3

After Swapping
2 3 6 4 7
———Iteration Ends———

———Iteration Starts———-

Sorting Window from index number:0 to 1
Pivot Element 3 at index:1

———Iteration Ends———

———Iteration Starts———-

Sorting Window from index number:0 to 1
Pivot Element 3 at index:1

———Iteration Ends———

———Iteration Starts———-

Sorting Window from index number:0 to 1
Pivot Element 2 at index:0

———Iteration Ends———

———Iteration Starts———-

Sorting Window from index number:2 to 4
Pivot Element 7 at index:4

———Iteration Ends———

———Iteration Starts———-

Sorting Window from index number:2 to 4
Pivot Element 4 at index:3

After Swapping
4 6 7
———Iteration Ends———

———Iteration Starts———-

Sorting Window from index number:3 to 4
Pivot Element 6 at index:3

———Iteration Ends———
———Processed sorted Array———
2 3 4 6 7 8 12

 
You can have above code from GIT.

GitHub-Mark-32px https://github.com/Niravkumar-Patel/SnippetExampleRepo.git


Binary Tree Insertion, Deletion, Search, Traversal in Java

Basic traversal on tree is best explained on http://en.wikipedia.org/wiki/Tree_traversal .

In Order:


binary_tree_inorder

 

Pre Order:

binary_tree_preorder

 

 

Post Order:

binary_tree_postorder

 

If anything is missing in explanation, you can google it and I know you all are expert as me.
Now my part starts from here.
How to implement it in java.

Project Structure in Eclipse:

Tree_projectStructure

Node.java    (nodeInfo variable has no logical meaning, it is just for printing purpose)

package datastructure.tree;

public class Node {
	
	private Node leftNode;
	private Node rightNode;
	private int nodeValue;
	private String nodeInfo;
	
	public Node(String nodeInfo,int nodeValue){
		this.nodeInfo = nodeInfo;
		this.nodeValue = nodeValue;
	}
	
	public Node getLeftNode() {
		return leftNode;
	}
	public void setLeftNode(Node leftNode) {
		this.leftNode = leftNode;
	}
	public Node getRightNode() {
		return rightNode;
	}
	public void setRightNode(Node rightNode) {
		this.rightNode = rightNode;
	}
	public int getNodeValue() {
		return nodeValue;
	}
	public void setNodeValue(int nodeValue) {
		this.nodeValue = nodeValue;
	}
	public String getNodeInfo() {
		return nodeInfo;
	}
	public void setNodeInfo(String nodeInfo) {
		this.nodeInfo = nodeInfo;
	}
}

 

Tree.java

package datastructure.tree;

public interface Tree {

	void insertNode(Node node);
	void deleteNode(Node node);
	Node searchNode(Node node);
	
	void inOrderTraversal(Node node);
	void preOrderTraversal(Node node);
	void postOrderTraversal(Node node);
}

 

TreeImpl.java

 

package datastructure.tree;

public class TreeImpl implements Tree{

	int tree_node_count = 0;
	public Node rootNode = null;
	
	public Node getRootNode() {
		return rootNode;
	}

	public void setRootNode(Node rootNode) {
		this.rootNode = rootNode;
	}

	public TreeImpl(Node rootNode){
		this.rootNode = rootNode;
		tree_node_count = 1;
	}

	@Override
	public void insertNode(Node node){
		Node treeNode = rootNode;
		
		while(true){
			if(node.getNodeValue()<treeNode.getNodeValue()){
				if(treeNode.getLeftNode()!=null){
					treeNode = treeNode.getLeftNode();
				}else{
					treeNode.setLeftNode(node);
					System.out.println("Node "+node.getNodeValue()+" saved at left child of node :"+treeNode.getNodeValue());
					break;
				}
			}else if(node.getNodeValue()>treeNode.getNodeValue()){
				if(treeNode.getRightNode()!=null){
					treeNode = treeNode.getRightNode();
				}else{
					treeNode.setRightNode(node);
					System.out.println("Node "+node.getNodeValue()+" saved at Right child of node :"+treeNode.getNodeValue());
					break;
				}
			}else{
				System.out.println("Duplicate Node can not be saved");
				break;
			}
		}
	}
	
	@Override
	public Node searchNode(Node node){
		Node currentNode = rootNode;
		while(currentNode!=null){
			if(currentNode.getNodeValue()==node.getNodeValue()){
				System.out.println("Node "+node.getNodeValue()+" Found");
				return currentNode;
			}else{
				if(node.getNodeValue()<currentNode.getNodeValue()){
					currentNode = currentNode.getLeftNode();
				}else{
					currentNode = currentNode.getRightNode();
				}
			}
		}
		System.out.println("Node "+node.getNodeValue()+" Not Found");
		return null;
	}


	@Override
	public void deleteNode(Node node) {
		Node previousNode =  null;
		Node currentNode = rootNode;
		
		if(node.getNodeValue()==currentNode.getNodeValue()){
			System.out.println("Your Tree is Vanished");			
		}else if(node.getNodeValue()<currentNode.getNodeValue()){
			previousNode = currentNode;
			currentNode = currentNode.getLeftNode();
		}else{
			previousNode = currentNode;
			currentNode = currentNode.getRightNode();
		}
		
		while(true){
			if(node.getNodeValue()==currentNode.getNodeValue()){
				
				
				if(currentNode.getRightNode()!=null){
					Node tempPreviousNode = currentNode;
					Node tempNode = currentNode.getRightNode();
					
					if(tempNode.getLeftNode()!=null){
						while(tempNode.getLeftNode()!=null){
							tempPreviousNode = tempNode;
							tempNode = tempNode.getLeftNode();
						}
						
						if(tempNode.getRightNode()!=null){
							tempPreviousNode.setLeftNode(tempNode.getRightNode());
							previousNode.setRightNode(tempNode);
							tempNode.setLeftNode(currentNode.getLeftNode());
							break;
						}else{
							tempNode.setLeftNode(currentNode.getLeftNode());
							tempNode.setRightNode(currentNode.getRightNode());
							previousNode.setRightNode(tempNode);
							tempPreviousNode.setLeftNode(null);
							break;
						}
					}else{
						tempNode.setLeftNode(currentNode.getLeftNode());
						previousNode.setRightNode(tempNode);
						break;
					}					
				}else if(currentNode.getLeftNode()!=null){
					previousNode.setLeftNode(currentNode.getLeftNode());
					currentNode = null;
					break;
				}else{
					currentNode = null;
					break;
				}				
			}else if(node.getNodeValue()<currentNode.getNodeValue()){
				previousNode = currentNode;
				currentNode = currentNode.getLeftNode();
			}else{
				previousNode = currentNode;
				currentNode = currentNode.getRightNode();
			}
		}
	}

	@Override
	public void inOrderTraversal(Node node) {
	
		if(node!=null){
			inOrderTraversal(node.getLeftNode());
			System.out.println("Node Value:"+node.getNodeValue());
			inOrderTraversal(node.getRightNode());
		}
	}

	@Override
	public void preOrderTraversal(Node node) {
		// TODO Auto-generated method stub
		if(node!=null){
			System.out.println("Node Value:"+node.getNodeValue());
			preOrderTraversal(node.getLeftNode());
			
			preOrderTraversal(node.getRightNode());
		}
	}

	@Override
	public void postOrderTraversal(Node node) {
		// TODO Auto-generated method stub
		if(node!=null){
			postOrderTraversal(node.getLeftNode());
			
			postOrderTraversal(node.getRightNode());
			System.out.println("Node Value:"+node.getNodeValue());
		}
	}
}

MainPractise,java

import datastructure.tree.Node;
import datastructure.tree.TreeImpl;



public class MainPractise implements Cloneable{	
	
	public static void main(String[] args) {
		
		Node node = new Node("Root Node",12);
		
		TreeImpl ti = new TreeImpl(node);
		
		Node leafNode = new Node("Leaf Node",5);
		ti.insertNode(leafNode);
		
		leafNode = new Node("Leaf Node",16);
		ti.insertNode(leafNode);
		
		leafNode = new Node("Leaf Node",2);
		ti.insertNode(leafNode);
		
		leafNode = new Node("Leaf Node",1);
		ti.insertNode(leafNode);

		leafNode = new Node("Leaf Node",3);
		ti.insertNode(leafNode);
		
		leafNode = new Node("Leaf Node",15);
		ti.insertNode(leafNode);

		leafNode = new Node("Leaf Node",19);
		ti.insertNode(leafNode);

		leafNode = new Node("Leaf Node",18);
		ti.insertNode(leafNode);
		
		Node deleteNode = new Node("Leaf Node",16);
		ti.deleteNode(deleteNode);
		
		System.out.println("==============In Order Traversal===================");
		ti.inOrderTraversal(ti.getRootNode());
		System.out.println("==============Pre Order Traversal==================");
		ti.preOrderTraversal(ti.getRootNode());
		System.out.println("==============Post Order Traversal=================");
		ti.postOrderTraversal(ti.getRootNode());
		
		
		System.out.println("===================================================");
		Node searchNode = new Node("Leaf Node", 17);
		ti.searchNode(searchNode);
		
		searchNode = new Node("Leaf Node", 3);
		ti.searchNode(searchNode);
       }
}

 

 

Output:

Node 5 saved at left child of node :12
Node 16 saved at Right child of node :12
Node 2 saved at left child of node :5
Node 1 saved at left child of node :2
Node 3 saved at Right child of node :2
Node 15 saved at left child of node :16
Node 19 saved at Right child of node :16
Node 18 saved at left child of node :19
==============In Order Traversal===================
Node Value:1
Node Value:2
Node Value:3
Node Value:5
Node Value:12
Node Value:15
Node Value:18
Node Value:19
==============Pre Order Traversal==================
Node Value:12
Node Value:5
Node Value:2
Node Value:1
Node Value:3
Node Value:18
Node Value:15
Node Value:19
==============Post Order Traversal=================
Node Value:1
Node Value:3
Node Value:2
Node Value:5
Node Value:15
Node Value:19
Node Value:18
Node Value:12
===================================================
Node 17 Not Found
Node 3 Found

 

I haven’t defined any methods of isEmpty() and as such methods. So if you need one let me know.

You can have above code from GIT.

GitHub-Mark-32px https://github.com/Niravkumar-Patel/SnippetExampleRepo.git

String Operations

1.Reverse string using loop

2. Reverse string using iterator

3. Check whether string is palindrome or not

 

Below is my project explorer setup:

StringOperationProjectExplorer


package stringOperation;

public class StringOperation {

	// Reverse String using Iteration
	public String reverString(String str){
		StringBuilder reverseString = new StringBuilder();
		
		int i = str.length();
		while(i>0){
			i--;
			reverseString.append(str.charAt(i));
		}
		
		return reverseString.toString();
	}
		
	// Reverse String using Recursion
	public String reverseStringWithRecursion(String str) {

        //last element of string
        if (str.length() == 1) {
            return str;
        }

        return reverseStringWithRecursion(str.substring(1)) + str.charAt(0);
    }
	
	//Check whether given String is palindrom or not
	public boolean checkPalindrome(String str){
		int j = str.length();
		boolean flag = true;
		for(int i=0;i<j/2;i++){
			if(str.charAt(i) == str.charAt(j-1-i)){
				continue;
			}else{
				flag = false;
				break;
			}
		}
		return flag;
	}	
	
}

import stringOperation.StringOperation;



public class MainPractise {

	public static void main(String[] args) {
		
		String str = "I want you to reverse me";
		StringOperation so = new StringOperation();
		System.out.println("With Loop     :"+so.reverString(str));
		System.out.println("With Recursion:"+so.reverseStringWithRecursion(str));
		
		str = "Not PP toN";
		System.out.println(so.checkPalindrome(str));
		
		str = "I am not palindrome";
		System.out.println(so.checkPalindrome(str));;
		
	}
}

Output:

With Loop :em esrever ot uoy tnaw I
With Recursion:em esrever ot uoy tnaw I
true
false

You can have above code from GIT.

GitHub-Mark-32px https://github.com/Niravkumar-Patel/SnippetExampleRepo.git


Insertion Sort implementation in Java

One of the simplest (in terms of understanding :P) sorting technique is Insertion Sort.
You will find many sites giving example of cards. Like suppose left hand has already sorted cards where as right hand has unsorted. You can pick first card from right hand unsorted and try to put it in left hand so that the sorted order preserves in left hand.

Suppose you never played card in your life (means you wasted your childhood 😛 ).
You can also think of 2 queue of people ( A and B). In queue A, all the people are standing in incremental order of their height and in queue B, no one gives a shit about any order. Now suppose a person P from queue B is tired of those people and wants to join queue A. So when he join queue A, he has to start from the person who is standing last and find a position so that the order of height preserves. In this process all the people from queue A who are taller than P, has to shift their place one step back.

Now lets implement this in java using ArrayList.

My project Explorer:

 

InsertionSortProjectExplorer

 

InsertionSort.java

package daa;

import java.util.ArrayList;

public class InsertionSort {	

	private static ArrayList<Integer> inputArray = new ArrayList<Integer>();

	public static ArrayList<Integer> getInputArray() {
		return inputArray;
	}

	//Just for the display purpose
	public InsertionSort(ArrayList<Integer> inputArray){
		InsertionSort.inputArray = inputArray;
	}
	
	public void sortGivenArray(){					
		for(int i=1;i<inputArray.size();i++){
			
			int key = inputArray.get(i);
			
			for(int j= i-1;j>=0;j--){
				if(key<inputArray.get(j)){
					// Shifting Each Element to its right as key is less than the existing element at current index
					inputArray.set(j+1,inputArray.get(j));
					
					// Special case scenario when all elements are less than key, so placing key value at 0th Position
					if(j==0){
						inputArray.set(0, key);
					}
				}else{
					// Putting Key value after element at current index as Key value is no more less than the existing element at current index
					inputArray.set(j+1,key);
					break; // You need to break the loop to save un necessary iteration
				}
			}
		}		
	}
}

 

 

MainPractise.java

import java.util.ArrayList;

import daa.InsertionSort;


public class MainPractise implements Cloneable {	
	
	public static void main(String[] args) {
		
		
		ArrayList<Integer> unsortedArray = new ArrayList<Integer>();
		
		unsortedArray.add(8);
		unsortedArray.add(7);
		unsortedArray.add(6);
		unsortedArray.add(5);
		unsortedArray.add(4);
		unsortedArray.add(0);
		unsortedArray.add(2);	
		InsertionSort is = new InsertionSort(unsortedArray);
		
		System.out.println("---------Initial Unsorted Array---------");
		for(int i:InsertionSort.getInputArray()){
			System.out.print(i+" ");
		}
		
		is.sortGivenArray();
		
		System.out.println("\n------------Sorted Array------------");
		for(int i:InsertionSort.getInputArray()){
			System.out.print(i+" ");
		}
        }
}

 

Output:

———Initial Unsorted Array———
8 7 6 5 4 0 2
————Sorted Array————
0 2 4 5 6 7 8

You can have above code from GIT.

GitHub-Mark-32px https://github.com/Niravkumar-Patel/SnippetExampleRepo.git

If you have any question mail us on
snippetexample@gmail.com or Post comments or join us on facebook.


Stack implementation using Array

Stack is an abstract data type.
Basic operation of stack can be:

1. Push :
Push object on top of stack.
Throw exception if stack is full.

2. Pop :
Take out(remove) object that is on top of stack .
Throw exception if stack is empty.

3. Top:
Read the object that is on top of stack.
Throw exception if stack is empty.

Now we need to implement these all operation in Java using Object Array.

Below is my eclipse folder structure. You may find this common but keeping all beginners in mind so please bare with me.

ArrayStack

Lets define an interface for a stack:

package datastructure.stack;

public interface Stack {

	//accessor method stack
	public int size();
	public boolean isEmpty();
	public Object top() throws Exception;
	
	//update method stack
	public void push(Object element) throws Exception;
	public Object pop() throws Exception;
}

 

 

 

Now we need to implement these functionality. So will be implementing this interface by our class called ArrayStack.java.

package datastructure.stack;

public class ArrayStack implements Stack {
	
	private Object stack[];
	private int capacity;
	private int currentPos=-1;
	
	public ArrayStack(int capacity){
		this.capacity = capacity;
		stack = new Object[capacity];
	}

	@Override
	public int size() {
		// TODO Auto-generated method stub
		return this.capacity;
	}

	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		if(currentPos<0){
			return true;
		}
		return false;
	}

	@Override
	public Object top() throws Exception {
		// TODO Auto-generated method stub	
		if(currentPos<0){
			throw new Exception(" Stack is Empty");
		}
		return stack[currentPos];
	}

	@Override
	public void push(Object element) throws Exception {
		// TODO Auto-generated method stub
		if(currentPos==capacity){
			throw new Exception();
		}
		stack[++currentPos] = element;
	}

	@Override
	public Object pop() throws Exception {
		// TODO Auto-generated method stub
		if(currentPos<0){
			throw new Exception();
		}
		return stack[currentPos--] = null;
	}

}

 

 

As you can see in the ArrayStack.java,
we define constructor to initialize the size of our stack. This size will set the limit on number of element in stack.
So let me just briefly explain about class variable and methods.

Object stack[] : An array which is going to be our stack(element holder)
int capacity : Max size of Stack
int currentPos : It is pointer of top element of stack. We will need to increment it when any element is pushed, decrement it when we do the pop operation. Initially we kept it -1 as first element will have index 0. So if there is no element it should be -1.

public int size()                                 : Gives you the capacity of Stack, which was set at the time of initialization.
public boolean isEmpty()                : Gives you true/false based on currentPos pointer.
public Object top()                            : Return the object that is there on top of stack. It does not remove it. And if there is no element that it will                                                                        throw exception.
public void push(Object element) :  Push the object specified as the parameter. If stack is full than it will throw exception.
public Object pop()                           :  Remove the element that is there on top of stack. If stack is empty it will throw the exception.

So thats all everyone. Below is some basic operation that I ran and the output of it.

import datastructure.stack.ArrayStack;

public class MainPractise {

	public static void main(String[] args) {		
		
		ArrayStack as = new ArrayStack(10);  // Stack can have at max 10 element
		try{
			System.out.println("Stack size:"+as.size());
			as.push("Nirav"); // push String object in stack
			as.pop(); // pop Nirav out of stack 🙁
			as.push("Nihar");
			String topString = (String)as.top(); // chek out nihar 😛
			System.out.println(topString); /* U will see stubborn nihar string object 
			                                print out bt the object will still be there */
			
			as.pop(); // Now There is no element in stack
			as.pop(); // it will throw exception as stack is empty
		}catch(Exception e){
			System.out.println("Exception message:"+e.getMessage());
		}
		
	}
}

The output of above code is:

Stack size:10
Nihar
Exception message:Stack is Empty

This is it.

You can have above code from GIT.

GitHub-Mark-32px https://github.com/Niravkumar-Patel/SnippetExampleRepo.git

If you have any question mail us on
snippetexample@gmail.com or Post comments or join us on facebook.