From 34f8120152911f97b5c9a5748bd1c9b0aab00210 Mon Sep 17 00:00:00 2001 From: Haidong Ji Date: Fri, 23 Nov 2018 16:16:01 -0600 Subject: Improved QuickSort done! Once again, a lot of fun. PythonTutor's visualization was extremely helpful!--- AlgoDesignAndTechniqueEdxJava/.classpath | 6 +- .../.settings/org.eclipse.jdt.core.prefs | 7 +- AlgoDesignAndTechniqueEdxJava/sources/Sorting.java | 115 +++++++++++++++++++++ .../tests/SortingTest.java | 39 +++++++ 4 files changed, 159 insertions(+), 8 deletions(-) create mode 100644 AlgoDesignAndTechniqueEdxJava/sources/Sorting.java create mode 100644 AlgoDesignAndTechniqueEdxJava/tests/SortingTest.java diff --git a/AlgoDesignAndTechniqueEdxJava/.classpath b/AlgoDesignAndTechniqueEdxJava/.classpath index 2e7b73a..21b267b 100644 --- a/AlgoDesignAndTechniqueEdxJava/.classpath +++ b/AlgoDesignAndTechniqueEdxJava/.classpath @@ -1,12 +1,8 @@ - - - - - + 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); + } + +} -- cgit v1.2.3