// Algorithm for determining the position of a value x in a given array
// or the position of inserting the value x in the array such that the sorting order is maintained
Input:
array a[1],a[2], .. a[n], n>=1, with distinct natural numbers
integer x, natural number
Output:
integer pos, natural number
Pseudocode:
Sub position()
pos = -1
left = 1
right = n // length of the input array
While left <= right
middle = left + (right-left)/2
If a[middle] == x // found exact match
pos = middle
Return pos
Else If a[middle] < x // search in left half
right = middle - 1
Else If a[middle] > x
left = middle + 1 // search in right half
pos = middle // update position to middle, as x should come after middle
End If
End While
If pos == -1
pos = left // no larger element found, x should be inserted at the beginning
Return pos
Else
pos = pos + 1 //
Return pos
End If
End Sub
Complexity:
O(log(n))
// Algorithm for determining the circular permutation
// of a given array k positions to the right
Input:
array x[1], x[2], ..., x[n], n>=1, with characters
integer k, 0 < k <=n
Output:
array y[1], y[2], ..., y[n], with characters
Pseudocode:
Sub k_permutation():
n = length of aray x
y = new array of size n
If p == 0
y = x
return y
For i = 0 to n-1
new_index = (i + k) % n
y[new_index] = x[i]
EndFor
Return y
End Sub
Complexity: O(n)
// Algorithm for determining if an array can represent
// an inorder traversal of binary search tree
// or the list of swaps to produce an array that satisfies the condition
Input:
array a[1], a[2], ..., a[n], n>0, with permutations of {1,...,n}
Output:
value 0 if array can represent inorder traversal of binary search tree
or list of swaps y to produce an array that satisfies the condition
Pseudocode:
Sub verify_bst_representation():
n = length of aray a
y = new array to hold list of possible interchanges
j = 0
visited = map to store the already swapped elements
For i = 1 to n
If a[i] != i and i not in visited
y[j] = (i, a[i])
tmp = a[i]
a[i] = a[a[i]]
a[a[i]] = tmp
visited[i] = true
j = j + 1
EndIf
EndFor
If y is not empty
Return y
Else
Return 0 // reaching this means the permutation represents a binary search tree
End Sub
Complexity: O(n)
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
class Product {
private:
string name;
int baseprice;
public:
Product(const string& name, int baseprice):
name{name},
baseprice{baseprice} {}
virtual int total_price() {
return this->baseprice;
}
virtual string toString() {
return this->name;
}
virtual ~Product() {}
};
class Computer: public Product {
private:
int tax;
public:
Computer(const string& name, int baseprice, int tax)
: Product(name, baseprice) {
this->tax = tax;
}
int total_price() {
return Product::total_price() + tax;
}
string toString() {
return Product::toString() + ", " + to_string(this->total_price());
}
};
class SorterByTotalPrice {
**public:**
**static** bool compareByTotalPrice(Product* a, Product* b){
return a->total_price() **>** b->total_price();
}
**static** void sort(vector<Product*>& computers){
std::sort(computers.begin(), computers.end(), compareByTotalPrice);
}
};
int main() {
vector<Product*> computers{
new Computer("HC90", 140, 10),
new Computer("HC91", 100, 12),
new Computer("HC85", 150, 15)
};
**SorterByTotalPrice::sort(computers);**
cout << computers[0]->toString();
for(auto c : computers)
delete c;
return 0;
}
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
class Contact {
private:
string name;
public:
Contact(string name) {
this->name = name;
}
virtual void sendMessage(const string& message) const = 0;
virtual string getName() const {
return name;
}
virtual ~Contact() {}
};
class Person : public Contact {
private:
string number;
public:
Person(string name, string number)
: Contact(name) {
this->number = number;
}
string getNumber() const {
return number;
}
void sendMessage(const string& message) const {
cout << getName() << " " << number << " " << endl << message << endl;
}
};
class Group : public Contact {
private:
vector<Contact*> contacts;
public:
Group(string name)
: Contact(name) {}
void addContact(Contact* contact) {
contacts.push_back(contact);
}
void sendMessage(const string& message) const {
for(const Contact* contact : contacts){
const Person* person = dynamic_cast<const Person*>(contact); //static_cast
cout << person->getName() << " " << person->Person::getNumber() << endl;
}
cout << message << endl;
}
~Group() {
for (Contact* contact : contacts){
delete contact;
}
}
};
int main() {
Person* p1 = new Person("Mother", "01");
Person* p2 = new Person("Father", "02");
Person* p3 = new Person("Jane", "03");
Person* p4 = new Person("John", "04");
Group* parents = new Group("Parents");
parents->addContact(p1);
parents->addContact(p2);
Group* family = new Group("Family");
family->addContact(p1);
family->addContact(p2);
family->addContact(p3);
family->sendMessage("You are invited");
p4->sendMessage("You are invited");
delete family;
delete p4;
return 0;
}
To understand the behavior of the subalgorithms g and transformare, we need to analyze the code.
Subalgorithm g(x, n, y, i)
This subalgorithm takes as input arrays x and y, integers n and i. Here's what it does:
If i≤n, it assigns y[i]←x[i]
i≤ni \leq n
y[i]←x[i]y[i] \leftarrow x[i]
It then recursively calls itself with i+1.
i+1i + 1
So, it essentially copies elements from x to y until it reaches the end of x.
Subalgorithm transformare(x, n, y, m, z, k)
This subalgorithm calls g and modifies k. Here's what it does:
If n=0, it calls g(y, m, z, 1) and sets k←m.
n=0n = 0
k←mk \leftarrow m
Else, it copies x[n] to y[m+1], then recursively calls itself with n−1 and m+1.
x[n]x[n]
y[m+1]y[m + 1]
n−1n - 1
m+1m + 1
To find out what the array z contains, let's trace the call:
Initial Call: transformare(x, n, y, 0, z, k)
n is the length of x.
m starts at 0.
On each call, the elements of x are copied to y in reverse order.
Finally, when n becomes 0, it copies y to z using g.
Therefore, z will contain elements of x in reverse order.
**#include <iostream>
#include <vector>
#include <unordered_map>**
using namespace std;
int main() {
**int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; ++i) {
cin >> a[i];
}**
**unordered_map<int, pair<int, int>> sumPairs;**
for(int i = 0; i < n; ++i) {
for(int j = i + 1; j < n; ++j) {
int sum = a[i] + a[j];
if(**sumPairs.find(-sum)** != **sumPairs.end()**) {
**auto p = sumPairs[-sum];**
**int x = p.first;
int y = p.second;**
if(**x != i && x != j && y != i && y != j**) {
vector<int> indices = {x + 1, y + 1, i + 1, j + 1};
sort(indices.begin(), indices.end());
cout << indices[0] << " " << indices[1] << " " << indices[2] << " " << indices[3] << endl;
return 0;
}
}
**sumPairs[sum] = {i, j};**
}
}
cout << -1 << endl;
return 0;
}
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class MyObject {
public:
**virtual void print() const = 0;**
**virtual ~MyObject() {}**
};
class MyInteger : public MyObject {
int value;
public:
MyInteger(int v) **: value(v)** {}
**void print() const override {**
cout << value;
}
};
class MyString : public MyObject {
string value;
public:
**MyString(const string&** v) **: value(v)** {}
**void print() const override {**
cout << value;
}
};
**class MyObjectList** {
**vector<MyObject*> objects;**
public:
**~MyObjectList() {
for(auto obj : objects) {
delete obj;
}
}**
**MyObjectList& add(MyObject* obj) {
objects.push_back(obj);
return *this;
}**
};
**class MyListIterator {
vector<MyObject*>& objects;
size_t index;**
public:
**MyListIterator(vector<MyObject*>& objs) : objects(objs), index(0) {}**
bool isValid() const {
**return index < objects.size();**
}
**MyObject* element() const {
return objects[index];
}**
**void next() {
++index;
}**
};
int main() {
MyObjectList list;
list.add(new MyInteger(2)).add(new MyString("Hi"));
MyString* s = new MyString("Bye");
list.add(s);
list.add(new MyString("5"));
MyListIterator i {list};
while (i.isValid()) {
MyObject* o = i.element();
o->print();
cout << " ";
i.next();
}
// prints: 2 Hi Bye 5
return 0;
}
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Person {
string surname;
string firstname;
int age;
public:
Person(string s, string f, int a) : surname(s), firstname(f), age(a) {}
string getSurname() const { return surname; }
string getFirstname() const { return firstname; }
int getAge() const { return age; }
bool operator<(const Person& other) const {
return surname < other.surname;
}
};
void merge(vector<Person*>& persons, int left, int mid, int right, bool (*compare)(const Person*, const Person*)) {
int n1 = mid - left + 1;
int n2 = right - mid;
vector<Person*> L(n1);
vector<Person*> R(n2);
for (int i = 0; i < n1; ++i)
L[i] = persons[left + i];
for (int j = 0; j < n2; ++j)
R[j] = persons[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (compare(L[i], R[j])) {
persons[k] = L[i];
++i;
} else {
persons[k] = R[j];
++j;
}
++k;
}
while (i < n1) {
persons[k] = L[i];
++i;
++k;
}
while (j < n2) {
persons[k] = R[j];
++j;
++k;
}
}
void mergeSort(vector<Person*>& persons, int left, int right, bool (*compare)(const Person*, const Person*)) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(persons, left, mid, compare);
mergeSort(persons, mid + 1, right, compare);
merge(persons, left, mid, right, compare);
}
}
bool compareBySurname(const Person* a, const Person* b) {
return a->getSurname() < b->getSurname();
}
bool compareByAge(const Person* a, const Person* b) {
return a->getAge() < b->getAge();
}
bool compareByAgeAndName(const Person* a, const Person* b) {
if (a->getAge() == b->getAge()) {
return a->getSurname() < b->getSurname();
}
return a->getAge() < b->getAge();
}
int main() {
vector<Person*> persons = {
new Person("Doe", "John", 30),
new Person("Smith", "Jane", 25),
new Person("Doe", "Alice", 30),
new Person("Brown", "Charlie", 20)
};
cout << "Sorted by surname:\\n";
mergeSort(persons, 0, persons.size() - 1, compareBySurname);
for (const auto& person : persons) {
cout << person->getSurname() << " " << person->getFirstname() << " " << person->getAge() << endl;
}
cout << "\\nSorted by age:\\n";
mergeSort(persons, 0, persons.size() - 1, compareByAge);
for (const auto& person : persons) {
cout << person->getSurname() << " " << person->getFirstname() << " " << person->getAge() << endl;
}
cout << "\\nSorted by age and name:\\n";
mergeSort(persons, 0, persons.size() - 1, compareByAgeAndName);
for (const auto& person : persons) {
cout << person->getSurname() << " " << person->getFirstname() << " " << person->getAge() << endl;
}
// Clean up allocated memory
for (auto person : persons) {
delete person;
}
return 0;
}