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());
+		}
+	}
+}