Merge pull request TheAlgorithms#87 from varunu28/master

AnupKumarPanwar · web-flow · commit affcbac394c4 · 2017-08-27T10:38:02.000+05:30
Updated QuickSort.java
diff --git a/Sorts/MergeSort.java b/Sorts/MergeSort.java
@@ -1,109 +1,100 @@
-import java.util.Scanner;
-
 /**
- * This class implements MergeSort
- * @author Unknown
+ *
+ * @author Varun Upadhyay (https://github.com/varunu28)
  *
  */
-public class MergeSort {
-	/** Array for mergeSort*/
-    private int[] array;
-    /** Temp Merge Array*/
-    private int[] tempMergArr;
-    /** Length of the array*/
-    private int length;
 
-    /**
-     * Sorts inputArr with merge sort algorithm
-     * 
-     * @param inputArr Array to be sorted
-     */
-    public final void sort(int inputArr[]) {
-        this.array = inputArr;
-        this.length = inputArr.length;
-        this.tempMergArr = new int[this.length];
-        this.mergeSort(0, this.length - 1);
-    }
+class MergeSort {
 
     /**
-     * Partitions Array into recursively smaller pieces
+     * This method implements the Generic Merge Sort
      *
-     * @param lowerIndex lower bound to include in the first partition
-     * @param higherIndex upper bound to include in the third partition
-     */
-    private void mergeSort(int lowerIndex, int higherIndex) {
-        if (lowerIndex < higherIndex) {
-            int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
-            // Below step sorts the left side of the array
-            this.mergeSort(lowerIndex, middle);
-            // Below step sorts the right side of the array
-            this.mergeSort(middle + 1, higherIndex);
-            // Now merge both sides
-            this.mergeParts(lowerIndex, middle, higherIndex);
+     * @param arr The array to be sorted
+     * @param temp The copy of the actual array
+     * @param left The first index of the array
+     * @param right The last index of the array
+     * Recursively sorts the array in increasing order
+     **/
+
+    public static <T extends Comparable<T>> void MS(T[] arr, T[] temp, int left, int right) {
+        if (left < right) {
+            int mid = left + (right - left) / 2;
+            MS(arr, temp, left, mid);
+            MS(arr,  temp,mid + 1, right);
+            merge(arr, temp, left, mid, right);
         }
+
     }
 
     /**
-     * Merges partitions
+     * This method implements the merge step of the merge sort
      *
-     * @param lowerIndex The lower index
-     * @param middle The middle index
-     * @param higherIndex The higher index
-     */
-    private void mergeParts(int lowerIndex, int middle, int higherIndex) {
-        for (int i = lowerIndex; i <= higherIndex; i++) {
-            this.tempMergArr[i] = this.array[i];
+     * @param arr The array to be sorted
+     * @param temp The copy of the actual array
+     * @param left The first index of the array
+     * @param mid The middle index of the array
+     * @param right The last index of the array
+     * merges two parts of an array in increasing order
+     **/
+
+    public static <T extends Comparable<T>> void merge(T[] arr, T[] temp, int left, int mid, int right) {
+        for (int i=left;i<=right;i++) {
+            temp[i] = arr[i];
         }
-        int i = lowerIndex;
-        int j = middle + 1;
-        int k = lowerIndex;
-        while (i <= middle && j <= higherIndex) {
-            if (this.tempMergArr[i] <= this.tempMergArr[j]) {
-                this.array[k] = this.tempMergArr[i];
+
+        int i= left;
+        int j = mid + 1;
+        int k = left;
+
+        while (i<=mid && j<=right) {
+            if (temp[i].compareTo(temp[j]) <= 0) {
+                arr[k] = temp[i];
                 i++;
-            } else {
-                this.array[k] = this.tempMergArr[j];
+            }
+            else {
+                arr[k] = temp[j];
                 j++;
             }
             k++;
         }
-        while (i <= middle) {
-            this.array[k] = this.tempMergArr[i];
-            k++;
+
+        while (i <= mid) {
+            arr[k] = temp[i];
             i++;
+            k++;
         }
-
     }
 
-    /**
-     * Gets input to sort
-     *
-     * @return unsorted array of integers to sort
-     */
-    public static int[] getInput() {
-        final int numElements = 6;
-        int[] unsorted = new int[numElements];
-        Scanner input = new Scanner(System.in);
-        System.out.println("Enter any 6 Numbers for Unsorted Array : ");
-        for (int i = 0; i < numElements; i++) {
-            unsorted[i] = input.nextInt();
+    // Driver program
+    public static void main(String[] args) {
+
+        // Integer Input
+        int[] arr = {4,23,6,78,1,54,231,9,12};
+        Integer[] array = new Integer[arr.length];
+        for (int i=0;i<array.length;i++) {
+            array[i] = arr[i];
         }
-        input.close();
-        return unsorted;
-    }
 
-    /**
-     * Main Method
-     *
-     * @param args Command line arguments
-     */
-    public static void main(String args[]) {
-        int[] inputArr = getInput();
-        MergeSort mergeSort = new MergeSort();
-        mergeSort.sort(inputArr);
-        for (int i : inputArr) {
-            System.out.print(i);
-            System.out.print(" ");
+        // Copy of actual array
+        Integer[] temp = new Integer[arr.length];
+
+        MS(array, temp, 0, arr.length-1);
+
+        // Output => 1	   4  	 6	9	12	23	54	78	231
+        for (int i=0;i<arr.length;i++) {
+            System.out.print(array[i] + " ");
+        }
+        System.out.println();
+
+        // String Input
+        String[] array1 = {"c", "a", "e", "b","d"};
+        String[] temp1 = new String[array1.length];
+        MS(array1, temp1, 0, array1.length-1);
+
+        //Output => a	b	c	d	e
+        for(int i=0; i<array1.length; i++)
+        {
+            System.out.print(array1[i]+"\t");
         }
     }
 }
diff --git a/Sorts/QuickSort.java b/Sorts/QuickSort.java
@@ -0,0 +1,93 @@
+/**
+ *
+ * @author Varun Upadhyay (https://github.com/varunu28)
+ *
+ */
+
+class QuickSort {
+
+    /**
+     * This method implements the Generic Quick Sort
+     *
+     * @param array The array to be sorted
+     * @param start The first index of an array
+     * @param end The last index of an array
+     * Sorts the array in increasing order
+     **/
+
+    public static <T extends Comparable<T>> void QS(T array[], int start, int end) {
+        if (start < end) {
+            int PIndex = partition(array, start, end);
+            QS(array, start, PIndex - 1);
+            QS(array, PIndex + 1, end);
+        }
+    }
+
+    /**
+     * This method finds the partition index for an array
+     *
+     * @param array The array to be sorted
+     * @param start The first index of an array
+     * @param end The last index of an array
+     * Finds the partition index of an array
+     **/
+
+    public static <T extends Comparable<T>> int partition(T array[], int start, int end) {
+        T pivot = array[end];
+        int PIndex = start;
+        for (int i=start;i<end;i++) {
+            if (array[i].compareTo(pivot) <= 0) {
+                swap(array, i, PIndex);
+                PIndex++;
+            }
+        }
+        swap(array, PIndex, end);
+        return PIndex;
+    }
+
+    /**
+     * This method swaps two elements of an array
+     *
+     * @param array The array to be sorted
+     * @param initial The first element
+     * @param fin The second element
+     * Swaps initial and fin element
+     **/
+
+    public static <T extends Comparable<T>> void swap(T[] array, int initial, int fin) {
+        T temp = array[initial];
+        array[initial] = array[fin];
+        array[fin] = temp;
+    }
+
+    // Driver Program
+    public static void main(String[] args) {
+
+        // For integer input
+        int[] arr = {3,4,1,32,0,2,44,111,5};
+        Integer[] array = new Integer[arr.length];
+        for (int i=0;i<arr.length;i++) {
+            array[i] = arr[i];
+        }
+
+        QS(array, 0, arr.length-1);
+
+        //Output => 0 1 2 3 4 5 32 44 111
+        for (int i=0;i<array.length;i++) {
+            System.out.print(array[i] + " ");
+        }
+        System.out.println();
+
+        // String Input
+        String[] array1 = {"c", "a", "e", "b","d"};
+
+        QS(array1, 0,array1.length-1);
+
+        //Output => a	b	c	d	e
+        for(int i=0; i<array1.length; i++)
+        {
+            System.out.print(array1[i]+"\t");
+        }
+    }
+}
+
diff --git a/Sorts/Quicksort.java b/Sorts/Quicksort.java
