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/.cproject | 418 +++++++++-----------------
PlaygroundCpp/.project | 2 +-
PlaygroundCpp/.settings/language.settings.xml | 67 ++---
PlaygroundCpp/Sources/Playground.cpp | 88 ++++--
4 files changed, 225 insertions(+), 350 deletions(-)
diff --git a/PlaygroundCpp/.cproject b/PlaygroundCpp/.cproject
index 83e6d3d..5a9934f 100644
--- a/PlaygroundCpp/.cproject
+++ b/PlaygroundCpp/.cproject
@@ -1,282 +1,142 @@
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
diff --git a/PlaygroundCpp/.project b/PlaygroundCpp/.project
index c294861..7abf47f 100644
--- a/PlaygroundCpp/.project
+++ b/PlaygroundCpp/.project
@@ -1,6 +1,6 @@
- PlaygroundCpp
+ AlgoDesignAndTechniqueEdxCpp
diff --git a/PlaygroundCpp/.settings/language.settings.xml b/PlaygroundCpp/.settings/language.settings.xml
index f5ddb15..aa6e0c9 100644
--- a/PlaygroundCpp/.settings/language.settings.xml
+++ b/PlaygroundCpp/.settings/language.settings.xml
@@ -1,48 +1,25 @@
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
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
#include
+#include
//#include
using std::vector;
+using std::swap;
-int conquer(vector &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 &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 partition3(vector &a, int l, int r) {
+ int x = a[l];
+ int j = l;
+ int dupCount = 0;
+ int biggerNumCount = 0;
-int get_majority_element(vector &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 m = { j, j + dupCount };
+ return m;
+}
+
+void randomized_quick_sort(vector &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 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 a = { 1, 1 };
-// ASSERT_EQ(get_majority_element(a, 0, a.size()-1), 1);
+
+//TEST(ImprovedQuickSort, test1) {
+// vector a = { 2, 3, 9, 2, 2 };
+// vector 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