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
|
// Ovning_3_3.cpp : Defines the entry point for the console application.
//
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
class Family
{
public:
Family() : name(""), age(0) {}
Family(const string &_name, int _age) : name(_name), age(_age) {}
Family(const Family &rhs) : name(rhs.name), age(rhs.age) {}
Family operator=(const Family &rhs)
{
if (&rhs == this)
{
return *this;
}
name = rhs.name;
age = rhs.age;
return *this;
}
//Metod: Sets the necessary info
void SetInfo(const string &_name, int _age)
{
name = _name;
age = _age;
}
const string &Name() const { return name; }
int Age() const { return age; }
private:
string name;
int age;
};
//Function Declarations
void BubbleSort(vector<Family> &myList);
void swap(Family &p, Family &q);
//bool BinarySearch(vector<Family> &myList, int);
bool BinarySearch(std::vector<Family> &myList, const int& key, const int& start, const int& end);
int main()
{
int choice;
//Create a list with persons and fill it:
vector<Family>myFamily;
myFamily.push_back(Family("Tuva", 17));
myFamily.push_back(Family("Rickard", 21));
myFamily.push_back(Family("Daniella", 35));
myFamily.push_back(Family("Michelle", 42));
BubbleSort(myFamily);
cout << "Sort order by age, youngest first:" << endl;
for (int i = 0; i < myFamily.size(); ++i)
{
cout << myFamily[i].Name() << " " << myFamily[i].Age() << endl;
}
// using default comparison:
/* std::sort (myFamily.begin(), myFamily.end());
std::cout << "looking for a 21... ";
if (std::binary_search (myFamily.begin(), myFamily.end(), 21))
std::cout << "found!\n"; else std::cout << "not found.\n";
// using myfunction as comp:
std::sort (myFamily.begin(), myFamily.end(), BinarySearch);
std::cout << "looking for a 35... ";
if (std::binary_search (myFamily.begin(), myFamily.end(), 35, BinarySearch))
std::cout << "found!\n"; else std::cout << "not found.\n"; */
int key = 21;
std::cout << key;
( BinarySearch(myFamily, key, 0, myFamily.size()-1) ) ? std::cout << " " : std::cout << " not ";
std::cout << "found" << std::endl;
return 0;
}
//Function Definitions
void BubbleSort(vector<Family> &myFamily)
{
// The outer loop, going through all list
for(int i = 0; i < myFamily.size(); i++)
{
//Inner loop, going through element by element
int nrLeft = myFamily.size() - i; // To se how many has been gone through
for (int j = 0; j < nrLeft - 1; j++)
{
if (myFamily[j].Age() > myFamily[j+1].Age()) // Compare the elements
{
swap(myFamily[j], myFamily[j+1]);
}
}
}
}
void swap(Family &p, Family &q)
{
Family temp = p;
p = q;
q = temp;
}
/* bool BinarySearch(vector<Family>&myFamily, int key)
{
for(int i = 0; i < myFamily.size(); i++)
return (myFamily[i].Age() < key);
}
*/
/**
* Binary search. 1st call with start=0 and end N-1
* @param v The vector to be searched.
* @param key The element we are searching for.
* @param start The start of the set we currently looking into.
* @param end The end of the set we currently looking into.
* @return true for found, false for not found.
*/
bool BinarySearch(vector<Family> &myFamily, const int& key, const int& start, const int& end)
{
if(end < start)
// Set is empty, return false
return false;
else
{
// Calculate midpoint to cut set in half
int mid = (start + end)/2;
if(myFamily[mid].Age() > key)
// Key is in lower subset
return BinarySearch(myFamily, key, start, mid-1);
else if (myFamily[mid].Age() < key)
// Key is in upper subset
return BinarySearch(myFamily, key, mid+1, end);
else
// Key has been found
return true;
}
}
|
