lab5.cpp

simple class example.

#include <fstream>
#include <iostream>
#include <string>
#include <sys/time.h>
#include <stdio.h>
#include <vector>
#include "asort.h"

using namespace std;

class Student {
  public:

    Student(): id(-1), grade(-1) {}
    Student(int i, int g) : id(i), grade(g) {}
    Student(const Student& s) {
      id=s.getid();
      grade=s.getgrade();
    }
    ~Student() {}

    Student& operator = (const Student& s) {
      id=s.getid();
      grade=s.getgrade();
      return (*this);
    }
    bool operator < (const Student& s) const {
    // return true if this student is smaller than Student s
      if (grade==s.getgrade()) return (id<s.getid());
      else return (grade<s.getgrade());
    }
    bool operator == (const Student& s) const {
    // return true if grades are same.
      return (grade==s.getgrade());
    }
    bool operator <= (const Student& s) const {
    // no equal
      return ((*this)<s);
    }

    int getid() const { return id; }
    int getgrade() const { return grade; }

  private:

    int id, grade;
};

ostream& operator<<(ostream& o, const Student& s) {
  o<<"("<<s.getid()<<","<<s.getgrade()<<")";
  return o;
}

void shellsort(vector<Student>& d) {
  int g, i, j;
  int ds=d.size();
  for (g=ds/2; g>0; g/=2) {
    for (i=g; i<ds; i++) {
      Student tmp=d[i];
      for (j=i; j>=g && tmp<d[j-g]; j-=g) d[j]=d[j-g];
      d[j]=tmp;
    }
  }
}


int main(int argc, char** argv) {
  // application here
  if (argc!=2) { // make sure the program has the right argument.
    cout<<"./myprogram lab2.txt"<<endl;
    return 1;
  }
  ifstream data;
  data.open(argv[1]);
  if (!data.is_open()) { // make sure the file is ready
    cout<<"cannot open the file "<<argv[1]<<endl;
    return 1;
  };

  // read data
  vector<Student> s(100000);
  string h;
  data>>h; // read off the first line
  data>>h; // read off the first line
  int i,j,k;
  int id, grade;
  for (i=0;!data.eof();i++ ) { // read the data of the first three students
    data>>id;
    data>>grade;
    if (!data.fail()) s[i]=Student(id,grade);
  }
  cout<<"Total "<<s.size()<<" students"<<endl<<endl;
  data.close();
  
  // prepare data for sorting
  // d[0] are sets of data of 100000 students
  // d[1] are sets of data of  50000 students
  // d[2] are sets of data of  33333 students
  vector<Student> d[3];
  for (i=0;i<3;i++) {
    int ds=((int)s.size()-1)/(2*i+2)*2+1;
    if (ds/2!=(ds-1)/2) { cout<<"not odd"<<endl; exit(1); }
    d[i].resize(ds);
    for (k=0;k<ds;k++) d[i][k]=s[k];
  }

  // heapsort
  cout<<"heapsort"<<endl;
  Heap<Student> sh[3];
  for (i=0;i<3;i++) {
    sh[i].buildHeap(d[i]);
    sh[i].outputbeforesort();
    sh[i].heapsort();
    sh[i].outputaftersort();
    cout<<endl;
  }

  // mergesort
  cout<<"mergesort"<<endl;
  vector<Student> md[3];
  for (i=0;i<3;i++) {
    md[i]=d[i];
    mergesort(md[i]);
    cout<<md[i].size()<<",";
    for (j=-1;j<2;j++) cout<<md[i][j+md[i].size()/2];
    cout<<endl;
  }
  cout<<endl;

  // quicksort
  cout<<"quicksort"<<endl;
  vector<Student> qd[3];
  for (i=0;i<3;i++) {
    qd[i]=d[i];
    quicksort(qd[i]);
    cout<<qd[i].size()<<",";
    for (j=-1;j<2;j++) cout<<qd[i][2*j+qd[i].size()/2];
    cout<<endl;
  }
  cout<<endl;
  
  // shellsort
  cout<<"shellsort"<<endl;
  vector<Student> sd[3];
  for (i=0;i<3;i++) {
    sd[i]=d[i];
    shellsort(sd[i]);
    cout<<sd[i].size()<<",";
    for (j=-1;j<2;j++) cout<<sd[i][3*j+sd[i].size()/2];
    cout<<endl;
  }
  cout<<endl;
  return 0;
}