根据任务的情况，需要对结构体数组进行排序。数据应按如下方式排序：在比较两个参与者时，解决任务越多的参与者排名越高。如果解决的任务数量相等，则惩罚较小的参与者先进行。如果惩罚也匹配，那么第一个登录的将是按字典顺序排列较早的登录。排序必须使用霍尔方法完成。如果我只比较数字，该算法就有效，但是当对某些数据使用比较器时，会出现错误“分段错误（核心转储）”。我无法弄清楚我做错了什么？ 我的代码如下所示：
// 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;
}
输入数据的形式为
input:
5
alla 4 100
gena 6 1000
gosha 2 90
rita 2 90
timofey 4 80
output:
gena
timofey
alla
gosha
rita
或
input:
5
alla 0 0
gena 0 0
gosha 0 0
rita 0 0
timofey 0 0
output:
alla
gena
gosha
rita
timofey
一切正常，但在此测试中出现错误：
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
您的
ij do {
i++;
} while (is_better(arr[i], pivot));
do {
j--;
} while (!is_better(arr[j], pivot));
当这种情况发生时，你会陷入未定义的行为——可能是分段错误。
ij您从整个数组中随机选择了一个主元，而您应该从当前分区中选择它。因此，您可以选择大于或小于当前分区中所有元素的主元。在霍尔算法中，循环在某个点“遇到”枢轴至关重要。如果不能保证这一点，算法可能会崩溃。 当
arr[j]while条件永远不会成立的风险。当遇到枢轴时循环退出对于算法来说至关重要。
这是您的partitionint 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]);
}
}