1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91
|
#include <iostream>
#include <iomanip>
#include <string>
using namespace std;
int mergesort(int n, string *id, string *name, string *gender, int *score);
int main()
{
const int NSIZE = 5;
string id[NSIZE] = {
"2012019109", "2009675341", "2009277197", "2012205829", "2006366045"
};
string name[NSIZE] = {
"Proadan Legeaf Coaa", "Payloth Legeragord Nydiragan",
"Grardosh Astaym", "Kigon Habwyn Weramas", "Wudric Legauseth"
};
string gender[NSIZE] = {
"Female", "Female", "Male", "Female", "Male"
};
int score[NSIZE] = {65, 82, 93, 52, 75};
if (mergesort(NSIZE, id, name, gender, score))
{
for (int i=0; i<NSIZE; ++i)
cout << left << setw(12) << id[i]
<< setw(30) << name[i]
<< setw(8) << gender[i]
<< score[i] << endl;
} else cout << "Out of memory\n";
}
//---------------------------------
void mergehelper(string *id, string *name, string *gender, int *score,
int beg, int end,
string *nid, string *nname, string *ngender, int *nscore)
{
if(end == beg+1) return;
int mid = (beg+end)/2;
int i0 = beg;
int i1 = mid;
mergehelper(id, name, gender, score,
beg, mid,
nid, nname, ngender, nscore);
mergehelper(id, name, gender, score,
mid, end,
nid, nname, ngender, nscore);
for (int i = 0; i < end - beg; i++)
{
bool smallLeft = (i0 < mid && (i1 >= end || name[i0] < name[i1]));
int j = (smallLeft ? i0 : i1)++;
nid[i] = id[j];
nname[i] = name[j];
ngender[i] = gender[j];
nscore[i] = score[j];
}
for(int i = beg; i < end; i++)
{
int j = i - beg;
id[i] = nid[j];
name[i] = nname[j];
gender[i] = ngender[j];
score[i] = nscore[j];
}
}
//---------------------------------
int mergesort(int n, string *id, string *name, string *gender, int *score)
{
string *nid = new string[n];
if(!nid) return 0;
string *nname = new string[n];
if(!nname) return 0;
string *ngender = new string[n];
if(!ngender) return 0;
int *nscore = new int[n];
if(!nscore) return 0;
mergehelper(id, name, gender, score,
0, n,
nid, nname, ngender, nscore);
delete [] nid;
delete [] nname;
delete [] ngender;
delete [] nscore;
return 1;
}
|