Optimized Bubble Sort using Java .....

Quick Logic - In bubble sort we are compairing adjacent elements, swap them if we need to and this                          will continue upto (N-1) passes .So optimized bubble sort will be most efficient if the                          array is already sorted or almost sorted.

Optimization Logic - We are checking that if two continues passes of the bubble sort are same then                            we don't have to continue further because array has already become sorted till now.

here is the code....

       
public class OptimizedBubbleSort {

 static int[] arr = {
  1,
  2,
  3,
  4,
  5,
  6,
  70,
  18,
  9
 };
 static boolean[] swapFlag = new boolean[arr.length - 1]; //to keep track that in each pass swap happens or not
 static int temp;

 public static void main(String[] args) {

  bubbleSort();
  for (int i = 0; i < arr.length; i++) {
   System.out.print(arr[i] + " ");
  }
 }

 public static void bubbleSort() {

  for (int i = 0; i < arr.length - 1; i++) {
   for (int y = 0; y < arr.length - i - 1; y++) {
    if (arr[y] > arr[y + 1]) {
     swap(y, y + 1);
     swapFlag[i] = true;
    }
   }
   System.out.println(i + " pass");
   if (i != 0) {
    if (swapFlag[i] == false && swapFlag[i - 1] == false) //condition where we are checking that int two succesive passes
     return;
   }
  }
 }

 public static void swap(int k, int r) {
  temp = arr[r];
  arr[r] = arr[k];
  arr[k] = temp;
 }

}

       
 

Dijkstra's Algorithm using Min Heap to find shortest path from source to all other nodes in Java .....

here is the code .....

       
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class DijkstraProblem {

 static int[][] costMatrix;
 static String line;
 static String[] lineValues;
 static int totalNodes;
 static int source;
 static int[] heapHolder; //to hold the cost of path to nodes 
 static int[] nodeNameHolder; //to hold the nodes corresponding to the heap cost in heapholder
 static int heapLength;
 static int smallest;
 static int left; // left child index
 static int right; // right child index
 static int temp;
 static int reducedNode = 0;
 static int reducedNodePathCost = 1;
 static int[] deletedNode; //to hold the cost and the node number everytime we delete root node from heap 
 static int newCostViaReducedNode;


 public static void main(String[] args) throws IOException {

  String path = "C:/Users/gauravy/Desktop/matrix.txt";
  loadfile(path);
  BufferedReader gr = new BufferedReader(new InputStreamReader(System.in));
  System.out.println("Please enter the node number from where you want shortest path to all nodes ...");
  source = Integer.parseInt(gr.readLine());
  applyDijkstra(source);

  System.out.println("Shortest path from source to all other nodes is below sequentially.....");
  for (int v = 0; v < totalNodes; v++) {
   System.out.print("source to node " + v + " cost is - " + costMatrix[source][v]);
   System.out.println("");
  }


 }

 // method to load the adjacency matrix for graph from the text file
 public static void loadfile(String path) throws IOException {

  FileReader fr = new FileReader(new File(path));
  BufferedReader br = new BufferedReader(fr);

  line = br.readLine();
  lineValues = line.split(" ");
  totalNodes = lineValues.length;
  costMatrix = new int[totalNodes][totalNodes];
  heapHolder = new int[totalNodes];
  deletedNode = new int[2];
  //viaNodeHolder = new int[totalNodes];
  nodeNameHolder = new int[totalNodes];
  heapLength = lineValues.length;

  int r = 0;

  while (line != null) {
   for (int c = 0; c < totalNodes; c++) {
    costMatrix[r][c] = Integer.parseInt(lineValues[c]);

   }
   r++;
   line = br.readLine();
   if (line != null)
    lineValues = line.split(" ");
  }
  fr.close();
  br.close();
 }

 // here we are applying the Dijkstra's algorithm
 public static void applyDijkstra(int source) {

  //viaNodeHolder[0] = 0;
  //nodeNameHolder[0]=0;
  for (int y = 0; y < heapLength; y++) {
   heapHolder[y] = Integer.MAX_VALUE;
   //viaNodeHolder[y] = 0;
   nodeNameHolder[y] = y;
  }
  heapHolder[source] = 0;

  buildMinHeap();

  for (int k = 0; k < totalNodes; k++) {
   deleteRoot();

   for (int p = 0; p < heapLength; p++) {
    newCostViaReducedNode = deletedNode[reducedNodePathCost] + costMatrix[deletedNode[reducedNode]][nodeNameHolder[p]];

    if (newCostViaReducedNode < heapHolder[p]) {
     heapHolder[p] = newCostViaReducedNode;
     costMatrix[source][nodeNameHolder[p]] = newCostViaReducedNode;
    }
    min_Heapify(0);
   }
  }
 }

 public static void buildMinHeap() {
  for (int p = heapHolder.length / 2 - 1; p >= 0; p--) {
   min_Heapify(p);
  }
 }

 // min heapify algorithm implemented here
 public static void min_Heapify(int p) {
  left = leftChild(p);
  right = rightChild(p);

  if ((left < heapLength) && (heapHolder[left] < heapHolder[p]))
   smallest = left;
  else
   smallest = p;

  if ((right < heapLength) && (heapHolder[right] < heapHolder[smallest]))
   smallest = right;

  if (smallest != p) {
   swap(smallest, p);
   min_Heapify(smallest);
  }
 }

 // returns index of left child
 public static int leftChild(int k) {
  return (2 * k + 1);
 }

 // returns of right child
 public static int rightChild(int i) {
  return (2 * i + 2);
 }

 // for swapping purpose
 public static void swap(int a, int b) {

  temp = heapHolder[a];
  heapHolder[a] = heapHolder[b];
  heapHolder[b] = temp;

  temp = nodeNameHolder[a];
  nodeNameHolder[a] = nodeNameHolder[b];
  nodeNameHolder[b] = temp;
 }

 // for deletion of root node from heap
 public static void deleteRoot() {

  deletedNode[reducedNode] = nodeNameHolder[0];
  deletedNode[reducedNodePathCost] = heapHolder[0];

  heapHolder[0] = heapHolder[heapLength - 1];
  //viaNodeHolder[0] = viaNodeHolder[heapLength - 1];
  nodeNameHolder[0] = nodeNameHolder[heapLength - 1];

  heapLength--;
  min_Heapify(0);
 }

}

       
 

