From 8012f4eeafb775e7edc2c01e99e2a156d2fdb1d5 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Wed, 28 Nov 2018 21:40:29 -0600
Subject: 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.---
 PlaygroundCpp/Sources/Playground.cpp | 110 ++++++++++++++---------------------
 1 file 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';
 }
-- 
cgit v1.2.3