Top Down Merge Sort

Top down Merge Sort code in Java:

package com.kpatil.sort;

public class MergeSort {

 public static void sort(int[] list) {
  int[] aux = new int[list.length];
  sort(list, aux, 0, list.length - 1);
 }

 public static void sort(int[] list, int[] aux, int left, int right) {
  if (right <= left) {
   return;
  }

  int mid = left + (right - left) / 2;
  sort(list, aux, left, mid); // sort first half recursively
  sort(list, aux, mid + 1, right); // sort second half recursively
  merge(list, aux, left, mid, right); // merge two sorted halves
 }

 public static void merge(int[] list, int[] aux, int left, int mid, int right) {
  for (int k = left; k <= right; k++) {
   aux[k] = list[k];
  }
  int i = left;
  int j = mid + 1;
  for (int k = left; k <= right; k++) {
   if (i > mid) {
    list[k] = aux[j];
    j++;
   } else if (j > right) {
    list[k] = aux[i];
    i++;
   } else if (aux[j] < aux[i]) {
    list[k] = aux[j];
    j++;
   } else {
    list[k] = aux[i];
    i++;
   }
  }
 }

}

JUnit test cases:

package com.kpatil.test;

import static org.junit.Assert.assertEquals;

import java.util.Arrays;

import org.junit.Test;

import com.kpatil.sort.MergeSort;

public class MergeSortTest {
 @Test
 public void test1() {
  int[] array = { 5, 2, 89, 0, 10, 3, 20, 1 };
  int[] sorted = { 0, 1, 2, 3, 5, 10, 20, 89 };
  MergeSort.sort(array);
  assertEquals(true, Arrays.equals(array, sorted));
 }

 @Test
 public void test2() {
  int SIZE = 1000;
  int[] list = new int[SIZE];
  int[] expectedList = new int[SIZE];
  for (int i = 0; i < SIZE; i++) {
   int rand = (int) (Math.random() * SIZE);
   list[i] = rand;
   expectedList[i] = rand;
  }
  MergeSort.sort(list);
  System.out.println("------------------");
  Arrays.sort(expectedList);
  assertEquals(true, Arrays.equals(list, expectedList));

  for (int i = 0; i < SIZE; i++) {
   System.out.print(list[i] + " ");
  }
  System.out.println();
 }
}

Bubble Sort in Java

Bubble sort code in Java:

package com.kpatil.sort;

public class BubbleSort {
 public static void sort(int[] list) {
  int n = list.length;
  boolean swapped = true;
  while (swapped) {
   swapped = false;
   for (int i = 1; i < n; i++) {
    if (list[i - 1] > list[i]) {
     int temp = list[i - 1];
     list[i - 1] = list[i];
     list[i] = temp;
     swapped = true;
    }
   }
   n = n - 1;
  }
 }
}

JUnit Test Cases:

package com.kpatil.test;

import static org.junit.Assert.*;
import java.util.Arrays;
import org.junit.Test;
import com.kpatil.sort.BubbleSort;

public class BubbleSortTest {

 @Test
 public void test1() {
  int[] array = { 5, 2, 89, 0, 10, 3, 20, 1 };
  int[] sorted = { 0, 1, 2, 3, 5, 10, 20, 89 };
  BubbleSort.sort(array);
  assertEquals(true, Arrays.equals(array, sorted));
 }

 @Test
 public void test2() {
  int SIZE = 1000;
  int[] list = new int[SIZE];
  int[] expectedList = new int[SIZE];
  for (int i = 0; i < SIZE; i++) {
   int rand = (int) (Math.random() * SIZE);
   list[i] = rand;
   expectedList[i] = rand;
  }
  BubbleSort.sort(list);
  Arrays.sort(expectedList);
  assertEquals(true, Arrays.equals(list, expectedList));
  
  for (int i = 0; i < SIZE; i++) {
   System.out.print(list[i] + " ");
  }
  System.out.println();
 }

}

Binary Search Example in Java

Here is a binary search code in Java programming language:

package com.kpatil.search;

public class BinarySearch {
 /**
  * Returns true if the given element is found in the list supplied.
  * 
  * @param list of integers
  * @param element to search
  * @return true if a given element is found in the list
  * 
  */
 public static boolean binarySearch(int[] list, int k) {

  if (list == null || list.length == 0) {
   return false;
  }

  int low = 0;
  int high = list.length - 1;

  while (low <= high) {
   // int mid = (high + low) / 2;
   int mid = low + ((high - low) / 2);
   if (list[mid] == k) {
    return true;
   } else if (list[mid] > k) {
    high = mid - 1;
   } else {
    low = mid + 1;
   }
  }

  return false;
 }

}

JUnit test cases:

package com.kpatil.test;

import static org.junit.Assert.*;

import org.junit.Test;

import com.kpatil.search.BinarySearch;

public class BinarySearchTest {

 @Test
 public void test1() {
  int[] list = { 3, 5, 7, 9, 11, 54, 59, 123 };
  assertEquals(true, BinarySearch.binarySearch(list, 123));
 }

 @Test
 public void test2() {
  int[] list = { 3, 5, 7, 9, 11, 54, 59, 123 };
  assertEquals(false, BinarySearch.binarySearch(list, 152));
 }

 @Test
 public void test3() {
  int[] list = null;
  assertEquals(false, BinarySearch.binarySearch(list, 2));
 }

 @Test
 public void test4() {
  int[] list = {2};
  assertEquals(true, BinarySearch.binarySearch(list, 2));
 }
 
 @Test
 public void test5() {
  int[] list = {};
  assertEquals(false, BinarySearch.binarySearch(list, 25));
 }

}