Max Heap using Java.....

here is the code...

       
public class BuildMaxHeapProblem {
 static int[] heap = {
  80,
  90,
  32,
  1,
  40,
  50,
  45,
  22,
  12,
  23,
  33
 };
 static int largest;
 static int left; //left child index
 static int right; //right child index
 static int temp;

 public static void main(String[] args) {
  buildMaxHeap();
  for (int k: heap) {
   System.out.print(k);
   System.out.print(" ");
  }
 }
 public static void buildMaxHeap() {
  for (int p = heap.length / 2 - 1; p >= 0; p--) {
   max_Heapify(p);
  }
 }
 public static void max_Heapify(int p) {
  left = leftChild(p);
  right = rightChild(p);

  if ((left < heap.length) && (heap[left] > heap[p]))
   largest = left;
  else largest = p;

  if ((right < heap.length) && (heap[right] > heap[largest]))
   largest = right;

  if (largest != p) {
   swap(largest, p);
   max_Heapify(largest);
  }
 }
 public static int leftChild(int k) {
  return (2 * k + 1);
 }
 public static int rightChild(int i) {
  return (2 * i + 2);
 }
 public static void swap(int a, int b) {
  temp = heap[a];
  heap[a] = heap[b];
  heap[b] = temp;
 }

}

       
 

Min Heap using Java.....

here is the code....

       

public class BuildMinHeapProblem {
 static int[] heap = {
  80,
  90,
  32,
  1,
  40,
  50,
  45,
  22,
  12,
  23,
  33
 };
 static int smallest;
 static int left; //left child index
 static int right; //right child index
 static int temp;

 public static void main(String[] args) {
  buildMinHeap();
  for (int k: heap) {
   System.out.print(k);
   System.out.print(" ");
  }
 }
 public static void buildMinHeap() {
  for (int p = heap.length / 2 - 1; p >= 0; p--) {
   min_Heapify(p);
  }
 }
 public static void min_Heapify(int p) {
  left = leftChild(p);
  right = rightChild(p);

  if ((left < heap.length) && (heap[left] < heap[p]))
   smallest = left;
  else smallest = p;

  if ((right < heap.length) && (heap[right] < heap[smallest]))
   smallest = right;

  if (smallest != p) {
   swap(smallest, p);
   min_Heapify(smallest);
  }
 }
 public static int leftChild(int k) {
  return (2 * k + 1);
 }
 public static int rightChild(int i) {
  return (2 * i + 2);
 }
 public static void swap(int a, int b) {
  temp = heap[a];
  heap[a] = heap[b];
  heap[b] = temp;
 }

}
       
 

Find all missing numbers in a sequence......

Problem:- Given a list of numbers from 1 to N where more than one numbers are                    missing between 1 to N find all of them .

