According to the condition of the task, it is required to sort an array of structures. The data should be sorted as follows: when comparing two participants, the one with more tasks solved will go higher. If the number of solved tasks is equal, the participant with the lesser penalty goes first. If the penalties also match, then the first one will be the one whose login goes earlier in lexicographic order. The sorting must be done using the Hoare method. The algorithm works if I only compare numbers, but when using a comparator for some data, the error "Segmentation fault (core dumped)" appears. I can't figure out what I'm doing wrong? My code is shown below:
// https://ru.wikipedia.org/wiki/Быстрая_сортировка
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
struct Participants {
std::string login;
int complited_tasks;
int fine;
Participants(std::string l, int c, int f) {
login = l;
complited_tasks = c;
fine = f;
}
};
void print_arr(std::vector<Participants> a);
void quick_sort(std::vector<Participants>& arr, int indx_left, int indx_right);
int partition(std::vector<int>& arr, int indx_left, int indx_right);
void get_participants(std::vector<Participants>& p);
bool is_better(Participants p1, Participants p2);
void get_test_data(std::vector<Participants>& p);
int main() {
std::vector<Participants> p;
// get_participants(p);
get_test_data(p);
quick_sort(p, 0, p.size() - 1);
print_arr(p);
return 0;
}
//creates a vector of data on which an error appears
void get_test_data(std::vector<Participants>& p) {
p.push_back(Participants("tufhdbi", 76, 58));
p.push_back(Participants("rqyoazgbmv", 59, 78));
p.push_back(Participants("qvgtrlkmyrm", 35, 27));
p.push_back(Participants("tgcytmfpj", 70, 27));
p.push_back(Participants("xvf", 84, 19));
p.push_back(Participants("jzpnpgpcqbsmczrgvsu", 30, 3));
p.push_back(Participants("evjphqnevjqakze", 92, 15));
p.push_back(Participants("wwzwv", 87, 8));
p.push_back(Participants("tfpiqpwmkkduhcupp", 1, 82));
p.push_back(Participants("tzamkyqadmybky", 5, 81));
p.push_back(Participants("amotrxgba", 0, 6));
p.push_back(Participants("easfsifbzkfezn", 100, 28));
p.push_back(Participants("kivdiy", 70, 47));
}
// data reading function
void get_participants(std::vector<Participants>& p) {
std::string inp;
std::getline(std::cin, inp);
int n = std::stoi(inp);
for (int i = 0; i < n; i++) {
std::vector<std::string> split_inp;
std::string t;
std::getline(std::cin, inp);
for (unsigned int j = 0; j < inp.size(); j++) {
if (inp[j] == ' ') {
split_inp.push_back(t);
t.clear();
continue;
}
t += inp[j];
}
split_inp.push_back(t);
p.push_back(Participants(split_inp[0],
std::stoi(split_inp[1]),
std::stoi(split_inp[2])));
}
}
void print_arr(std::vector<Participants> a) {
for (unsigned int i = 0; i < a.size(); i++) {
std::cout << a[i].login << '\n';
}
}
int partition(std::vector<Participants>& arr, int indx_left, int indx_right) {
Participants pivot = arr[rand() % arr.size()];
int i = indx_left - 1, j = indx_right + 1;
while (true) {
do {
i++;
} while (is_better(arr[i], pivot));
do {
j--;
} while (!is_better(arr[j], pivot));
if (i >= j)
return j;
std::swap(arr[i], arr[j]);
}
}
// the function of comparing two elements
// returns true if the first element is better than the second
bool is_better(Participants p1, Participants p2) {
bool p1_better = false;
if (p1.complited_tasks > p2.complited_tasks) {
p1_better = true;
}
else if (p1.complited_tasks == p2.complited_tasks) {
if (p1.fine < p2.fine)
p1_better = true;
else if (p1.fine == p2.fine) {
if (std::lexicographical_compare(p1.login.begin(), p1.login.end(),
p2.login.begin(), p2.login.end()))
p1_better = true;
}
}
return p1_better;
}
void quick_sort(std::vector<Participants>& arr, int indx_left, int indx_right) {
if (indx_left < indx_right) {
int stop_indx = partition(arr, indx_left, indx_right);
quick_sort(arr, indx_left, stop_indx);
quick_sort(arr, stop_indx + 1, indx_right);
}
return;
}
With input data in the form of
input:
5
alla 4 100
gena 6 1000
gosha 2 90
rita 2 90
timofey 4 80
output:
gena
timofey
alla
gosha
rita
or
input:
5
alla 0 0
gena 0 0
gosha 0 0
rita 0 0
timofey 0 0
output:
alla
gena
gosha
rita
timofey
Everything works correctly, but it gives an error on this test:
input:
13
tufhdbi 76 58
rqyoazgbmv 59 78
qvgtrlkmyrm 35 27
tgcytmfpj 70 27
xvf 84 19
jzpnpgpcqbsmczrgvsu 30 3
evjphqnevjqakze 92 15
wwzwv 87 8
tfpiqpwmkkduhcupp 1 82
tzamkyqadmybky 5 81
amotrxgba 0 6
easfsifbzkfezn 100 28
kivdiy 70 47
output:
easfsifbzkfezn
evjphqnevjqakze
wwzwv
xvf
tufhdbi
tgcytmfpj
kivdiy
rqyoazgbmv
qvgtrlkmyrm
jzpnpgpcqbsmczrgvsu
tzamkyqadmybky
tfpiqpwmkkduhcupp
amotrxgba
Both your i as your j index variables can run out of range of the vector in these loops:
do {
i++;
} while (is_better(arr[i], pivot));
do {
j--;
} while (!is_better(arr[j], pivot));
When that happens, you get into undefined behaviour -- possibly a segmentation fault.
The reason that i or j can run out of bounds is twofold:
You have selected a pivot randomly from the whole array, while you are supposed to select it from the current partition. As a consequence you may select a pivot that is greater than all of the elements within the current partition, or less than all of them. In Hoare's algorithm it is crucial that the loops will encounter the pivot at some point. If that is not guaranteed, the algorithm can break.
Your second inner loop continues when arr[j] is equal to the pivot, but it should exit in that case. Again, when you allow the loop to continue in that case, you risk the while condition will never become true. It is essential to the algorithm that the loop exits when the pivot is encountered.
Here is your partition function with minimal changes to fix those two issues:
int partition(std::vector<Participants>& arr, int indx_left, int indx_right) {
// The pivot must be selected from the current partition:
Participants pivot = arr[indx_left + rand() % (indx_right + 1 - indx_left)];
int i = indx_left - 1, j = indx_right + 1;
while (true) {
do {
i++;
} while (is_better(arr[i], pivot));
do {
j--;
// invert the arguments and don't negate, so that loop exits when equal
} while (is_better(pivot, arr[j]));
if (i >= j)
return j;
std::swap(arr[i], arr[j]);
}
}