Psl67/recursion templates

findmax

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<int> x;

void read_input()
{
  cin >> n;
  for(int i = 0; i < n; i++) {
    int xx;
    cin >> xx;
    x.push_back(xx);
  }
}

int find_max(vector<int>& x, int n)
{
  // TODO: write this function, do not use any loop control
}

int main()
{
  read_input();
  cout << find_max(x,n) << endl;
}

selection sort

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<int> x;

void read_input()
{
  cin >> n;
  for(int i = 0; i < n; i++) {
    int xx;
    cin >> xx;
    x.push_back(xx);
  }
}

int find_max_index(vector<int>& x, int n)
{
  // TODO: return the index of the maximum element in x[0], x[1],... x[n-1]
  //       don't use any loop control structures
}

void swap(int& x, int& y)
{
  int t = x;
  x = y;
  y = t;
}

void selection_sort(vector<int>& x, int n)
{
  // TODO: don't use any loop control structures
}

int main()
{
  read_input();
  selection_sort(x, n);
  for(int i=0; i<n; i++) {
    cout << x[i] << endl;
  }
}

Merge sort

#include <iostream>
#include <vector>

using namespace std;

const int MAX_N = 100010;

int n;
int buffer[MAX_N];
int a[MAX_N];

void read_input()
{
  cin >> n;
  for(int i = 0; i < n; i++) {
    cin >> a[i];
  }
}

void merge(int arr[],
	   int xl, int xr,
	   int yl, int yr,
	   int buffer[])
{
  if((xl > xr) && (yl > yr)) {
    return;
  }
  // TODO: compare arr[xl] and arr[yl] and put in buffer[0], 
  //       then recursively merge the rest of the array (passing buffer+1 to move the buffer)
  //       make sure to deal with the cases that xl > xr and yl > yr 
}

void copyarray(int src[], int desc[], int n)
{
  // NOTES: you may see this as an example to implement merge
  if(n==0)
    return;
  desc[0] = src[0];
  copyarray(src + 1, desc + 1, n - 1);
}

void mergesort(int arr[], int l, int r)
{
  if(l >= r)
    return;

  int mid = (l + r) / 2;
  mergesort(arr, l, mid);
  mergesort(arr, mid + 1, r);

  merge(arr, l, mid, mid + 1, r, buffer);
  copyarray(buffer, &arr[l], r - l + 1);
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);

  read_input();

  mergesort(a,0,n-1);

  for(int i = 0; i < n; i++) {
    cout << a[i] << "\n";
  }
}