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

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

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

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

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

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

}

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

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