Merge Soft

This is how i implemented the MergeSoft in Java

package com.webspherenotes.algo;

public class MergeSort {

  /**
   * @param args
   */
  public static void main(String[] args) {

    int[] inplace = {10,9,8,7,6,5,4,3,2,1,0};
    MergeSort ms = new MergeSort();
    ms.sort(inplace,0, inplace.length-1);
    ms.printArray(inplace,"Final result");
  }

  
  private void sort(int[] input, int lo, int hi){
    if(hi <= lo) return;
    int mid =  (hi+lo)/2;
    sort(input,lo,mid);
    sort(input,mid+1,hi);
    merge(input, lo,mid,hi);
  }
  
  private void merge(int[] input, int lo,  int mid, int hi){
    
    printArray(input,lo,hi,"input");
    int auxArrayLength = hi - lo+1;
    int[] auxArray = new int[auxArrayLength];
    int auxCounter  =0 ;
    for(int i = lo ; i <= hi ;i++)
      auxArray[auxCounter++] = input[i];
    printArray(auxArray,"Temp  Array");
    
    int auxArrayMid = (mid-lo) ;
    int firstArrayCounter  =0 ;
    int secondArrayCounter = auxArrayMid +1;
    for(int inputArrayCounter = lo ; inputArrayCounter <= hi; inputArrayCounter++ ){
      if(firstArrayCounter > auxArrayMid){ //First array is all coiped
        input[inputArrayCounter] = auxArray[secondArrayCounter++];
      }else if(secondArrayCounter >= auxArrayLength){ //Second array is all copied
        input[inputArrayCounter] = auxArray[firstArrayCounter++];
      }else if(auxArray[firstArrayCounter] < auxArray[secondArrayCounter]){ //Value at the top of first array is small
        input[inputArrayCounter] = auxArray[firstArrayCounter++];
      }else{
        input[inputArrayCounter] = auxArray[secondArrayCounter++];
      }
      printArray(input, "mergeTemp");
    }
    
    
    printArray(input,lo,hi,"output");
  }

  private void printArray(int[] input, String label) {

    System.out.print(label+ " ->{");
    for (int i = 0; i < input.length; i++) {
      System.out.print(input[i]);
      if (i != input.length - 1)
        System.out.print(" , ");
    }
    System.out.println("}");
  }
  
  private void printArray(int[] input,int lo, int hi, String label) {

    System.out.print(label+ " -> {");
    for (int i = lo; i <= hi; i++) {
      System.out.print(input[i]);
      if (i != input.length - 1)
        System.out.print(" , ");
    }
    System.out.println("}");
  }
}

Selection Sort

Iterate in the array and find out the smallest element first replace it with the first element, then iterate the n-1 array and find out smallest element and replace it with 1st element,... Growth of function is n2

package com.webspherenotes.algo;

public class SelectionSort {
 
 public static void main(String[] args) {
  int[] input = {6,5,4,3,2,1};
  
  SelectionSort selectionSort = new SelectionSort();
  selectionSort.printArray(input);
  int[] ouptut = selectionSort.sort(input);
  
  System.out.print("Result is ->");
  selectionSort.printArray(ouptut);
  System.out.println("Number of exchagnes " + selectionSort.noOfExchanges);
 }

 
 private int[] sort(int[] input){
  int length = input.length;
  for(int i = 0 ; i < length -1 ; i++){
   int smallest = i;
   for(int j = i + 1 ; j < length; j++ ){
    if(input[smallest] > input[j]){
     smallest = j;
    }
   }
   if(i != smallest){
    exchange(input, smallest, i);
    printArray(input);
   }
  }
  return input;
 }

 private void printArray(int[] input) {

  System.out.print("{");
  for (int i = 0; i < input.length; i++) {
   System.out.print(input[i]);
   if (i != input.length - 1)
    System.out.print(" , ");
  }
  System.out.println("}");
 }

 int noOfExchanges;

 private void exchange(int[] array, int first, int second) {
  int temp = array[first];
  array[first] = array[second];
  array[second] = temp;
  noOfExchanges++;
 }
}

Add two integer arrays

Consider the problem of adding two n-bit binary integers, stored in two n-element arrays A and B. The sum of the two integers should be stored in binary form in an .n C 1/-element array C. State the problem formally and write pseudocode for adding the two integers.

