summaryrefslogtreecommitdiff
path: root/PlaygroundCpp/Sources
diff options
context:
space:
mode:
authorHaidong Ji2018-11-28 21:40:29 -0600
committerHaidong Ji2018-11-28 21:40:29 -0600
commit8012f4eeafb775e7edc2c01e99e2a156d2fdb1d5 (patch)
tree78d3bd0ab7ca04a2e105a7671e714a2b5d63d57c /PlaygroundCpp/Sources
parentbed42c90e74f917bc155936e309211a57d724112 (diff)
Inversion count done!
Worked out the algo earlier, but the challenge was to learn to use vector in C++ and vector slicing. I got bad allocation error initially due to misunderstanding that the end is not inclusive: that is, vector.begin() + m reaches vector.begin() + m-1.
Diffstat (limited to 'PlaygroundCpp/Sources')
-rw-r--r--PlaygroundCpp/Sources/Playground.cpp110
1 files changed, 44 insertions, 66 deletions
diff --git a/PlaygroundCpp/Sources/Playground.cpp b/PlaygroundCpp/Sources/Playground.cpp
index 6cd3f7a..aff2024 100644
--- a/PlaygroundCpp/Sources/Playground.cpp
+++ b/PlaygroundCpp/Sources/Playground.cpp
@@ -1,83 +1,61 @@
#include <vector>
#include <iostream>
-#include <cstdlib>
//#include <gtest/gtest.h>
using std::vector;
-using std::swap;
-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]);
+long mergeInversionCount(vector<int> &B, vector<int> &C, vector<int> &D) {
+ long count = 0;
+ while (B.size() != 0 && C.size() != 0) {
+ int b = B[0];
+ int c = C[0];
+ if (b <= c) {
+ D.push_back(b);
+ B.erase(B.begin());
+ } else {
+ count += B.size();
+ D.push_back(c);
+ C.erase(C.begin());
}
}
- swap(a[l], a[j]);
- return j;
+ D.insert(D.end(), B.begin(), B.end());
+ D.insert(D.end(), C.begin(), C.end());
+ return count;
}
-vector<int> partition3(vector<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++;
+long getInversionCountFromList(vector<int> &A, vector<int> &D) {
+ long numberOfInversions = 0;
+ if (A.size() == 1) {
+ D.push_back(A[0]);
+ return 0;
}
- vector<int> m = { j, j + dupCount };
- return m;
+ int m = A.size() / 2;
+ vector<int> D1;
+ vector<int>::const_iterator first = A.begin();
+ vector<int>::const_iterator last = A.begin() + m;
+ vector<int> newVec(first, last);
+ numberOfInversions += getInversionCountFromList(newVec, D1);
+ vector<int> D2;
+ vector<int>::const_iterator ffirst = A.begin() + m;
+ vector<int>::const_iterator llast = A.end();
+ vector<int> newVecc(ffirst, llast);
+ numberOfInversions += getInversionCountFromList(newVecc, D2);
+ long mergeCount = mergeInversionCount(D1, D2, D);
+ return numberOfInversions + mergeCount;
}
-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(ImprovedQuickSort, test1) {
+//TEST(InversionCount, 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);
+// vector<int> result(5);
+// ASSERT_EQ(4, getInversionCountFromList(a, result));
//}
int main() {
- int n;
- std::cin >> n;
- vector<int> a(n);
- for (size_t i = 0; i < a.size(); ++i) {
- std::cin >> a[i];
- }
- randomized_quick_sort(a, 0, a.size() - 1);
- for (size_t i = 0; i < a.size(); ++i) {
- std::cout << a[i] << ' ';
- }
+ int n;
+ std::cin >> n;
+ vector<int> a(n);
+ for (size_t i = 0; i < a.size(); i++) {
+ std::cin >> a[i];
+ }
+ vector<int> b(a.size());
+ std::cout << getInversionCountFromList(a, b) << '\n';
}