Порядок быстрой сортировки по первому типу, а затем по второму типу векторной пары строк и int

Question

Порядок быстрой сортировки по первому типу, а затем по второму типу векторной пары строк и int

Это для моих данных структурирует домашнюю работу, и я пытаюсь выяснить, как сделать мой порядок функций быстрой сортировки путем возрастания значений строки, а затем с помощью int. Я могу получить строку, но тогда как мне сделать второй заказ?

vector<PAIR> readwords::count_vector(vector<string> sv) {
unsigned int i = 0;
int j = 0;
int match = 0;

// cout << "Working with these string: " << endl;
// print_vector(sv);

for (i=0; i < sv.size(); i++) {
// cout << "count of i: " << i << " word is: " << sv.at(i) << endl;

match = 0;
if(readwords::vp.size() == 0) { readwords::vp.push_back(make_pair(sv.at(i),1)); continue; }

for (j=readwords::vp.size() - 1; j >= 0; --j) {
if (sv.at(i) == readwords::vp.at(j).first) {
// cout << "Match found with: " << sv.at(i) << endl;;
readwords::vp.at(j).second = readwords::vp.at(j).second + 1;
match = 1;
}

// cout << "Value of j and match: " << j << match << endl;
if ( j == 0 && match == 0) {
// cout << "Match found at end with: " << sv.at(i) << endl;;
readwords::vp.push_back(make_pair(sv.at(i),1));
}
}
}

return readwords::vp;
}

typedef pair<string, int> PAIR;

void readwords::quicksort(char how[]) {

char key[] = "k";
char value[] = "v";

// if(strcmp(how,key) || strcmp(how,value)) {
// cout << "Seams you used a sorting function with an incorrect argument.  Recompile!" << endl;
// exit(1);
// }

if(!strcmp(how,key)) {
qs_by_key(readwords::vp, 0, readwords::vp.size() - 1);
print_vectorpair(readwords::vp);
}

if(!strcmp(how,value)) {
qs_by_value(readwords::vp, 0, readwords::vp.size() - 1);
print_vectorpair(readwords::vp);
}

}

void readwords::qs_by_value(vector< PAIR > &vp, int start, int end) {
int pivot;

if(start < end) {
pivot = qs_part_by_value(vp, start, end);
qs_by_value(vp, start, pivot-1);
qs_by_value(vp, pivot+1, end);
}
}

int readwords::qs_part_by_value(vector< PAIR > &vp, int start, int end) {
int mid = (start + end)/2;
swap(vp[start], vp[mid]);
int pivot_i = start;
string pivot_val = vp[start].first;

for(int i = start + 1; i <= end; i++) {
if(vp[i].first < pivot_val) {
pivot_i++;
swap(vp[pivot_i], vp[i]);
}
}
swap(vp[start], vp[pivot_i]);
return pivot_i;
}

void readwords::qs_by_key(vector< PAIR > &vp, int start, int end) {
int pivot;

if(start < end) {
pivot = qs_part_by_key(vp, start, end);
qs_by_key(vp, start, pivot-1);
qs_by_key(vp, pivot+1, end);
}
}

-1

c++order pair quicksort vector

Решение

Другие решения

Самый простой способ добиться этого — отсортировать все сначала по int (вторичный критерий), а затем string (основной критерий), используя устойчивый алгоритм по крайней мере для второго рода. Таким образом, все элементы с одинаковыми string останется в том же порядке, что и раньше; это, они останутся отсортированными по int,

Вообще говоря, быстрая сортировка не является устойчивым алгоритмом, но некоторые реализации этого являются. Например (взято из Википедия):

  function quicksort('array')
if length('array') ≤ 1
return 'array'  // an array of zero or one elements is already sorted
select and remove a pivot value 'pivot' from 'array'
create empty lists 'less' and 'greater'
for each 'x' in 'array'
if 'x' ≤ 'pivot' then append 'x' to 'less'
else append 'x' to 'greater'
return concatenate(quicksort('less'), 'pivot', quicksort('greater')) // two recursive calls

1

Источник

Accepted Answer

Сначала сравните строки. Тогда, только если это приводит к равенству (strcmp возвращая 0), сравните целые числа. псевдокод:

algorithm compare-pairs(Pair(x_str, x_i), Pair(y_str, y_i))
difference = compare-strings(x_str, y_str)
if difference == 0 then
difference = compare-integers(x_i, y_i)
return difference

(В качестве альтернативы сначала сортируйте по строке, затем группируйте по строке, затем сортируйте по целому числу.)

2