|
Усе сартаванні, разабраныя вышэй, дазвалялі ўпарадкаваць элементы масіву па ўзрастанні. Калі ў алгарытме замяніць параўнанне элементаў на параўнанне значэнняў функцыі ад гэтых элементаў, то сартаванні могуць быць разнастайнымі.
Функцыю для параўнання двух аб’ектаў называюць кампаратарам (ад англ. compare — параўнаць).
Функцыя-кампаратар залежыць ад двух параметраў і вяртае лагічнае значэнне. Тып параметраў функцыі павінен супадаць з тыпам элементаў у масіве. Функцыя павінна вяртаць значэнне true для двух значэнняў, якія знаходзяцца «ў парадку», і false ў адваротным выпадку.
Прыклад 18.17. Дадзены лінейны масіў з цэлых лікаў. Напісаць праграму сартавання масіву так, каб усе цотныя лікі стаялі ў пачатку масіву, а няцотныя — у канцы. Даныя згенерыраваць выпадковым чынам.
Этапы выканання задання
I. Зыходныя даныя: пераменныя n — колькасць лікаў у масіве, a — масіў.
II. Вынік: адсартаваны масіў а.
III. Алгарытм рашэння задачы.
- Увод зыходных даных. Элементы масіву згенерыраваны выпадковым чынам.
- Для рашэння задачы будзем выкарыстоўваць алгарытм сартавання абменам.
- Створым кампаратар (функцыю параўнання), якая будзе параўноўваць лікі па астачах ад дзялення на 2.
- Будзем мяняць элементы месцамі, калі яны размешчаны «не ў парадку».
- Вывад выніку.
IV. Апісанне пераменных: n – int, a – vector<int>.
Для рашэння гэтай задачы выбар алгарытму сартавання абменам не з’яўляецца аптымальным, паколькі ён патрабуе каля n2 аперацый параўнання і абмену. Прыклад неабходны для таго, каб паказаць выкарыстанне функцыі-кампаратара.
Для атрымання аптымальнага рашэння можна зыходзіць з таго факта, што ўсе лікі адносна астачы пры дзяленні на 2 бываюць усяго дзвюх катэгорый (цотныя і няцотныя), і для іх сартавання дастаткова усяго аднаго праходу па масіве. Гэта можна зрабіць па аналогіі з алгарытмам хуткага сартавання з дапамогай двух паказальнікаў: злева шукаем першы няцотны, а справа — апошні цотны і мяняем іх месцамі (прыклад 18.18).
Прыклад 18.19. Дадзены лінейны масіў са слоў. Напісаць праграму сартавання масіву так, каб словы размяшчаліся ў парадку спадання колькасці літар «а» ў слове. Даныя прачытаць з файла.
Этапы выканання задання
I. Зыходныя даныя: пераменныя n — колькасць слоў у масіве, a — масіў.
II. Вынік: адсартаваны масіў а.
III. Алгарытм рашэння задачы.
- Увод зыходных даных.
- Для рашэння задачы будзем выкарыстоўваць алгарытм сартавання выбарам.
- Створым кампаратар (функцыю параўнання), які будзе параўноўваць словы па колькасці літар «а» ў слове.
- Таксама створым функцыю, якая будзе вызначаць колькасць літар «а» ў слове.
- Вывад выніку.
IV. Апісанне пераменных: n – int, a – vector<string>.
Прыклад 18.20. У тэкставым файле input.txt захоўваецца інфармацыя пра студэнтаў. Для кожнага студэнта паказаны яго прозвішча, горад, з якога ён прыехаў, і тры лікі — балы за ЦТ, з якімі ён паступіў у ВНУ. Адсартаваць спіс студэнтаў у парадку спадання сумарнага бала за ЦТ. Вывесці прозвішча, горад і сумарны бал.
Этапы выканання задання
I. Зыходныя даныя: пераменныя n — колькасць запісаў пра студэнтаў, a — масіў структур.
II. Вынік: адсартаваны масіў а.
III. Алгарытм рашэння задачы.
- Увод зыходных даных.
- У апісанні структуры, акрамя палёў, паказаных ва ўмове задачы, дабавім поле «сума», у якой запішам сумарны бал (апісанне структуры было разабрана ў прыкладзе 17.8).
- Для рашэння задачы будзем выкарыстоўваць алгарытм сартавання простымі ўстаўкамі.
- Створым кампаратар (функцыю параўнання), якая будзе параўноўваць дзве структуры па полі сумы балаў.
- Вывад выніку.
IV. Апісанне пераменных:: n – int, a – vector<student>. |
Кампаратар — гэта адносіны парадку. Як функцыя ён павінен задавальняць аксіёмы адносінаў парадку:
- функцыя з’яўляецца дэтэрмінаванай: comp(a,b) для канкрэтных a і b заўсёды вяртае адзін і той жа вынік;
- функцыя валодае ўласцівасцю транзітыўнасці: comp(a,b) && comp(b,c) абазначае тое ж самае, што
comp(a,c) (у самым простым выпадку, калі a < b і b < c, то a < c);
- функцыя валодае ўласцівасцю антысіметрычнасці: omp(a,b) && comp(b,a) абазначае, што а = b.
Прыклад 18.17.
V. Праграма:
|
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
bool comp(int x, int y)
{
return (x % 2 < y % 2);
}
using namespace std;
int main()
{
srand(time(NULL));
int n;
cout << "n = ";
cin >> n;
vector <int> a(n);
cout << "chisla:" << endl;
for (int i = 0; i < n; i++){
a[i] = rand() % 100;
cout << a[i] << " ";
}
cout << endl << "sort" << endl;
for (int k = 1; k < n; k++)
for (int i = 0; i < n - k; i++)
if (!comp(a[i], a[i + 1]))
swap(a[i], a[i + 1]);
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
return 0;
}
|
VI. Тэсціраванне.
Прыклад 18.18. Фрагмент праграмы:
|
int i = 0, j = n - 1;
while (i <= j) {
while (a[i] % 2 == 0)
i++;
while (a[j] % 2)
j--;
if (i <= j) {
swap (a[i], a[j]);
i++;
j--;
}
}
|
Прыклад 18.19.
V. Праграма:
|
#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <windows.h>
using namespace std;
using namespace std::__cxx11;
int kol_a(string s)
{
int k = 0;
for (int i = 0; i < s.length(); i++)
if (s[i] == 'а' || s[i] == 'А')
k++;
return k;
}
bool comp(string x, string y)
{
return (kol_a(x) > kol_a(y));
}
int main()
{
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
ifstream fin("input.txt");
ofstream fout("output.txt");
int n;
fin >> n;
fin.ignore();
vector <string> a(n);
for (int i = 0; i < n; i++)
fin >> a[i];
for (int k = 0; k < n - 1; k++){
int nmax = k;
for (int i = k + 1; i < n; i++)
if (comp (a[i], a[nmax]))
nmax = i;
swap(a[k], a[nmax]);
}
for (int i = 0; i < n; i++)
fout << a[i] << endl;
return 0;
}
|
V. Тэсціраванне. У тэкставы файл запісаны словы з пункта 18.1.
 
Прыклад 18.20.
V. Фрагмент праграмы (функцыю vvod і бібліятэкі, што падключаюцца, гл. у прыкладзе 17.8):
|
struct student
{
string fam, gorod;
vector <int> otm = vector<int>(3);
int summa;
};
…
bool comp(student x, student y)
{
return (x.summa > y.summa);
}
int main()
{
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
vector <student> a;
vvod (a);
ofstream fout ("output.txt");
for (int k = 1; k < a.size(); k++){
int i = k;
while (i > 0 &&
!comp(a[i - 1], a[i])){
swap(a[i - 1], a[i]);
i--;
}
}
for (int i = 0; i < a.size(); i++){
fout << a[i].fam << '\t';
fout << a[i].gorod << '\t';
fout << a[i].summa << endl;
}
return 0;
}
|
VI. Тэсціраванне. Выкарыстоўваецца тэкставы файл з прыкладу 17.8.
|
