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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
|
#include <iostream>
#include <cmath>
#include <cstdlib> // for exit(1).
using namespace std;
class rational {
friend ostream& operator<<(ostream &, rational &);
friend istream& operator>>(istream &, rational &);
public:
rational();
rational(int, int);
rational operator+(const rational &) const;
rational operator-(const rational &) const;
// post-condition: result of (calling object - explicitly passed object) is returned
void operator*=(const rational &);
bool operator<(const rational &);
// post-condition: if calling obj is smaller, returns true; returns false otherwise; num and denom can be positive or negative
private:
int GCD();
int num;
int denom;
};
rational::rational()
{
num = 0; denom = 1;
}
rational::rational(int n, int d)
{
if (d == 0)
{
cout << "Denominator cannot be zero, program is terminated." << endl;
exit(1);
}
num = n;
denom = d;
}
rational rational::operator+(const rational &obj2) const
{
rational sum; // rational type! stores sum of two rational numbers or objects
sum.num = (*this).num * obj2.denom + obj2.num * (*this).denom;
sum.denom = (*this).denom * obj2.denom;
return sum;
}
rational rational::operator-(const rational &obj) const
{
rational diff; // rational type! stores "difference" of two rational numbers or objects
diff.num = (*this).num * obj.denom - obj.num * (*this).denom;
diff.denom = (*this).denom * obj.denom;
return diff;
}
void rational::operator*=(const rational &obj)
{
rational temp; // for clarity; the below code can be simpler
temp.num = num * obj.num;
temp.denom = denom * obj.denom;
*this = temp;
}
int rational::GCD()
{
int n1 = abs(num), n2 = abs(denom), remainder;
remainder = n1 % n2;
while(remainder != 0)
{
n1 = n2;
n2 = remainder;
remainder = n1 % n2;
}
return n2;
}
bool rational::operator<(const rational &obj)
{
rational diff = *this - obj; // makes use of the overloaded "-" operator
if (static_cast<double>(diff.num) / static_cast<double>(diff.denom) < 0)
return true;
else
return false;
}
ostream& operator<<(ostream &out, rational &obj) // return an ostream object by reference allows calls to be cascaded
{ // notice that parameter obj cannot be const because it values will be changed
int gcd = obj.GCD();
obj.num /= gcd;
obj.denom /= gcd;
out << obj.num << "/" << obj.denom;
return out;
}
istream& operator>>(istream &in, rational &obj)
{
in >> obj.num >> obj.denom;
return in;
}
void quickSort(rational r[], int left,int right);
// pre-condition: unsorted array and # of elements in the array are passed to the function
// post-condition: array is sorted in ascending order
void quickSort(int arr[], int left, int right) {
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];
/* partition */
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
};
/* recursion */
if (left < j)
quickSort(arr, left, j);
if (i < right)
quickSort(arr, i, right);
}
int getInput(rational [], int);
int getInput(rational r[], int n)
{
int i = 0;
char ans;
cout << "Each rational number consists of two integers: an numerator and a denominator." << endl;
cout << "You may enter up to " << n << " rational numbers:" << endl;
do {
cout << "Enter a rational number: ";
cin >> r[i++];
cout << "More rational numbers to enter? (Y/N): ";
cin >> ans;
} while (ans == 'Y' || ans == 'y');
return i;
}
int main()
{
const int SIZE = 10;
rational r[SIZE];
int n;
n = getInput(r, SIZE);
cout << "\nYou have entered " << n << " ratrional numbers." << endl;
cout << "\n\nBefore sorting, the list of rationals are: " << endl;
for (int i = 0; i < n; i++)
cout << r[i] << " ";
quickSort(r, n);
cout << "\n\nAfter sorting, the list of rationals are: " << endl;
for (int i = 0; i < n; i++)
cout << r[i] << " ";
cout << endl;
system("pause");
return 0;
}
|
