CS14 SI Lab 3 solutions

ex1.cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool binary_search_rec(const vector<int>& v, unsigned start, unsigned end, int target) {
  int middle = (start + end) / 2;
  if (start == end) {
    return false;
  }

  if (target == v.at(middle)) {
    return true;
  } else if (target < v.at(middle)) {
    return binary_search_rec(v, 0, middle, target);
  } else {
    return binary_search_rec(v, middle + 1, end, target);
  }
}

bool binary_search(vector<int>& v, int target) {
  /* Maybe make sure the vector is sorted beforehand */
  sort(v.begin(), v.end());

  return binary_search_rec(v, 0, v.size() - 1, target);
}


int main() {}

ex2.cpp

#include <iostream>
#include <vector>

using namespace std;

void merge(vector<int>& v, unsigned start, unsigned mid, unsigned end) {
  unsigned i = start, j = mid + 1;
  vector<int> merged;
  while (i <= mid && j <= end) {
    
    if (v.at(i) < v.at(j)) {
      merged.push_back(v.at(i++));
    } else {
      merged.push_back(v.at(j++));
    }
  }

  while (i <= mid) {
    merged.push_back(v.at(i++));
  }

  while (j <= end) {
    merged.push_back(v.at(j++));
  }

  for (i = 0, j = start; i < merged.size(); ++i) {
    v.at(j) = merged.at(i);
  }
}

void mergesort_rec(vector<int>& v, unsigned start, unsigned end) {
  if (start < end) {
    unsigned mid = (start + end) / 2;
    mergesort_rec(v, start, mid);
    mergesort_rec(v, mid + 1, end);
    merge(v, start, mid, end);
  }
}

void mergesort(vector<int>& v) {
  mergesort_rec(v, 0, v.size() - 1);
}

int main() {
}

ex3.cpp

#include <iostream>
#include <vector>
#include <cmath>
#include <cstdlib>

using namespace std;

void quicksort_rec(vector<int>& v) {
  if (v.size() <= 1) {
    return;
  }

  // Choose the middle I guess
  int pivot = (v.size() - 1) / 2;
  int pivot_ele = v.at(pivot);

  // Let's just remove it to make our lives easier
  swap(pivot_ele, v.at(v.size() - 1));
  v.pop_back();

  vector<int> left, right;

  for (vector<int>::iterator i = v.begin(); i != v.end(); ++i) {
    if (*i < pivot_ele) {
      left.push_back(*i);
    } else {
      right.push_back(*i);
    }
  }

  // Sort both sides
  quicksort_rec(left);
  quicksort_rec(right);

  // Merge them into original vector.
  v.clear();
  v = left;
  v.push_back(pivot_ele);
  for (unsigned i = 0; i < right.size(); ++i) {
    v.push_back(right.at(i));
  }
}

int main() {
  srand(time(NULL));

  vector<int> random_data;
  for (unsigned i = 0; i < 10; ++i) {
    random_data.push_back(rand());
  }

  quicksort_rec(random_data);

  for (unsigned i = 0; i < random_data.size(); ++i) {
    cout << random_data.at(i) << " ";
  }
  cout << endl;

  return 0;
}