Sorting algorithms in java array

Sorting algorithms in java array
There are many sorting algorithms in data structures world each having their own pros and cons.
let's see how these searching algorithms can be implemented in Java using arrays. 
Below are the implemented searching algorithms  in the below example code.

  •     Implement bubble sort in java.
  •     Implement selection sort in java.
  •     Implement insertion sort in java.
  •     Implement quick sort in java.
  •     Implement merge sort in java.
Sorting class code : 

package com.krish.sorting;

import java.util.Random;

public class SortingTechniques {
 // Applies selection sort technique to the given array
 public static int[] doSelectionSort(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 smallerNumber = arr[index];
   arr[index] = arr[i];
   arr[i] = smallerNumber;
  }
  return arr;
 }

 // Applies bubble sort technique to the given array
 public static int[] doBubbleSort(int[] arr) {
  int n = arr.length;
  int k;
  for (int m = n; m >= 0; m--) {
   for (int i = 0; i < n - 1; i++) {
    k = i + 1;
    if (arr[i] > arr[k]) {
     swapNumbers(i, k, arr);
    }
   }
  }
  return arr;

 }

 // Applies Insertion sorting Technique
 public static int[] doInsertionSort(int[] arr) {
  int temp;
  for (int i = 1; i < arr.length; i++) {
   for (int j = i; j > 0; j--) {
    if (arr[j] < arr[j - 1]) {
     temp = arr[j];
     arr[j] = arr[j - 1];
     arr[j - 1] = temp;
    }
   }
  }
  return arr;
 }

 // Applies Quick sort to the given array
 public static void doQuickSort(int lowerIndex, int higherIndex,int[] myArray) {
  int i = lowerIndex;
  int j = higherIndex;
  // calculate pivot number, I am taking pivot as middle index number
  int pivot = myArray[lowerIndex + (higherIndex - lowerIndex) / 2];
  // Divide into two arrays
  while (i <= j) {
   /**
    * In each iteration, we will identify a number from left side which
    * is greater then the pivot value, and also we will identify a
    * number from right side which is less then the pivot value. Once
    * the search is done, then we exchange both numbers.
    */
   while (myArray[i] < pivot) {
    i++;
   }
   while (myArray[j] > pivot) {
    j--;
   }
   if (i <= j) {
    exchangeNumbers(i, j,myArray);
    // move index to next position on both sides
    i++;
    j--;
   }
  }
  // call quickSort() method recursively
  if (lowerIndex < j)
   doQuickSort(lowerIndex, j,myArray);
  if (i < higherIndex)
   doQuickSort(i, higherIndex,myArray);
 }

 private static void exchangeNumbers(int i, int j,int[] myArray) {
  int temp = myArray[i];
  myArray[i] = myArray[j];
  myArray[j] = temp;
 }

 private static void swapNumbers(int i, int k, int[] arr) {
  int temp;
  temp = arr[i];
  arr[i] = arr[k];
  arr[k] = temp;
 }

 public static void printArray(int[] printArray) {
  for (int i : printArray) {
   System.out.print(i);
   System.out.print(", ");
  }
 }

 private static int[] getRandomNumbersArray() {
  Random myRandom = new Random();
  int[] randomArray = { myRandom.nextInt(100), myRandom.nextInt(20),
    myRandom.nextInt(600), myRandom.nextInt(60),
    myRandom.nextInt(200) };
  return randomArray;
 }

 public static void main(String[] args) {

  int[] myArray = getRandomNumbersArray();
  System.out.println("\nBefore Selection sort:");
  printArray(myArray);
  System.out.println("\nAfter Selection sort:");
  printArray(doSelectionSort(myArray));
  
  myArray = getRandomNumbersArray();
  System.out.println("\nBefore Bubble sort:");
  printArray(myArray);
  System.out.println("\nAfter Bubble sort:");
  printArray(doSelectionSort(myArray));
  
  myArray = getRandomNumbersArray();
  System.out.println("\nBefore Insertion sort:");
  printArray(myArray);
  System.out.println("\nAfter Insertion sort:");
  printArray(doSelectionSort(myArray));
  myArray = getRandomNumbersArray();
  
  System.out.println("\nBefore Quick sort:");
  printArray(myArray);
  int length = myArray.length;
  doQuickSort(0, length - 1,myArray);
  System.out.println("\nAfter Quick sort:");
  printArray(myArray);
 }
}

 Output : 

