Spring 2020

PIC 10B: Intermediate Programming

Discussion Section 2A

Wonjun Lee

Week8

Tuesday

Problems related to sort algorithms
Link to the video

Enter password:

Exercise P11.2
Solution
#include < iostream >
#include < vector >
#include < string >

using namespace std;

class Employee
{
public:
  Employee(string name, double salary): name(name), salary(salary) {}
  string get_name() const{
    return name;
  }
  double get_salary() const{
    return salary;
  }
private:
  string name;
  double salary;
};

ostream& operator<<(ostream& out, const Employee& value){
  out << "[ Name : " << value.get_name() << " Salary : " << value.get_salary() << "]";
  return out;
}

bool operator<(const Employee& left, const Employee& right){
  if(left.get_salary() < right.get_salary()){
    return true;
  }
  return false;
}

void swap(vector< Employee* >& v, int i, int j){
  Employee* tmp = v[i];
  v[i] = v[j];
  v[j] = tmp;
}

void sort(vector< Employee* >& v){

  int N = v.size();
  Employee* p = nullptr;

  for(int i=0;i < N;++i){
    p = v[i];
    int ind = i;
    for(int j=i+1;j < N;++j){
      if(*(v[j]) < *p){
        p   = v[j];
        ind = j;
      }
    }
    swap(v,i,ind);
  }
}

int main()
{
  vector< Employee* > v;
  v.push_back(new Employee("John",1000));
  v.push_back(new Employee("Ringo",2000));
  v.push_back(new Employee("Paul",500));
  v.push_back(new Employee("George",800));

  for(int i=0;i < v.size();++i){
    cout << *(v[i]) << " ";
  }
  cout << endl;

  sort(v);

  cout << "After sort" << endl;

  for(int i=0;i < v.size();++i){
    cout << *(v[i]) << " ";
  }
  cout << endl;
}
Exercise P11.4
Solution
#include < iostream >
#include < vector >
#include < string >

using namespace std;

class Employee
{
public:
  Employee(string name, double salary): name(name), salary(salary) {}
  string get_name() const{
    return name;
  }
  double get_salary() const{
    return salary;
  }
private:
  string name;
  double salary;
};

ostream& operator<<(ostream& out, const Employee& value){
  out << "[ Name : " << value.get_name() << " Salary : " << value.get_salary() << "]";
  return out;
}

bool operator<(const Employee& left, const Employee& right){
  if(left.get_salary() < right.get_salary()){
    return true;
  }
  return false;
}

void merge(vector< Employee* >& v, int from, int mid, int to){

  vector< Employee* > new_v;
  int c1=from;
  int c2=mid+1;

  while(c1 <= mid && c2 <= to){
    if(*v[c1] < *v[c2]){
      new_v.push_back(v[c1]);
      c1++;
    }else{
      new_v.push_back(v[c2]);
      c2++;
    }
  }
  if(c1 <= mid){
    for(int i=c1; i<=mid;++i){
      new_v.push_back(v[i]);
    }
  }else{
    for(int i=c2; i<=to;++i){
      new_v.push_back(v[i]);
    } 
  }
  v = new_v;
}

void sort(vector< Employee* >& v, int from, int to){

  if(from == to) return;

  int mid  = (from+to)/2;

  sort(v,from,mid);
  sort(v,mid+1,to);

  merge(v,from,mid,to);
}

int main()
{
  vector< Employee* > v;
  v.push_back(new Employee("John",1000));
  v.push_back(new Employee("Ringo",2000));
  v.push_back(new Employee("Paul",500));
  v.push_back(new Employee("George",800));
  for(int i=0;i < v.size();++i){
    cout << *(v[i]) << " ";
  }
  cout << endl;

  // sort(v,0,v.size()-1);

  sort(v.begin(), v.end(), myfun);

  cout << "After sort" << endl;

  for(int i=0;i < v.size();++i){
    cout << *(v[i]) << " ";
  }
  cout << endl;
}
Exercise P11.10
Solution
#include < iostream >
#include < vector >
#include < string >
#include < algorithm > // IMPORTANT

using namespace std;

class Employee
{
public:
  Employee(string name, double salary): name(name), salary(salary) {}
  string get_name() const{
    return name;
  }
  double get_salary() const{
    return salary;
  }
private:
  string name;
  double salary;
};

ostream& operator<<(ostream& out, const Employee& value){
  out << "[ Name : " << value.get_name() << " Salary : " << value.get_salary() << "]";
  return out;
}

bool operator<(const Employee& left, const Employee& right){
  if(left.get_salary() < right.get_salary()){
    return true;
  }
  return false;
}

bool myfun(Employee* left, Employee* right){
  if(left->get_salary() < right->get_salary()){
    return true;
  }
  return false;
}

int main()
{
  vector< Employee* > v;
  v.push_back(new Employee("John",1000));
  v.push_back(new Employee("Ringo",2000));
  v.push_back(new Employee("Paul",500));
  v.push_back(new Employee("George",800));

  for(int i=0;i < v.size();++i){
    cout << *(v[i]) << " ";
  }
  cout << endl;

  sort(v.begin(),v.end(),myfun);

  cout << "After sort" << endl;

  for(int i=0;i < v.size();++i){
    cout << *(v[i]) << " ";
  }
  cout << endl;
}

Thursday

About HW5 and Linked List
Link to the video

Enter password: