diff options
author | Haidong Ji | 2018-11-23 16:16:01 -0600 |
---|---|---|
committer | Haidong Ji | 2018-11-23 16:16:01 -0600 |
commit | 34f8120152911f97b5c9a5748bd1c9b0aab00210 (patch) | |
tree | 6ba9a06e012b100da45ba76db7e525e83528c86e /AlgoDesignAndTechniqueEdxJava/sources | |
parent | 81692fe3e2b51ba1dfffe7724e1e31000abe07e2 (diff) |
Improved QuickSort done!
Once again, a lot of fun. PythonTutor's visualization was extremely
helpful!
Diffstat (limited to 'AlgoDesignAndTechniqueEdxJava/sources')
-rw-r--r-- | AlgoDesignAndTechniqueEdxJava/sources/Sorting.java | 115 |
1 files changed, 115 insertions, 0 deletions
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()); + } + } +} |