Before Selection sort:
10, 0, 480, 41, 175,
After Selection sort:
0, 10, 41, 175, 480,
Before Bubble sort:
77, 3, 91, 4, 8,
After Bubble sort:
3, 4, 8, 77, 91,
Before Insertion sort:
35, 14, 41, 24, 168,
After Insertion sort:
14, 24, 35, 41, 168,
Before Quick sort:
6, 9, 188, 21, 102,
After Quick sort:
6, 9, 21, 102, 188,

References : [1][2]

Read more


Queue implementation using linked list in Java

Queue implementation using linked list in Java
Queue is another famous data structure which allows operating from two ends(front and rear) through head and tail. It works in First In First Out(FIFO) fashion.
Queue data structure is like two ended room which allows entry(enqueue) from one end called as rear and exit (dequeue) from another end called a front...
So to remember , queue always supports insertion from rear-end / tail and deletion called as dequeue happens only from fron end / head.

Let's see how can we implement simple Queue data structure in Java using a single linked list. 

We need follow the Cell class we have used in the Stack example in the previous post.

Queue main class : 
package com.krish.queue;

import com.krish.datastructures.common.Cell;

public class QueueMain {
 Cell head;
 Cell tail;

 public QueueMain() {
  head = null;
  tail = null;
 }

 public void enqueue(Object obj) {
  Cell newCell = new Cell(obj, null);
  if (head == null && tail == null)
   head = newCell;
  else
   tail.next = newCell;
  tail = newCell;
  System.out.println("Enqueud element:"+obj);
  printQueue();
 }

 public Cell front() {
  return head;
 }

 public Cell rear() {
  return tail;
 }

 public void dequeue() {
  if (head == null && tail == null) {
   System.out.println("Q is empty");
  } else {
   System.out.println("Dequeued element:"+head.getVal());
   if (head.next == null) {
    tail = null;
   }
   head = head.next;
  }
  printQueue();
 }

 public int getsize() {
   int size = 0;
  if(!(head ==null && tail == null)){
     size = 1;
     for(Cell n = head; n.next != null; n = n.next)
         size = size+1; 
  
     return size;
  }
  return size;
  }

 public void printQueue() {
  if (head == null && tail == null) {
   System.out.println("Q is empty");
  } else {
   System.out.println("Q Elememts:");
   Cell current = head;
   System.out.println("Head");
   while (current != null) {
    System.out.println("->" + current.getVal());
    current = current.next;
   }
   System.out.println("<--tail br="">   System.out.println("Size of the Q:"+getsize());
  }
 }

 public static void main(String[] args) {
  QueueMain queue = new QueueMain();
  queue.enqueue(23);
  queue.enqueue(43);
  queue.enqueue(143);
  queue.enqueue(321);
  queue.dequeue();
  queue.dequeue();
 }
}
Output : 
Enqueud element:23
Q Elememts:
Head
->23
<--tail br="">Size of the Q:1
Enqueud element:43
Q Elememts:
Head
->23
->43
<--tail br="">Size of the Q:2
Enqueud element:143
Q Elememts:
Head
->23
->43
->143
<--tail br="">Size of the Q:3
Enqueud element:321
Q Elememts:
Head
->23
->43
->143
->321
<--tail br="">Size of the Q:4
Dequeued element:23
Q Elememts:
Head
->43
->143
->321
<--tail br="">Size of the Q:3
Dequeued element:43
Q Elememts:
Head
->143
->321
<--tail br="">Size of the Q:2

References : [1][2][3][4]

Read more


Stack implementation using linked list in Java

Stack implementation using linked list in Java with out using arrays

We have seen implementing the stack using arrays in java in the previous post which has certain drawbacks like inserting / deleting an element from the desired or particular location.

So in a linked list there is a connection for each node / cell (it contains one object to hold desired value and link to the next node / cell). 

So when user pushed an element to the stack first element goes to the end, and the recently pushed item will have connection to the last recent item. 

so when a new node is pushed, existing top becomes old and new one becomes top similarly for each pop operation in stack takes out top element and his next becomes present top. 

below example code helps to understand linked list creation using Cell class an StackUsing LinkedList class helps will do actual push and pop operations


Cell Class : (Linked list) :
package com.krish.datastructures.common;

public class Cell {
	Object val; // value in the cell
	public Cell next; // the address of the next cell in the list

	/**
	 * Constructor Cell builds a new cell
	 * 
	 * @param value
	 *            - the value inserted in the cell
	 * @param link
	 *            - the cell that is chained to this new cell
	 */
	public Cell(Object value, Cell link) {
		val = value;
		next = link;
	}

	/** getVal returns the value held in the cell */
	public Object getVal() {
		return val;
	}

	/** getNext returns the address of the cell chained to this one */
	public Cell getNext() {
		return next;
	}

