|
Все сортировки, разобранные выше, позволяли упорядочить элементы массива по возрастанию. Если в алгоритме заменить сравнение элементов на сравнение значений функции от этих элементов, то сортировки могут быть разнообразными.
Функцию для сравнения двух объектов называют компаратором (от англ. compare — сравнить).
Функция-компаратор зависит от двух параметров и возвращает логическое значение. Тип параметров функции должен совпадать с типом элементов в массиве. Функция должна возвращать знание true, для двух значений, которые находятся «в порядке» и false в противном случае.
Пример 18.17. Дан линейный массив из целых чисел. Написать программу сортировки массива так, чтобы все четные числа стояли в начале массива, а нечетные — в конце. Данные сгенерировать случайным образом.
Этапы выполнения задания
I. Исходные данные: переменные n — количество чисел в массиве, a — массив.
II. Результат: отсортированный массив а.
III. Алгоритм решения задачи.
1. Ввод исходных данных. Элементы массива сгенерированы случайным образом.
2. Для решения задачи будем использовать алгоритм сортировки обменом.
3. Создадим компаратор (функцию сравнения), которая будет сравнивать числа по остаткам от деления на 2.
4. Будем менять элементы местами, если они расположены «не в порядке».
5. Вывод результата.
IV. Описание переменных: n – int, a – vector<int>.
Для решения этой задачи выбор алгоритма сортировки обменом не является оптимальным, поскольку он потребует порядка n2 операций сравнения и обмена. Пример необходим для того, чтобы показать использование функции-компаратора.
Для получения оптимального решения можно исходить из того факта, что все числа относительно остатка при делении на 2 бывают всего двух категорий (четные и нечетные), и для их сортировки достаточно всего одного прохода по массиву. Это можно сделать по аналогии с алгоритмом быстрой сортировки с помощью двух указателей: слева ищем первый нечетный, а справа — последний четный и меняем их местами (пример 18.18).
Пример 18.19. Дан линейный массив из слов. Написать программу сортировки массива так, чтобы слова располагались в порядке убывания количества букв «а» в слове. Данные прочитать из файла.
Этапы выполнения задания
I. Исходные данные: переменные n — количество слов в массиве, a — массив.
II. Результат: отсортированный массив а.
III. Алгоритм решения задачи.
1. Ввод исходных данных..
2. Для решения задачи будем использовать алгоритм сортировки выбором.
3. Создадим компаратор (функцию сравнения), которая будет сравнивать слова по количеству букв «а» в слове.
4. Также создадим функцию, которая будет определять количество букв «а» в слове.
5. Вывод результата.
IV. Описание переменных: n – int, a – vector<string>.
Пример 18.20. В текстовом файле input.txt хранится информация о студентах. Для каждого студента указана его фамилия, город, из которого он приехал, и три числа — баллы за ЦТ, с которыми он поступил в вуз. Отсортировать список студентов в порядке убывания суммарного балла за ЦТ. Вывести фамилию, город и суммарный балл.
Этапы выполнения задания
I. Исходные данные: переменные n — количество записей о студентах, a — массив структур.
II. Результат: отсортированный массив а.
III. Алгоритм решения задачи.
1. Ввод исходных данных.
2. В описании структуры, кроме полей, указанных в условии задачи, добавим поле сумма, в которой запишем суммарный балл (описание структуры было разобрано в примере 17.8).
3. Для решения задачи будем использовать алгоритм сортировки простыми вставками.
4. Создадим компаратор (функцию сравнения), которая будет сравнивать две структуры по полю суммы баллов.
5. Вывод результата.
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.
|
