Improved QuickSort done!

Once again, a lot of fun. PythonTutor's visualization was extremely
helpful!

4 files changed, 159 insertions, 8 deletions

diff --git a/AlgoDesignAndTechniqueEdxJava/.classpath b/AlgoDesignAndTechniqueEdxJava/.classpath
index 2e7b73a..21b267b 100644
--- a/AlgoDesignAndTechniqueEdxJava/.classpath
+++ b/AlgoDesignAndTechniqueEdxJava/.classpath
@@ -1,12 +1,8 @@
 <?xml version="1.0" encoding="UTF-8"?>
 <classpath>
-	<classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER/org.eclipse.jdt.internal.debug.ui.launcher.StandardVMType/JavaSE-9">
-		<attributes>
-			<attribute name="module" value="true"/>
-		</attributes>
-	</classpathentry>
 	<classpathentry kind="src" path="sources"/>
 	<classpathentry kind="src" path="tests"/>
 	<classpathentry kind="con" path="org.eclipse.jdt.junit.JUNIT_CONTAINER/5"/>
+	<classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER"/>
 	<classpathentry kind="output" path="bin"/>
 </classpath>
diff --git a/AlgoDesignAndTechniqueEdxJava/.settings/org.eclipse.jdt.core.prefs b/AlgoDesignAndTechniqueEdxJava/.settings/org.eclipse.jdt.core.prefs
index 021167a..25e312a 100644
--- a/AlgoDesignAndTechniqueEdxJava/.settings/org.eclipse.jdt.core.prefs
+++ b/AlgoDesignAndTechniqueEdxJava/.settings/org.eclipse.jdt.core.prefs
@@ -1,12 +1,13 @@
 eclipse.preferences.version=1
 org.eclipse.jdt.core.compiler.codegen.inlineJsrBytecode=enabled
-org.eclipse.jdt.core.compiler.codegen.targetPlatform=9
+org.eclipse.jdt.core.compiler.codegen.methodParameters=do not generate
+org.eclipse.jdt.core.compiler.codegen.targetPlatform=1.8
 org.eclipse.jdt.core.compiler.codegen.unusedLocal=preserve
-org.eclipse.jdt.core.compiler.compliance=9
+org.eclipse.jdt.core.compiler.compliance=1.8
 org.eclipse.jdt.core.compiler.debug.lineNumber=generate
 org.eclipse.jdt.core.compiler.debug.localVariable=generate
 org.eclipse.jdt.core.compiler.debug.sourceFile=generate
 org.eclipse.jdt.core.compiler.problem.assertIdentifier=error
 org.eclipse.jdt.core.compiler.problem.enumIdentifier=error
 org.eclipse.jdt.core.compiler.release=enabled