here is the code ......

       
public class AllMissingNumbersProblem {
 static int missNum;
 static int largestNum;
 static boolean[] keepTrack;
 public static void main(String args[]) {

  int[] arr = {
   4,
   2,
   6,
   5,
   3,
   1,
   8,
   12,
   9,
   11
  };
  largestNum = findLargestNumber(arr);
  keepTrack = new boolean[largestNum + 1];

  for (int i = 0; i < arr.length; i++)
   keepTrack[arr[i]] = true;

  System.out.println("Missing numbers are listed below....");
  for (int p = 1; p < keepTrack.length; p++) {
   if (!keepTrack[p])
    System.out.println(p);
  }

 }
 public static int findLargestNumber(int[] arr) {
  int temp;
  for (int i = 0; i < arr.length - 1; i++) {
   if (arr[i] > arr[i + 1]) {
    temp = arr[i + 1];
    arr[i + 1] = arr[i];
    arr[i] = temp;
   }
  }
  return arr[arr.length - 1];
 }
}

       
 

Find the missing number......

Problem:- Given a list of number from 1 to N find the missing number ....

Logic -Just calculate sum of N natural numbers (n*(n+1))/2.
            Then subtract the sum of all given numbers from above calculated sum                    and you will get missing number.

here is the code......

       

public class MissingNumberProblem {
 static int missNum;
 static int largestNum;
 static int naturalSum;
 static int totalNumbersSum;
 public static void main(String args[]) {

  int[] arr = {
   4,
   2,
   6,
   5,
   3,
   1,
   8,
   12,
   9,
   11,
   7
  };
  largestNum = findLargestNumber(arr);
  naturalSum = (largestNum * (largestNum + 1)) / 2;

  for (int i = 0; i < arr.length; i++) {
   totalNumbersSum = totalNumbersSum + arr[i];
  }

  missNum = naturalSum - totalNumbersSum;
  System.out.println("Missing number is " + missNum);

 }
 public static int findLargestNumber(int[] arr) {
  int temp;
  for (int i = 0; i < arr.length - 1; i++) {
   if (arr[i] > arr[i + 1]) {
    temp = arr[i + 1];
    arr[i + 1] = arr[i];
    arr[i] = temp;
   }
  }
  return arr[arr.length - 1];
 }
}
       
 

Tic-Tac-Toe Game using Java.......

Features - 1.This program always takes constant time for playing a move and       evaluating winning condition.

2.Game can be played on board of any size ,currently I've configured it for max Board size of 10 .

3.Currently only multiplayer mode is implemented ,single player with bot will be implemented soon .

NOTE-  Conventions to play Tic-Tac-Toe game are as follows...
1.When it asked for size of the board enter single digit number for e.g -if you want to play on 3*3 then just enter "3" (without quotes of course) and press "enter".
         
 2.When you want to play a move enter the row and column index of the position separated by a space .
 e.g - If you want to enter a move on first column of first row then just                     enter "1 1" ( without double quotes ) and then press "enter".  

here is the code ...............

       

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.*;

public class TicTacToeProblem {
 static int size;
 static int mode;
 static HashMap < String, ArrayList < String >> player1RowsAndDiagonals = new HashMap < String, ArrayList < String >> (); //to keep track of rows and diagonal formation for player 1 
 static HashMap < String, ArrayList < String >> player2RowsAndDiagonals = new HashMap < String, ArrayList < String >> (); //to keep track of rows and diagonal formation for player 2
 static HashMap < String, ArrayList < String >> player1Columns = new HashMap < String, ArrayList < String >> (); //to keep track of column formation for player 1 
 static HashMap < String, ArrayList < String >> player2Columns = new HashMap < String, ArrayList < String >> (); //to keep track of column formation for player 2 
 static HashSet < String > filledPositions = new HashSet < String > ();

 public static void main(String[] args) throws NumberFormatException,
  IOException {
   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   System.out.println("Please enter the size of board in numeral");
   size = Integer.parseInt(br.readLine());

   while ((size > 10) == true) {
    System.out.println("Max size allowed is 10");
    System.out.println("please re enter the size");
    size = Integer.parseInt(br.readLine());
   }
   System.out.println("please enter playing mode number");
   System.out.println("1.two player");
   System.out.println("2.with bot");
   mode = Integer.parseInt(br.readLine());
   while (mode != 1 && mode != 2) {
    System.out.println("Please enter appropriate choice of mode 1 or 2");
    mode = Integer.parseInt(br.readLine());
   }
   if (mode == 1) {
    System.out.println("Initializing Setup..........");
    multiplayer(size);
   } else
    withBot(size);
   br.close();
  }

