From bed42c90e74f917bc155936e309211a57d724112 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Fri, 23 Nov 2018 20:44:11 -0600
Subject: Improved QuickSort done!

---
 PlaygroundCpp/Sources/Playground.cpp | 88 ++++++++++++++++++++++++++----------
 1 file changed, 63 insertions(+), 25 deletions(-)

(limited to 'PlaygroundCpp/Sources')

diff --git a/PlaygroundCpp/Sources/Playground.cpp b/PlaygroundCpp/Sources/Playground.cpp
index e9f516d..6cd3f7a 100644
--- a/PlaygroundCpp/Sources/Playground.cpp
+++ b/PlaygroundCpp/Sources/Playground.cpp
@@ -1,37 +1,72 @@
 #include <vector>
 #include <iostream>
+#include <cstdlib>
 //#include <gtest/gtest.h>
 
 using std::vector;
+using std::swap;
 
-int conquer(vector<int> &a, int b, int c, int left, int right) {
-	int countB = 0;
-	int countC = 0;
-	for (int i = left; i < right + 1; i++) {
-		if (a[i] == b)
-			countB++;
-		if (a[i] == c)
-			countC++;
+int partition2(vector<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++;
+			swap(a[i], a[j]);
+		}
 	}
-	if (countB > (right - left + 1) / 2)
-		return b;
-	if (countC > (right - left + 1) / 2)
-		return c;
-	return -1;
+	swap(a[l], a[j]);
+	return j;
 }
+vector<int> partition3(vector<int> &a, int l, int r) {
+	int x = a[l];
+	int j = l;
+	int dupCount = 0;
+	int biggerNumCount = 0;
 
-int get_majority_element(vector<int> &a, int left, int right) {
-	if (left == right)
-		return a[left];
-	int middle = (right - left) / 2;
-	int b = get_majority_element(a, left, left + middle);
-	int c = get_majority_element(a, left + middle + 1, right);
-	int d = conquer(a, b, c, left, right);
-	return d;
+	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++;
+	}
+	vector<int> m = { j, j + dupCount };
+	return m;
+}
+
+void randomized_quick_sort(vector<int> &a, int l, int r) {
+	if (l >= r) {
+		return;
+	}
+
+	int k = l + rand() % (r - l + 1);
+	swap(a[l], a[k]);
+//	int m = partition2(a, l, r);
+
+	vector<int> m = partition3(a, l, r);
+
+	randomized_quick_sort(a, l, m[0] - 1);
+	randomized_quick_sort(a, m[1] + 1, r);
 }
-//TEST(MajorityElement, test1) {
-//	vector<int> a = { 1, 1 };
-//	ASSERT_EQ(get_majority_element(a, 0, a.size()-1), 1);
+
+//TEST(ImprovedQuickSort, test1) {
+//	vector<int> a = { 2, 3, 9, 2, 2 };
+//	vector<int> result = { 2, 2, 2, 3, 9 };
+//	randomized_quick_sort(a, 0, a.size() - 1);
+//	ASSERT_EQ(result, a);
 //}
 
 int main() {
@@ -41,5 +76,8 @@ int main() {
 	for (size_t i = 0; i < a.size(); ++i) {
 		std::cin >> a[i];
 	}
-	std::cout << (get_majority_element(a, 0, n - 1) != -1) << '\n';
+	randomized_quick_sort(a, 0, a.size() - 1);
+	for (size_t i = 0; i < a.size(); ++i) {
+		std::cout << a[i] << ' ';
+	}
 }
-- 
cgit v1.2.3