-org.eclipse.jdt.core.compiler.source=9
+org.eclipse.jdt.core.compiler.source=1.8
diff --git a/AlgoDesignAndTechniqueEdxJava/sources/Sorting.java b/AlgoDesignAndTechniqueEdxJava/sources/Sorting.java
new file mode 100644
index 0000000..1f42012
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/sources/Sorting.java
@@ -0,0 +1,115 @@
+import java.io.BufferedReader;
+import java.io.IOException;
+import java.io.InputStream;
+import java.io.InputStreamReader;
+import java.util.Random;
+import java.util.StringTokenizer;
+
+public class Sorting {
+	private static Random random = new Random();
+
+	private static int[] partition3(int[] a, int l, int r) {
+		int x = a[l];
+		int j = l;
+		int dupCount = 0;
+		int biggerNumCount = 0;
+
+		for (int i = l + 1; i <= r; i++) {
+			if (a[i] < x) {
+				int t = a[i];
+				a[j] = t;
+				t = a[i - biggerNumCount];
+				a[i] = t;
+				a[i - biggerNumCount] = x;
+				j++;
+				continue;
+			}
+			if (a[i] == x) {
+				int t = a[j + dupCount + 1];
+				a[i] = t;
+				a[j + dupCount + 1] = x;
+				dupCount++;
+				continue;
+			}
+			biggerNumCount++;
+		}
+		int[] m = { j, j + dupCount };
+		return m;
+	}
+
+	private static int partition2(int[] a, int l, int r) {
+		int x = a[l];
+		int j = l;
+		for (int i = l + 1; i <= r; i++) {
+			if (a[i] <= x) {
+				j++;
+				int t = a[i];
+				a[i] = a[j];
+				a[j] = t;
+			}
+		}
+		int t = a[l];
+		a[l] = a[j];
+		a[j] = t;
+		return j;
+	}
+
+	public static void randomizedQuickSort(int[] a, int l, int r) {
+		if (l >= r) {
+			return;
+		}
+		int k = random.nextInt(r - l + 1) + l;
+		int t = a[l];
+		a[l] = a[k];
+		a[k] = t;
+
+//		int m = partition2(a, l, r);
+//		randomizedQuickSort(a, l, m - 1);
+//		randomizedQuickSort(a, m + 1, r);
+		// use partition3
+		int[] m = partition3(a, l, r);
+		randomizedQuickSort(a, l, m[0] - 1);
+		randomizedQuickSort(a, m[1] + 1, r);
+	}
+
+	public static void main(String[] args) {
+		FastScanner scanner = new FastScanner(System.in);
+		int n = scanner.nextInt();
+		int[] a = new int[n];
+		for (int i = 0; i < n; i++) {
+			a[i] = scanner.nextInt();
+		}
+		randomizedQuickSort(a, 0, n - 1);
+		for (int i = 0; i < n; i++) {
+			System.out.print(a[i] + " ");
+		}
+	}
+
+	static class FastScanner {
+		BufferedReader br;
+		StringTokenizer st;
+
+		FastScanner(InputStream stream) {
+			try {
+				br = new BufferedReader(new InputStreamReader(stream));
+			} catch (Exception e) {
+				e.printStackTrace();
+			}
+		}
+
+		String next() {
+			while (st == null || !st.hasMoreTokens()) {
+				try {
+					st = new StringTokenizer(br.readLine());
+				} catch (IOException e) {
+					e.printStackTrace();
+				}
+			}
+			return st.nextToken();
+		}
+
+		int nextInt() {
+			return Integer.parseInt(next());
+		}
+	}
+}
diff --git a/AlgoDesignAndTechniqueEdxJava/tests/SortingTest.java b/AlgoDesignAndTechniqueEdxJava/tests/SortingTest.java
new file mode 100644
index 0000000..7149edf
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/tests/SortingTest.java
@@ -0,0 +1,39 @@
+import static org.junit.jupiter.api.Assertions.*;
+
+import org.junit.jupiter.api.Test;
+
+class SortingTest {
+
+	@Test
+	void testSorting0() {
+		int[] a = { 2, 3, 9, 2, 2 };
+		int[] result = { 2, 2, 2, 3, 9 };
+		Sorting.randomizedQuickSort(a, 0, a.length - 1);
+		assertArrayEquals(result, a);
+	}
+
+	@Test
+	void testSorting1() {
+		int[] a = { 2, 3, 9, 2, 9 };
+		int[] result = { 2, 2, 3, 9, 9 };
+		Sorting.randomizedQuickSort(a, 0, a.length - 1);
+		assertArrayEquals(result, a);
+	}
+
+	@Test
+	void testSorting2() {
+		int[] a = { 2 };
+		int[] result = { 2 };
+		Sorting.randomizedQuickSort(a, 0, a.length - 1);
+		assertArrayEquals(result, a);
+	}
+
+	@Test
+	void testSorting3() {
+		int[] a = { 2, 1 };
+		int[] result = { 1, 2 };
+		Sorting.randomizedQuickSort(a, 0, a.length - 1);
+		assertArrayEquals(result, a);
+	}
+
+}