Merge pull request TheAlgorithms#490 from lq920320/Development

varunu28 · web-flow · commit 3eff87291b4e · 2018-08-26T09:44:28.000-07:00
add some tests for Sort
diff --git a/src/main/com/java/sorts/BubbleSort.java b/src/main/com/java/sorts/BubbleSort.java
@@ -0,0 +1,28 @@
+package src.main.com.java.sorts;
+
+import static src.main.com.java.sorts.SortUtils.less;
+import static src.main.com.java.sorts.SortUtils.swap;
+
+public class BubbleSort {
+  /**
+   * This method implements the Generic Bubble Sort
+   *
+   * @param array The array to be sorted
+   *              Sorts the array in increasing order
+   **/
+  public <T extends Comparable<T>> T[] sort(T[] array) {
+    int last = array.length;
+    //Sorting
+    boolean swap;
+    do {
+      swap = false;
+      for (int count = 0; count < last - 1; count++) {
+        if (less(array[count + 1], array[count])) {
+          swap = swap(array, count, count + 1);
+        }
+      }
+      last--;
+    } while (swap);
+    return array;
+  }
+}
diff --git a/src/main/com/java/sorts/HeapSort.java b/src/main/com/java/sorts/HeapSort.java
@@ -0,0 +1,115 @@
+package src.main.com.java.sorts;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+
+import static src.main.com.java.sorts.SortUtils.less;
+import static src.main.com.java.sorts.SortUtils.swap;
+
+public class HeapSort {
+
+
+  private static class Heap<T extends Comparable<T>> {
+    /**
+     * Array to store heap
+     */
+    private T[] heap;
+
+    /**
+     * Constructor
+     *
+     * @param heap array of unordered integers
+     */
+    Heap(T[] heap) {
+      this.heap = heap;
+    }
+
+    /**
+     * Heapifies subtree from top as root to last as last child
+     *
+     * @param rootIndex index of root
+     * @param lastChild index of last child
+     */
+    private void heapSubtree(int rootIndex, int lastChild) {
+      int leftIndex = rootIndex * 2 + 1;
+      int rightIndex = rootIndex * 2 + 2;
+      T root = heap[rootIndex];
+      if (rightIndex <= lastChild) {
+        // if has right and left children
+        T left = heap[leftIndex];
+        T right = heap[rightIndex];
+        if (less(left, right) && less(left, root)) {
+          swap(heap, leftIndex, rootIndex);
+          heapSubtree(leftIndex, lastChild);
+        } else if (less(right, root)) {
+          swap(heap, rightIndex, rootIndex);
+          heapSubtree(rightIndex, lastChild);
+        }
+      } else if (leftIndex <= lastChild) {
+        // if no right child, but has left child
+        T left = heap[leftIndex];
+        if (less(left, root)) {
+          swap(heap, leftIndex, rootIndex);
+          heapSubtree(leftIndex, lastChild);
+        }
+      }
+    }
+
+
+    /**
+     * Makes heap with root as root
+     *
+     * @param root index of root of heap
+     */
+    private void makeMinHeap(int root) {
+      int leftIndex = root * 2 + 1;
+      int rightIndex = root * 2 + 2;
+      boolean hasLeftChild = leftIndex < heap.length;
+      boolean hasRightChild = rightIndex < heap.length;
+      if (hasRightChild) {
+        //if has left and right
+        makeMinHeap(leftIndex);
+        makeMinHeap(rightIndex);
+        heapSubtree(root, heap.length - 1);
+      } else if (hasLeftChild) {
+        heapSubtree(root, heap.length - 1);
+      }
+    }
+
+    /**
+     * Gets the root of heap
+     *
+     * @return root of heap
+     */
+    private T getRoot(int size) {
+      swap(heap, 0, size);
+      heapSubtree(0, size - 1);
+      // return old root
+      return heap[size];
+    }
+
+
+  }
+
+  public <T extends Comparable<T>> T[] sort(T[] unsorted) {
+    return sort(Arrays.asList(unsorted)).toArray(unsorted);
+  }
+
+  private <T extends Comparable<T>> List<T> sort(List<T> unsorted) {
+    int size = unsorted.size();
+
+    @SuppressWarnings("unchecked")
+    Heap<T> heap = new Heap<>(unsorted.toArray((T[]) new Comparable[unsorted.size()]));
+
+    // make min heap using index 0 as root.
+    heap.makeMinHeap(0);
+    List<T> sorted = new ArrayList<>(size);
+    while (size > 0) {
+      T min = heap.getRoot(--size);
+      sorted.add(min);
+    }
+
+    return sorted;
+  }
+}
diff --git a/src/main/com/java/sorts/QuickSort.java b/src/main/com/java/sorts/QuickSort.java
@@ -0,0 +1,65 @@
+package src.main.com.java.sorts;
+
+import static src.main.com.java.sorts.SortUtils.less;
+import static src.main.com.java.sorts.SortUtils.swap;
+
+public class QuickSort {
+
+
+  /**
+   * This method implements the Generic Quick Sort
+   *
+   * @param array The array to be sorted
+   *              Sorts the array in increasing order
+   **/
+  public <T extends Comparable<T>> T[] sort(T[] array) {
+    doSort(array, 0, array.length - 1);
+    return array;
+  }
+
+
+  /**
+   * The sorting process
+   *
+   * @param left  The first index of an array
+   * @param right The last index of an array
+   * @param array The array to be sorted
+   **/
+
+  private static <T extends Comparable<T>> void doSort(T[] array, int left, int right) {
+    if (left < right) {
+      int pivot = partition(array, left, right);
+      doSort(array, left, pivot - 1);
+      doSort(array, pivot, right);
+    }
+  }
+
+  /**
+   * This method finds the partition index for an array
+   *
+   * @param array The array to be sorted
+   * @param left  The first index of an array
+   * @param right The last index of an array
+   *              Finds the partition index of an array
+   **/
+
+  private static <T extends Comparable<T>> int partition(T[] array, int left, int right) {
+    int mid = (left + right) / 2;
+    T pivot = array[mid];
+
+    while (left <= right) {
+      while (less(array[left], pivot)) {
+        ++left;
+      }
+      while (less(pivot, array[right])) {
+        --right;
+      }
+      if (left <= right) {
+        swap(array, left, right);
+        ++left;
+        --right;
+      }
+    }
+    return left;
+  }
+}
diff --git a/src/main/com/java/sorts/SelectionSort.java b/src/main/com/java/sorts/SelectionSort.java
@@ -0,0 +1,32 @@
+package src.main.com.java.sorts;
+
+import static src.main.com.java.sorts.SortUtils.less;
+import static src.main.com.java.sorts.SortUtils.swap;
+
+public class SelectionSort {
+
+  /**
+   * This method implements the Generic Selection Sort
+   *
+   * @param arr The array to be sorted
+   *            Sorts the array in increasing order
+   **/
+  public <T extends Comparable<T>> T[] sort(T[] arr) {
+    int n = arr.length;
+    for (int i = 0; i < n - 1; i++) {
+      // Initial index of min
+      int min = i;
+      for (int j = i + 1; j < n; j++) {
+        if (less(arr[j], arr[min])) {
+          min = j;
+        }
+      }
+      // Swapping if index of min is changed
+      if (min != i) {
+        swap(arr, i, min);
+      }
+    }
+
+    return arr;
+  }
+}
diff --git a/src/main/com/java/sorts/ShellSort.java b/src/main/com/java/sorts/ShellSort.java
@@ -0,0 +1,32 @@
+package src.main.com.java.sorts;
+
+import static src.main.com.java.sorts.SortUtils.less;
+import static src.main.com.java.sorts.SortUtils.swap;
+
+public class ShellSort {
+
+  /**
+   * This method implements Generic Shell Sort.
+   *
+   * @param array The array to be sorted
+   */
+  public <T extends Comparable<T>> T[] sort(T[] array) {
+    int length = array.length;
+    int n = 1;
+
+    while (n < length / 3) {
+      n = 3 * n + 1;
+    }
+
+    while (n >= 1) {
+      for (int i = n; i < length; i++) {
+        for (int j = i; j >= n && less(array[j], array[j - n]); j -= n) {
+          swap(array, j, j - n);
+        }
+      }
+      n /= 3;
+    }
+
+    return array;
+  }
+}
diff --git a/src/main/com/java/sorts/SortUtils.java b/src/main/com/java/sorts/SortUtils.java
@@ -0,0 +1,45 @@
+package src.main.com.java.sorts;
+
+final class SortUtils {
+
+
+  /**
+   * Helper method for swapping places in array
+   *
+   * @param array The array which elements we want to swap
+   * @param idx   index of the first element
+   * @param idy   index of the second element
+   */
+  static <T> boolean swap(T[] array, int idx, int idy) {
+    T swap = array[idx];
+    array[idx] = array[idy];
+    array[idy] = swap;
+    return true;
+  }
+
+
+  /**
+   * This method checks if first element is less then the other element
+   *
+   * @param v first element
+   * @param w second element
+   * @return true if the first element is less then the second element
+   */
+  static <T extends Comparable<T>> boolean less(T v, T w) {
+    return v.compareTo(w) < 0;
+  }
+
+
+  /**
+   * Swaps all position from {@param left} to @{@param right} for {@param array}
+   *
+   * @param array is an array
+   * @param left  is a left flip border of the array
+   * @param right is a right flip border of the array
+   */
+  static <T extends Comparable<T>> void flip(T[] array, int left, int right) {
+    while (left <= right) {
+      swap(array, left++, right--);
+    }
+  }
+}
diff --git a/src/test/com/java/sorts/BubbleSortTest.java b/src/test/com/java/sorts/BubbleSortTest.java
@@ -0,0 +1,29 @@
+package src.test.com.java.sorts;
+
+
+import org.junit.Assert;
+import org.junit.Test;
+import src.main.com.java.sorts.BubbleSort;
+
+import java.util.Arrays;
+
+public class BubbleSortTest {
+
+  @Test
+  public void bubbleSortTest() {
+    BubbleSort bubbleSort = new BubbleSort();
+    Integer[] unsortedInt = new Integer[]{0, 5, 9, 2, 1, 3, 4, 8, 6, 7};
+    Integer[] sortedInt = new Integer[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
+    System.out.println(Arrays.toString(bubbleSort.sort(unsortedInt)));
+
+    Assert.assertArrayEquals(sortedInt, bubbleSort.sort(unsortedInt));
+
+    Character[] unsortedChar = new Character[]{'f', 'h', 'c', 'a', 'b', 'd', 'g', 'e'};
+    Character[] sortedChar = new Character[]{'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'};
+    System.out.println(Arrays.toString(bubbleSort.sort(unsortedChar)));
+
+    Assert.assertArrayEquals(sortedChar, bubbleSort.sort(unsortedChar));
+
+  }
+
+}
diff --git a/src/test/com/java/sorts/HeapSortTest.java b/src/test/com/java/sorts/HeapSortTest.java
@@ -0,0 +1,27 @@
+package src.test.com.java.sorts;
+
+
+import org.junit.Assert;
+import org.junit.Test;
+import src.main.com.java.sorts.HeapSort;
+
+import java.util.Arrays;
+
+public class HeapSortTest {
+
+  @Test
+  public void heapSortTest() {
+    HeapSort heapSort = new HeapSort();
+    Integer[] unsortedInt = new Integer[]{0, 5, 9, 2, 1, 3, 4, 8, 6, 7};
+    Integer[] sortedInt = new Integer[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
+    System.out.println(Arrays.toString(heapSort.sort(unsortedInt)));
+
+    Assert.assertArrayEquals(sortedInt, heapSort.sort(unsortedInt));
+
+    Character[] unsortedChar = new Character[]{'f', 'h', 'c', 'a', 'b', 'd', 'g', 'e'};
+    Character[] sortedChar = new Character[]{'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'};
+    System.out.println(Arrays.toString(heapSort.sort(unsortedChar)));
+
+    Assert.assertArrayEquals(sortedChar, heapSort.sort(unsortedChar));
+  }
+}
diff --git a/src/test/com/java/sorts/QuickSortTest.java b/src/test/com/java/sorts/QuickSortTest.java
diff --git a/src/test/com/java/sorts/SelectionSortTest.java b/src/test/com/java/sorts/SelectionSortTest.java
diff --git a/src/test/com/java/sorts/ShellSortTest.java b/src/test/com/java/sorts/ShellSortTest.java