	/**
	 * setNext resets the address of the cell chained to this one
	 * 
	 * @param link
	 *            - the address of the Cell that is chained to this one
	 */
	public void setNext(Cell link) {
		next = link;
	}
}


Stack using Linked list : 

package com.krish.stack;

import com.krish.datastructures.common.Cell;

public class StackUsingLinkedLists {
	public static Cell top;

	/** Constructor Stack creates an empty stack */
	public StackUsingLinkedLists() {
		top = null;
	}

	/**
	 * push inserts a new element onto the stack
	 * 
	 * @param ob
	 *            - the element to be added
	 */
	public void push(Object ob) {
		System.out.println("PUSH : Inserted the element:" + ob);
		top = new Cell(ob, top);
		printStack();
	}

	/**
	 * pop removes the most recently added element prints error if stack is
	 * empty
	 */
	public void pop() {
		if (top == null) {
			System.out.println("POP: Stack error: stack empty");
		} else {
			Object answer = top.getVal();
			top = top.getNext();
			System.out.println("POP: popped the element:" + answer);
			printStack();
		}

	}

	/**
	 * top returns the identity of the most recently added element
	 * 
	 * @return the element
	 * @exception RuntimeException
	 *                if stack is empty
	 */
	public Object top() {
		if (top == null) {
			throw new RuntimeException("Stack error: stack empty");
		}
		return top.getVal();
	}

	/**
	 * isEmpty states whether the stack has 0 elements.
	 * 
	 * @return whether the stack has no elements
	 */
	public boolean isEmpty() {
		return (top == null);
	}

	// Print the stack elements by using top and next
	public void printStack() {
		if (top == null) {
			System.out.println("PRINT: Stack error: stack empty");
		} else {
			System.out.println("PRINT:These are the stack elements now!");
			Cell temp = top;
			while (temp != null) {
				System.out.println(temp.getVal());
				temp = temp.next;
			}
		}
	}