package com.webspherenotes.algo;

public class AddTwoIntegers {

  /**
   * @param args
   */
  public static void main(String[] args) {
    int[] first = {9,9,9,9};
    int[] second = {9,9,9,9};
    
    AddTwoIntegers addTwoInteger = new AddTwoIntegers();
    addTwoInteger.printArray(addTwoInteger.add(first, second));
    
  }

  
  private int[] add(int[] first, int[] second){
    int length = first.length;
    int[] result = new int[length+1];
    int carry = 0 ;
    for(int i = length -1 ; i >=0 ; i--){
      int currentValue = first[i] + second[i] + carry;
      result[i+1] = currentValue %10;
      carry = currentValue/10;
      printArray(result);
    }
    result[0]=carry;
    return result;
  }
  
  private void printArray(int[] input) {

    System.out.print("{");
    for (int i = 0; i < input.length; i++) {
      System.out.print(input[i]);
      if (i != input.length - 1)
        System.out.print(" , ");
    }
    System.out.println("}");
  }

}

Reverse Insert Sort

Problem -> Rewrite the INSERTION-SORT procedure to sort into non increasing instead of non decreasing order. Solution

package com.webspherenotes.algo;

public class InsertSortReverse {

  /**
   * @param args
   */
  public static void main(String[] args) {
    int[] input = { 1, 2, 3, 4, 5, 6, 7 };

    InsertSortReverse insertSort = new InsertSortReverse();
    insertSort.printArray(input);
    int[] ouptut = insertSort.sort(input);

    System.out.print("Result is ->");
    insertSort.printArray(ouptut);
    System.out.println("Number of exchagnes " + insertSort.noOfExchanges);

  }

  private int[] sort(int[] input) {
    int length = input.length;
    for (int counter = length - 2; counter >= 0; counter--) {

      int key = input[counter];
      int exchangeCounter = counter + 1;
      while (exchangeCounter < length && key < input[exchangeCounter]) {
        exchange(input, exchangeCounter - 1, exchangeCounter);
        exchangeCounter++;
        printArray(input);
      }
    }

    return input;
  }

  private void printArray(int[] input) {

    System.out.print("{");
    for (int i = 0; i < input.length; i++) {
      System.out.print(input[i]);
      if (i != input.length - 1)
        System.out.print(" , ");
    }
    System.out.println("}");
  }

  int noOfExchanges;

  private void exchange(int[] array, int first, int second) {
    int temp = array[first];
    array[first] = array[second];
    array[second] = temp;
    noOfExchanges++;
  }
}

Insert Sort

1 for j D 2 to A:length 2 key D AOEj 3 // Insert AOEj into the sorted sequence AOE1 : : j 1 . 4 i D j 1 5 while i > 0 and AOEi > key 6 AOEi C 1 D AOEi 7 i D i 1 8 AOEi C 1 D key

package com.webspherenotes.algo;

public class InsertSort {

  /**
   * @param args
   */
  public static void main(String[] args) {
    int[] input = {1,2,3,4,5,6};
    
    InsertSort insertSort = new InsertSort();
    insertSort.printArray(input);
    int[] ouptut = insertSort.sort(input);
    
    System.out.print("Result is ->");
    insertSort.printArray(ouptut);
    System.out.println("Number of exchagnes " + insertSort.noOfExchanges);
  }

  
  private int[] sort(int[] input){
    int length = input.length;
    for(int i = 1 ; i < length; i++){
      int currValue = input[i];

      int exchangeStartIndex = i -1;
      while(exchangeStartIndex >=0 && currValue < input[exchangeStartIndex]){
        exchange(input, exchangeStartIndex+1, exchangeStartIndex);
        exchangeStartIndex --;
        printArray(input);
      }
    }
    return input;
  }
  
  private void printArray(int[] input){
    
    System.out.print("{");
    for(int i = 0 ; i < input.length; i++){
      System.out.print(input[i]);
      if(i != input.length -1)
        System.out.print(" , ");
    }
    System.out.println("}");
  }
  int noOfExchanges;
  private void exchange(int[] array, int first, int second){
    int temp = array[first];
    array[first] = array[second];
    array[second] = temp;
    noOfExchanges++;
  }
}