Algorithms : complete 01-algorithmic_toolbox 03-divide_and_conquer

5 files changed, 244 insertions, 41 deletions

diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/01-binary_search/binary_search.cpp b/01-algorithmic_toolbox/03-divide_and_conquer/01-binary_search/binary_search.cpp
index c93e2cf..40f8f01 100644
--- a/01-algorithmic_toolbox/03-divide_and_conquer/01-binary_search/binary_search.cpp
+++ b/01-algorithmic_toolbox/03-divide_and_conquer/01-binary_search/binary_search.cpp
@@ -4,9 +4,16 @@
 
 using std::vector;
 
-int binary_search(const vector<int> &a, int x) {
-  int left = 0, right = (int)a.size(); 
-  //write your code here
+int binary_search(const vector<int> &a, int x)
+{
+  int left = 0, right = (int) a.size();
+  while (left <= right) {
+      int mid = (left + right) / 2;
+      if (a[mid] == x) return mid;
+      if (a[mid] < x) left = (mid + 1);
+      else right = (mid - 1);
+  }
+  return -1;
 }
 
 int linear_search(const vector<int> &a, int x) {
@@ -30,7 +37,7 @@ int main() {
     std::cin >> b[i];
   }
   for (int i = 0; i < m; ++i) {
-    //replace with the call to binary_search when implemented
-    std::cout << linear_search(a, b[i]) << ' ';
+    std::cout << binary_search(a, b[i]) << ' ';
   }
+  std::cout << '\n';
 }
diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/02-majority_element/majority_element.cpp b/01-algorithmic_toolbox/03-divide_and_conquer/02-majority_element/majority_element.cpp
index 803db91..448eceb 100644
--- a/01-algorithmic_toolbox/03-divide_and_conquer/02-majority_element/majority_element.cpp
+++ b/01-algorithmic_toolbox/03-divide_and_conquer/02-majority_element/majority_element.cpp
@@ -3,12 +3,49 @@
 #include <vector>
 
 using std::vector;
+using std::swap;
 
-int get_majority_element(vector<int> &a, int left, int right) {
-  if (left == right) return -1;
-  if (left + 1 == right) return a[left];
-  //write your code here
-  return -1;
+int get_majority_element(vector<int> &a, int left, int right, int &r)
+{
+    /* std::cout << "["<<left<<";"<<right<<"]"<<std::endl; */
+
+    if (left == right) {
+        r = a[left];
+        /* std::cout << "   1 * " << r << std::endl; */
+        return 1;
+    }
+
+    int ret;
+    int n = right - left + 1;
+    int mid = (left + right) / 2;
+
+    ret = get_majority_element(a, left, mid, r);
+    if (ret > 0) {
+        for (size_t i = mid + 1; i <= right; i++) {
+            if (a[i] == r) ret += 1;
+        }
+        if (ret > n / 2) {
+            /* std::cout << "   " << ret << " * " << r << std::endl; */
+            return ret;
+        }
+        /* std::cout << "       nope " << ret << "/"<< n << std::endl; */
+    }
+
+    ret = get_majority_element(a, mid + 1, right, r);
+    if (ret > 0) {
+        for (size_t i = left; i <= mid; i++) {
+            /* std::cout << a[i] <<  " " <<r <<std::endl; */
+            if (a[i] == r) ret += 1;
+        }
+        if (ret > n / 2) {
+            /* std::cout << "   " << ret << " * " << r << std::endl; */
+            return ret;
+        }
+        /* std::cout << "       nope " << ret << "/"<< n << std::endl; */
+    }
+
+    /* std::cout << "       nope" << std::endl; */
+    return 0;
 }
 
 int main() {
@@ -18,5 +55,6 @@ int main() {
   for (size_t i = 0; i < a.size(); ++i) {
     std::cin >> a[i];
   }
-  std::cout << (get_majority_element(a, 0, a.size()) != -1) << '\n';
+  int r;
+  std::cout << (get_majority_element(a, 0, a.size() - 1, r) > 0) << '\n';
 }
diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/03-sorting/sorting.cpp b/01-algorithmic_toolbox/03-divide_and_conquer/03-sorting/sorting.cpp
index 7a60a12..b27af77 100644
--- a/01-algorithmic_toolbox/03-divide_and_conquer/03-sorting/sorting.cpp
+++ b/01-algorithmic_toolbox/03-divide_and_conquer/03-sorting/sorting.cpp
@@ -4,6 +4,27 @@
 using std::vector;
 using std::swap;
 
+/* int partition3(vector<int> &a, int l, int r) */
+/* { */
+/*   int x = a[l]; */
+/*   int i = l + 1; */
+/*   int j = r; */
+/*   int k = r; */
+/*   while (i <= k) { */
+/*       int v = a[j]; */
+/*       if (v < x ) { */
+/*           swap(a[i], a[j]); */
+/*           i++; */
+/*       } else if (v > x) { */
+/*           swap(a[j], a[k]); */
+/*           k--; */
+/*           j--; */
+/*       } */
+/*       else */
+/*           j--; */
+/*   } */
+/* } */
+
 int partition2(vector<int> &a, int l, int r) {
   int x = a[l];
   int j = l;
@@ -22,12 +43,30 @@ void randomized_quick_sort(vector<int> &a, int l, int r) {
     return;
   }
 
-  int k = l + rand() % (r - l + 1);
-  swap(a[l], a[k]);
-  int m = partition2(a, l, r);
+  int p = l + rand() % (r - l + 1);
+  swap(a[l], a[p]);
+  /* int m = partition2(a, l, r); */
+
+  p = a[l];
+  int i = l + 1;
+  int j = r;
+  int k = r;
+  while (i <= j) {
+      int v = a[j];
+      if (v < p ) {
+          swap(a[i], a[j]);
+          i++;
+      } else if (v > p) {
+          swap(a[j], a[k]);
+          k--;
+          j--;
+      }
+      else
+          j--;
+  }
 
-  randomized_quick_sort(a, l, m - 1);
-  randomized_quick_sort(a, m + 1, r);
+  randomized_quick_sort(a, l, i - 1);
+  randomized_quick_sort(a, k + 1, r);
 }
 
 int main() {
@@ -41,4 +80,5 @@ int main() {
   for (size_t i = 0; i < a.size(); ++i) {
     std::cout << a[i] << ' ';
   }
+  std::cout << '\n';
 }
diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/04-inversions/inversions.cpp b/01-algorithmic_toolbox/03-divide_and_conquer/04-inversions/inversions.cpp
index efc7a82..8400a2d 100644
--- a/01-algorithmic_toolbox/03-divide_and_conquer/04-inversions/inversions.cpp
+++ b/01-algorithmic_toolbox/03-divide_and_conquer/04-inversions/inversions.cpp
@@ -2,15 +2,41 @@
 #include <vector>
 
 using std::vector;
+using std::swap;
 
-long long get_number_of_inversions(vector<int> &a, vector<int> &b, size_t left, size_t right) {
-  long long number_of_inversions = 0;
-  if (right <= left + 1) return number_of_inversions;
-  size_t ave = left + (right - left) / 2;
-  number_of_inversions += get_number_of_inversions(a, b, left, ave);
-  number_of_inversions += get_number_of_inversions(a, b, ave, right);
-  //write your code here
-  return number_of_inversions;
+long long get_number_of_inversions(vector<int> &a, vector<int> &b, size_t left, size_t right)
+{
+    long long number_of_inversions = 0;
+    if (right <= left + 1) return number_of_inversions;
+    size_t ave = left + (right - left) / 2;
+    number_of_inversions += get_number_of_inversions(a, b, left, ave);
+    number_of_inversions += get_number_of_inversions(a, b, ave, right);
+
+    size_t i = left, j = ave, k = left;
+
+    while ((i != ave) && (j != right)) {
+        if (a[i] <= a[j]) {
+            b[k] = a[i];
+            i++;
+
+        } else {
+            b[k] = a[j];
+            j++;
+            number_of_inversions += (ave - i);
+        }
+        k++;
+    }
+
+    for( ; i != ave; i++, k++)
+        b[k] = a[i];
+
+    for( ; j != right; j++, k++)
+        b[k] = a[j];
+
+    for(i = left, k = left; i < right; i++, k++)
+        a[i] = b[k];
+
+    return number_of_inversions;
 }
 
 int main() {
diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/05-points_and_segments/points_and_segments.cpp b/01-algorithmic_toolbox/03-divide_and_conquer/05-points_and_segments/points_and_segments.cpp
index 3e9dfaf..1720870 100644
--- a/01-algorithmic_toolbox/03-divide_and_conquer/05-points_and_segments/points_and_segments.cpp
+++ b/01-algorithmic_toolbox/03-divide_and_conquer/05-points_and_segments/points_and_segments.cpp
@@ -2,37 +2,129 @@
 #include <vector>
 
 using std::vector;
+using std::swap;
 
-vector<int> fast_count_segments(vector<int> starts, vector<int> ends, vector<int> points) {
-  vector<int> cnt(points.size());
-  //write your code here
-  return cnt;
+enum T {
+    L = 0, P = 1, R = 2
+};
+
+struct Pair
+{
+    int v;
+    T t;
+    int i;
+};
+
+void randomized_quick_sort(vector<Pair> &pairs, int l, int r)
+{
+  if (l >= r)
+    return;
+
+  int p = l + rand() % (r - l + 1);
+  swap(pairs[l], pairs[p]);
+
+  int v = pairs[l].v;
+  int t = pairs[l].t;
+  int i = l + 1;
+  int j = r;
+  int k = r;
+  while (i <= j) {
+      int w = pairs[j].v;
+      if (w < v ) {
+          swap(pairs[i], pairs[j]);
+          i++;
+      } else if (w > v) {
+          swap(pairs[j], pairs[k]);
+          k--;
+          j--;
+      } else {
+          w = pairs[j].t;
+          if (w < t) {
+              swap(pairs[i], pairs[j]);
+              i++;
+          } else if (w > t) {
+              swap(pairs[j], pairs[k]);
+              k--;
+              j--;
+          } else
+              j--;
+      }
+  }
+
+  randomized_quick_sort(pairs, l, i - 1);
+  randomized_quick_sort(pairs, k + 1, r);
 }
 
-vector<int> naive_count_segments(vector<int> starts, vector<int> ends, vector<int> points) {
-  vector<int> cnt(points.size());
-  for (size_t i = 0; i < points.size(); i++) {
-    for (size_t j = 0; j < starts.size(); j++) {
-      cnt[i] += starts[j] <= points[i] && points[i] <= ends[j];
+/* int binary_search_point(const vector<Pair> &pairs, int x) */
+/* { */
+/*   int left = 0; */
+/*   int right = pairs.size(); */
+/*   int m = 0; */
+
+/*   while (left <= right) { */
+/*       m = (left + right) / 2; */
+/*       Pair p = pairs[m]; */
+/*       if (p.v == x) { */
+/*           if (p.t == T::P) return m; */
+/*           else if (p.t == T::L) left = (m + 1); */
+/*           else right = (m - 1); */
+/*       } */
+/*       else if (p.v < x) left = (m + 1); */
+/*       else right = (m - 1); */
+/*   } */
+/*   return -1; */
+/* } */
+
+vector<int> fast_count_segments(vector<Pair> pairs, vector<int> points)
+{
+    /* for (size_t i = 0; i < pairs.size(); i++) */
+    /*     std::cout << pairs[i].v << ";" << pairs[i].t << " "; */
+    /* std::cout << std::endl; */
+
+    randomized_quick_sort(pairs, 0, pairs.size() - 1);
+
+    /* for (size_t i = 0; i < pairs.size(); i++) */
+    /*     std::cout << pairs[i].v << ";" << pairs[i].t << " "; */
+    /* std::cout << std::endl; */
+
+    vector<int> cnt(points.size());
+    int v = 0;
+    for (size_t i = 0; i < pairs.size(); i++) {
+        Pair p = pairs[i];
+        if (p.t == T::L)
+            v += 1;
+        else if (p.t == T::R)
+            v -= 1;
+        else
+            cnt[p.i] = v;
     }
-  }
-  return cnt;
+    return cnt;
 }
 
 int main() {
   int n, m;
   std::cin >> n >> m;
-  vector<int> starts(n), ends(n);
-  for (size_t i = 0; i < starts.size(); i++) {
-    std::cin >> starts[i] >> ends[i];
+  vector<Pair> pairs(n * 2 + m);
+  size_t i = 0;
+  size_t max = (2 * n);
+  for (; i < max; i++) {
+    std::cin >> pairs[i].v;
+    pairs[i].t = T::L;
+    i++;
+    std::cin >> pairs[i].v;
+    pairs[i].t = T::R;
   }
   vector<int> points(m);
-  for (size_t i = 0; i < points.size(); i++) {
+  for (i = 0; i < m; i++) {
     std::cin >> points[i];
+    int j = i + max;
+    pairs[j].v =  points[i];
+    pairs[j].t = T::P;
+    pairs[j].i = i;
   }
-  //use fast_count_segments
-  vector<int> cnt = naive_count_segments(starts, ends, points);
+  vector<int> cnt = fast_count_segments(pairs, points);
   for (size_t i = 0; i < cnt.size(); i++) {
     std::cout << cnt[i] << ' ';
   }
+  std::cout << '\n';
 }