	public static void main(String[] args) {
		StackUsingLinkedLists stack = new StackUsingLinkedLists();
		stack.pop();
		stack.push(23);
		stack.push(267);
		stack.push(500);
		stack.pop();
		stack.pop();
		stack.pop();
	}
}
Output : 
POP: Stack error: stack empty
PUSH : Inserted the element:23
PRINT:These are the stack elements now!
23
PUSH : Inserted the element:267
PRINT:These are the stack elements now!
267
23
PUSH : Inserted the element:500
PRINT:These are the stack elements now!
500
267
23
POP: popped the element:500
PRINT:These are the stack elements now!
267
23
POP: popped the element:267
PRINT:These are the stack elements now!
23
POP: popped the element:23
PRINT: Stack error: stack empty
Reference : [1] [2

Read more


Stack implementation in Java

Stack implementation in Java
Stack : Stack in first in last out operated data structure ,where the first inserted (push'ed)element into the stack will be taken out (pop'ed) at last. it is like single door room . Those who enters room first will be able to come out only in the last . In other word last pushed element will be poped out first .

which we call generally as LIFO - Last In First Out

We can implement this stack using Java arrays like below ...
The below implementation takes/reads size of the stack what user want to create and implements stack operations.

Main Program :
package com.krish.stack;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class StackMain {

	public static void main(String[] args) {
		try{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String size;

		System.out.println("Enter stack size u want to create : ");
		size = br.readLine();
		System.out.println("Creating a Stack size is:"+Integer.parseInt(size));
		Stack stack = new Stack(Integer.parseInt(size));
		stack.printStackElements();
		stack.push(100);
		stack.push(200);
		stack.push(300);
		stack.pop();
		stack.pop();
		stack.pop();
		}
		catch(Exception e){
			e.printStackTrace();
		}
	}

}

Stack Class:  
package com.krish.stack;

public class Stack {
	int[] myStack;
	int top = -1;
	int size;

	public Stack(int size) {
		this.size = size;
		myStack = new int[size];
	}

	public void printStackElements() {
		if (top >= 0) {
			System.out.println("Present elements in the stack:");
			for (int i = 0; i <= top; i++) {
				System.out.println("Element at " + i + "position is "
						+ myStack[i]);
			}

		} else {
			System.out.println("Stack is empty");

		}

	}

	public void push(int element) {
		if (top < size - 1) {
			System.out.println("Pushing " + element + " to stack now");
			System.out.println("After push()");
			top++;
			myStack[top] = element;
			printStackElements();

		} else {
			System.out.println("Stack overflow; element can't be pushed");
		}
	}

	public void pop() {
		if (top >= 0) {
			System.out.println("Poping the top element now:" + myStack[top]);
			top--;
			printStackElements();
		} else {
			System.out.println("stack undeflow");
		}
	}
}

Output : 
 Enter stack size u want to create :
2
Creating a Stack size is:2
Stack is empty
Pushing 100 to stack now
After push()
Present elements in the stack:
Element at 0position is 100
Pushing 200 to stack now
After push()
Present elements in the stack:
Element at 0position is 100
Element at 1position is 200
Stack overflow; element can't be pushed
Poping the top element now:200
Present elements in the stack:
Element at 0position is 100
Poping the top element now:100
Stack is empty
stack undeflow

Advantages and disadvanaatages of using arrays in this : 
1. We can access any stack element when in array at any point of time randomly. 
2. Size is fixed we can't add more elements.
3. If we want to remove an element in between the elements then it is difficult to adjust the other elements. 
4. IF we want to insert at a particular position in between the array also it is difficult.

Reference : [1]

Read more


SQL injection - Java

SQL Injection 

SQL injection is a code injection technique, used to attack data driven applications, in which malicious SQL statements are inserted into an entry field for execution (e.g. to dump the database contents to the attacker).[1] SQL injection must exploit a security vulnerability in an application's software, for example, when user input is either incorrectly filtered for string literal escape characters embedded in SQL statements or user input is not strongly typed and unexpectedly executed. SQL injection is mostly known as an attack vector for websites but can be used to attack any type of SQL database.
   
PreparedStatements are the way to go, because they make SQL injection impossible. Here's a simple example taking the user's input as the parameters:

public insertUser(String name, String email) {
   Connection conn = null;
   PreparedStatement stmt = null;
   try {
      conn = setupTheDatabaseConnectionSomehow();
      stmt = conn.prepareStatement("INSERT INTO person (name, email) values (?, ?)");
      stmt.setString(1, name);
      stmt.setString(2, email);
      stmt.executeUpdate();
   }
   finally {
      try {
         if (stmt != null) { stmt.close(); }
      }
      catch (Exception e) {
         // log this error
      }
      try {
         if (conn != null) { conn.close(); }
      }
      catch (Exception e) {
         // log this error
      }
   }
}
Reference : http://stackoverflow.com/questions/1812891/java-escape-string-to-prevent-sql-injection

Read more


JDBC - Java - Interview questions

JDBC - Java - Theory - Interview questions
JDBC Basics :

    Establishing a connection. : First, establish a connection with the data source you want to use. A data source can be a DBMS, a legacy file system, or some other source of data with a corresponding JDBC driver. This connection is represented by a Connection object.
    Create a statement. : A Statement is an interface that represents a SQL statement. You execute Statement objects, and they generate ResultSet objects, which is a table of data representing a database result set. You need a Connection object to create a Statement object.
  
    There are three different kinds of statements:

    Statement: Used to implement simple SQL statements with no parameters.
    PreparedStatement: (Extends Statement.) Used for precompiling SQL statements that might contain input parameters. See Using Prepared Statements for more information.
    CallableStatement: (Extends PreparedStatement.) Used to execute stored procedures that may contain both input and output parameters. See Stored Procedures for more information.

    Execute the query. :
    To execute a query, call an execute method from Statement such as the following:

    execute: Returns true if the first object that the query returns is a ResultSet object. Use this method if the query could return one or more ResultSet objects. Retrieve the ResultSet objects returned from the query by repeatedly calling Statement.getResultSet.
    executeQuery: Returns one ResultSet object.
    executeUpdate: Returns an integer representing the number of rows affected by the SQL statement. Use this method if you are using INSERT, DELETE, or UPDATE SQL statements.

    Process the ResultSet object. : You access the data in a ResultSet object through a cursor. Note that this cursor is not a database cursor. This cursor is a pointer that points to one row of data in the ResultSet object. Initially, the cursor is positioned before the first row. You call various methods defined in the ResultSet object to move the cursor.
    Close the connection. : When you are finished using a Statement, call the method Statement.close to immediately release the resources it is using. When you call this method, its ResultSet objects are closed.

For example, the method CoffeesTables.viewTable ensures that the Statement object is closed at the end of the method, regardless of any SQLException objects thrown, by wrapping it in a finally block:

} finally {
    if (stmt != null) { stmt.close(); }
}

JDBC throws an SQLException when it encounters an error during an interaction with a data source.

Read more

Translate

Enter your email address:

Buffs ...

Visitors


hits counter
View My StatsCheck Google Page Rank

Add to Google Reader or Homepage

Bookmark and Share

Tags


Powered by WidgetsForFree