 public static void multiplayer(int size) throws IOException {
  String[] playerMove = null;
  String move = null;
  int coordinateX;
  int coordinateY;
  int player;
  int secondDiagonalSum = size + 1;
  int maxMoves = size * size;

  for (int i = 1; i <= size; i++) { //here just initializing arrayLists for each rows and each columns for both players
   ArrayList < String > rowList1 = new ArrayList < String > ();
   ArrayList < String > rowList2 = new ArrayList < String > ();
   ArrayList < String > columnList1 = new ArrayList < String > ();
   ArrayList < String > columnList2 = new ArrayList < String > ();
   player1RowsAndDiagonals.put((new Integer(i).toString()), rowList1);
   player2RowsAndDiagonals.put((new Integer(i).toString()), rowList2);
   player1Columns.put((new Integer(i).toString()), columnList1);
   player2Columns.put((new Integer(i).toString()), columnList2);
  }

  ArrayList < String > player1diag1 = new ArrayList < String > (); //here initializing arrayLists to keep track of both the diagonals for both players
  ArrayList < String > player1diag2 = new ArrayList < String > ();
  ArrayList < String > player2diag1 = new ArrayList < String > ();
  ArrayList < String > player2diag2 = new ArrayList < String > ();

  player1RowsAndDiagonals.put("diag1", player1diag1);
  player1RowsAndDiagonals.put("diag2", player1diag2);
  player2RowsAndDiagonals.put("diag1", player2diag1);
  player2RowsAndDiagonals.put("diag2", player2diag2);

  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

  System.out.println("OK,now start playing enter your choices alternatively");

  for (int i = 0; i < maxMoves; i++) {
   if (i % 2 == 0) {
    System.out.println("player 1 turn");
    player = 1;
   } else {
    System.out.println("player 2 turn");
    player = 2;
   }
   move = br.readLine();
   while (filledPositions.contains(move) == true) { //check for already played Move
    System.out.println("this move has been already played please enter another move");
    move = br.readLine();
   }
   filledPositions.add(move);
   playerMove = move.split(" ");
   coordinateX = Integer.parseInt(playerMove[0]);
   coordinateY = Integer.parseInt(playerMove[1]);

   switch (player) {
    case 1:
     if (playerMove[0].equals(playerMove[1])) { //condition for one of the position in diagonal one
      player1RowsAndDiagonals.get("diag1").add(playerMove[1]);
      player1RowsAndDiagonals.get(playerMove[0]).add(playerMove[1]);
      player1Columns.get(playerMove[1]).add(playerMove[0]);

      if ((coordinateX + coordinateY) == secondDiagonalSum) //condition for one of the position in diagonal two 
       player1RowsAndDiagonals.get("diag2").add(playerMove[1]);

      if ((player1Columns.get(playerMove[1]).size() == size) || (player1RowsAndDiagonals.get("diag1").size() == size) || (player1RowsAndDiagonals.get(playerMove[0]).size() == size) || (player1RowsAndDiagonals.get("diag2").size() == size)) {
       System.out.println("Player 1 wins game is finished");
       return;
      }
     } else {
      player1RowsAndDiagonals.get(playerMove[0]).add(playerMove[1]);
      player1Columns.get(playerMove[1]).add(playerMove[0]);

      if ((coordinateX + coordinateY) == secondDiagonalSum)
       player1RowsAndDiagonals.get("diag2").add(playerMove[1]);

      if ((player1Columns.get(playerMove[1]).size() == size) || (player1RowsAndDiagonals.get("diag1").size() == size) || (player1RowsAndDiagonals.get(playerMove[0]).size() == size) || (player1RowsAndDiagonals.get("diag2").size() == size)) {
       System.out.println("Player 1 wins game is finished");
       return;
      }
     }
     break;
    case 2:
     if (playerMove[0].equals(playerMove[1])) {
      player2RowsAndDiagonals.get("diag1").add(playerMove[1]);
      player2RowsAndDiagonals.get(playerMove[0]).add(playerMove[1]);
      player2Columns.get(playerMove[1]).add(playerMove[0]);

      if ((coordinateX + coordinateY) == secondDiagonalSum)
       player2RowsAndDiagonals.get("diag2").add(playerMove[1]);

      if ((player2Columns.get(playerMove[1]).size() == size) || (player2RowsAndDiagonals.get("diag1").size() == size) || (player2RowsAndDiagonals.get(playerMove[0]).size() == size) || (player2RowsAndDiagonals.get("diag2").size() == size)) {
       System.out.println("Player 1 wins game is finished");
       return;
      }
     } else {
      player2RowsAndDiagonals.get(playerMove[0]).add(playerMove[1]);
      player2Columns.get(playerMove[1]).add(playerMove[0]);

      if ((coordinateX + coordinateY) == secondDiagonalSum)
       player2RowsAndDiagonals.get("diag2").add(playerMove[1]);

      if ((player2Columns.get(playerMove[1]).size() == size) || (player2RowsAndDiagonals.get("diag1").size() == size) || (player2RowsAndDiagonals.get(playerMove[0]).size() == size) || (player2RowsAndDiagonals.get("diag2").size() == size)) {
       System.out.println("Player 2 wins game is finished");
       return;
      }
     }
     break;
    default:
     break;
   }
  } //end of loop 
  System.out.println("Match Tie NO one Wins");
 }



 public static void withBot(int size) {
  System.out.println("Working on it, this mode will be added soon till then keep playing multiplayer mode");
  return;
 }
}