Merge pull request thuva4#267 from AtoMc/master

thuva4 · web-flow · commit b6abb7cdba94 · 2017-10-20T13:26:21.000+05:30
Add Quickselect for Java
diff --git a/CONTRIBUTING.md b/CONTRIBUTING.md
@@ -130,4 +130,5 @@ Unfortunately, sometimes the bug can be only reproduced in your project or in yo
 - [tushar-dtu](https://github.com/tushar-dtu)
 - [AymanASamyM](https://github.com/AymanASamyM)
 - [arunpyasi](https://github.com/arunpyasi)
-- [Akos Kovacs](https://github.com/plaidshirtakos)
+- [Akos Kovacs](https://github.com/plaidshirtakos)
+- [AtoMc](https://github.com/AtoMc)
diff --git a/Doomsday/Java/Doomsday.java b/Doomsday/Java/Doomsday.java
@@ -18,7 +18,7 @@ public class Doomsday {
 	public static int dow(int y, int m, int d) {
 		final int[] t = { 0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4 };
 		y -= (m < 3) ? 1 : 0;
-	    return (y + y/4 - y/100 + y/400 + t[m-1] + d) % 7;
+		return (y + y/4 - y/100 + y/400 + t[m-1] + d) % 7;
 	}
 	
 	/**
diff --git a/QuickSelect/Java/QuickSelect.java b/QuickSelect/Java/QuickSelect.java
@@ -0,0 +1,70 @@
+/**
+ * Find the kth smallest element in an unordered array.
+ * 
+ * @author Atom
+ * @see <a href="https://en.wikipedia.org/wiki/Quickselect">Quickselect</a>
+ */
+public class QuickSelect {
+	
+	/**
+	 * Lomuto partition scheme
+	 * 
+	 * @param arr
+	 * @param low
+	 * @param high
+	 * @return the pivot's final location
+	 */
+	private static <T extends Comparable<? super T>> int partition(final T[] arr, final int low, final int high) {
+		T pivot = arr[high];
+		int index = low;
+		for (int i = low; i < high; i++) {
+			if (arr[i].compareTo(pivot) <= 0) {
+				swap(arr, i, index);
+				index++;
+			}
+		}
+		swap(arr, index, high);
+		return index;
+	}
+	
+	/**
+	 * Find the kth smallest element in an unordered array.
+	 * 
+	 * @param arr
+	 * @param kth from 0 to arr.length - 1
+	 * @return kth smallest element
+	 */
+	public static <T extends Comparable<? super T>> T select(final T[] arr, final int kth) {
+		if (kth < 0 || kth > arr.length - 1) throw new IllegalArgumentException("elements in the array = " + arr.length + ", kth(0..length-1) = " + kth);
+		
+		int left = 0;
+		int right = arr.length - 1;
+		while (right >= left) {
+			int pivotIndex = partition(arr, left, right);
+			if (kth == pivotIndex) {
+				return arr[pivotIndex];
+			} else if (kth < pivotIndex) {
+				right = pivotIndex - 1;
+			} else {
+				left = pivotIndex + 1;
+			}
+		}
+		return null;
+	}
+	
+	private static void swap(Object arr[], int i1, int i2) {
+		if (i1 == i2) { return; }
+		
+		Object temp = arr[i1];
+		arr[i1] = arr[i2];
+		arr[i2] = temp;
+	}
+	
+	public static void main(String[] args) {
+		for (int kth = 0; kth < 10; kth++) {
+			Integer[] a = { 1, 4, 2, 5, 0, 3, 9, 7, 6, 8 };
+			System.out.println("kth(" + kth + ") smallest element = " + select(a, kth));
+		}
+	}
+
+}
diff --git a/README.md b/README.md
@@ -44,7 +44,7 @@ MiniMaxWithABPruning | :+1: |  |  |  |  |  |  |  |
 Modified_Binary_Search |  |  |  | :+1: |  |  |  |  |
 Postman Sort |  |  |  | :+1: |  |  |  |  |
 Quick Sort | :+1: | :+1: |  |  | :+1: | :+1: | :+1: | :+1: |  :+1:
-Quick Select |  | :+1: |  |  |  |  | :+1: | |  
+Quick Select | :+1: | :+1: |  |  |  |  | :+1: | |  
 Uniform-cost search | :+1: |  |  |  |  | :+1: | :+1: |  |
 RadixSort | :+1: | :+1: |  |  | :+1: |  |  |  |
 RobinCarp | :+1: |  |  |  |  |  |  |  |
@@ -591,6 +591,8 @@ Union Find |:+1:|  |  |  |  |  |  |  |
 
 * Q-learning    :    learn an action-value function that gives the expected utility of taking a given action in a given state and following a fixed policy thereafter
 
+* [Quickselect](QuickSelect)    :    selection algorithm to find the kth smallest element in an unordered list
+
 * [Quicksort](QuickSort)    :    divide list into two, with all items on the first list coming before all items on the second list.; then sort the two lists. Often the method of choice
 
 * Quine&ndash;McCluskey algorithm    :    Also called as Q-M algorithm, programmable method for simplifying the boolean equations.

Original file line number	Diff line number	Diff line change
`@@ -18,7 +18,7 @@ public class Doomsday {`
`18`	`18`	`public static int dow(int y, int m, int d) {`
`19`	`19`	`final int[] t = { 0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4 };`
`20`	`20`	`y -= (m < 3) ? 1 : 0;`
`21`		`- return (y + y/4 - y/100 + y/400 + t[m-1] + d) % 7;`
	`21`	`+ return (y + y/4 - y/100 + y/400 + t[m-1] + d) % 7;`
`22`	`22`	`}`
`23`	`23`
`24`	`24`	`/**`