summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2018-11-23 16:16:01 -0600
committerHaidong Ji2018-11-23 16:16:01 -0600
commit34f8120152911f97b5c9a5748bd1c9b0aab00210 (patch)
tree6ba9a06e012b100da45ba76db7e525e83528c86e
parent81692fe3e2b51ba1dfffe7724e1e31000abe07e2 (diff)
Improved QuickSort done!
Once again, a lot of fun. PythonTutor's visualization was extremely helpful!
-rw-r--r--AlgoDesignAndTechniqueEdxJava/.classpath6
-rw-r--r--AlgoDesignAndTechniqueEdxJava/.settings/org.eclipse.jdt.core.prefs7
-rw-r--r--AlgoDesignAndTechniqueEdxJava/sources/Sorting.java115
-rw-r--r--AlgoDesignAndTechniqueEdxJava/tests/SortingTest.java39
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);
+ }
+
+}