§11 Алгоритмы сортировки и поиска. Обобщенные алгоритмы sort и find

Сортировка массива

Для упорядочивания элементов массива необходимо использовать алгоритмы сортировки. Важность сортировки для массивов заключается в том, что нужный элемент в упорядоченном массиве можно найти гораздо быстрее, нежели в неотсортированном.
Различают два вида сортировки: по возрастанию (от меньшего к большему) или по убыванию (от большего к меньшему). Если в массиве имеются равные элементы, то сортировка в направлении от меньшего к большему называется сортировкой по не убыванию, а от большего к меньшему — сортировкой по не возрастанию.
Для работы с массивами создадим две функции myMas() и printMas(). Первая — для вывода исходного массива, а вторая — для вывода измененного массива. Эти функции необходимо поместить в файл проекта с именем (например) myFunction.cpp.

Сортировка отбором (линейная сортировка)

Идея алгоритма очень проста. Допустим, массив сортируется по возрастанию. Будем использовать структуру вложенных циклов. Во внешнем цикле поочередно берутся элементы массива с первого до предпоследнего. Во вложенном цикле проверяется взятый элемент с элементами начиная с последующего до конца массива. Если текущий элемент больше проверяемого элемента, то они меняются местами. Реализация функции сортировки mySortLine на основе C-массива:

void mySortLine(int mas[], const int &k, int &r) {
	for (int i = 0; i < k - 1; i++)
		for (int j = i + 1; j < k; j++) {
			r++;
			if (mas[i] > mas[j]) {
				int buf = mas[i];
				mas[i] = mas[j];
				mas[j] = buf;
			}
		}
}

Эту функцию мы добавим в файл myFunction.cpp.
Программа 11.1. myFunction.cpp

#include <iostream>
#include <iomanip>
#include <random>
#include <ctime>
#include "myFunction.h"
using namespace std;

void myMas(int mas[], const int &k) {
	static default_random_engine rnd(time(0));
	static uniform_int_distribution<unsigned> d(10, 99);
	for (int i = 0; i < k; i++)
		mas[i] = d(rnd);
	cout << "\nЭлементы исходного массива:" << endl;
	for (int i = 0; i < k; i++)
		cout << mas[i] << setw(3);
}

void mySortLine(int mas[], const int &k, int &r) {
	for (int i = 0; i < k - 1; i++)
		for (int j = i + 1; j < k; j++) {
			r++;
			if (mas[i] > mas[j]) {
				int buf = mas[i];
				mas[i] = mas[j];
				mas[j] = buf;
			}
		}
}

void printMas(int mas[], const int &k) {
	cout << "\nЭлементы модифицированного массива:" << endl;
	for (int i = 0; i < k - 1; i++)
		cout << mas[i] << setw(3);
	cout << endl;
}

Заголовочный файл должен содержать следующие прототипы:

#ifndef MYFUNCTION_H_
#define MYFUNCTION_H_
void myMas(int[], const int&);
void mySortLine(int[], const int&, int&);
void printMas(int[], const int&);
#endif /* MYFUNCTION_H_ */

Реализация основного алгоритма программы может выглядеть так:
Программа 11.1. Main.cpp

#include <iostream>
#include "myFunction.h"
using namespace std;

int main() {
	int const n = 50;
	int ar[n];
	int m {};
	myMas(ar, n);
	mySortLine(ar, n, m);
	printMas(ar, n);
	cout << "Всего шагов цикла: "
		 << m
		 << endl;
	return 0;
}

В качестве аргументов в функцию подаются: Си-массив, количество элементов массива и счетчик шагов цикла. Для всех параметров используется передача аргумента по ссылке. Обратите внимание на то, как передается массив. В прототипе и определении функции mySortLine размер массива не передается, а для аргумента используется только имя массива.
Вывод программы 11.1:

Элементы исходного массива:
59 53 45 78 63 11 13 64 64 47 59 48 66 49 35 91 93 47 11 76 26 29 19 12 76 50 45 84 76 95 69 35 48 14 13 12 16 68 28 32 15 40 70 33 41 58 24 34 57 77
Элементы модифицированного массива:
11 11 12 12 13 13 14 15 16 19 24 26 28 29 32 33 34 35 35 40 41 45 45 47 47 48 48 49 50 53 57 58 59 59 63 64 64 66 68 69 70 76 76 76 77 78 84 91 93 95
Всего шагов цикла: 1225

Пузырьковая сортировка (сортировка обменами)

Название сортировки произошло от аналогии с известным физическим явлением: всплытия пузырька воздуха на поверхность в жидкости. Идея алгоритма состоит в следующем. Во внешнем цикле определяется граница области сравнения, а во вложенном цикле сравниваются рядом стоящие элементы: на первом шаге 1-й и 2-й, затем 2-й и 3-й и т. д. Более «легкий» элемент постепенно перемещается («всплывает») в начало массива.
Реализуем программу с помощью контейнера array. Возможная реализация функции mySortBubble:

void mySortBubble(array<int, 50> &mas, int &r) {
	for (size_t i = 0; i < mas.size() - 2; i++)
		for (size_t j = 0; j < mas.size() - i - 1; j++) {
			r++;
			if (mas[j] > mas[j + 1]) {
				int buf = mas[j];
				mas[j] = mas[j + 1];
				mas[j + 1] = buf;
			}
		}
}

Внесем изменения и в другие функции в файле myFunction.cpp для работы с объектом типа array:
Программа 11.2. myFunction.cpp

#include <iostream>
#include <iomanip>
#include <random>
#include <ctime>
#include <array>
#include "myFunction.h"
using namespace std;

void myMas(array<int, 50> &mas) {
	static default_random_engine rnd(time(0));
	static uniform_int_distribution<unsigned> d(10, 99);
	for (auto &i : mas)
		i = d(rnd);
	cout << "\nЭлементы исходного массива:" << endl;
	for (auto &i : mas)
		cout << i << setw(3);
}

void mySortBubble(array<int, 50> &mas, int &r) {
	for (size_t i = 0; i < mas.size() - 2; i++)
		for (size_t j = 0; j < mas.size() - i - 1; j++) {
			r++;
			if (mas[j] > mas[j + 1]) {
				int buf = mas[j];
				mas[j] = mas[j + 1];
				mas[j + 1] = buf;
			}
		}
}

void printMas(array<int, 50> &mas) {
	cout << "\nЭлементы модифицированного массива:" << endl;
	for (auto &i : mas)
		cout << i << setw(3);
	cout << endl;
}

Поскольку размер массива является частью типа в функциях файла myFunction.cpp размер не передается.
Прототипы в заголовочном файле должны быть приведены к следующему виду:

#ifndef MYFUNCTION_H_
#define MYFUNCTION_H_
void myMas(std::array<int, 50>&);
void mySortBubble(std::array<int, 50>&, int&);
void printMas(std::array<int, 50>&);
#endif /* MYFUNCTION_H_ */

Обратите внимание на необходимость указания того факта, что array принадлежит пространству имен std.
Возможная реализация основной программы:
Программа 11.2. Main.cpp

#include <iostream>
#include <array>
#include "myFunction.h"
using namespace std;

int main() {
	array<int, 50> ar {};
	int m {};
	myMas(ar);
	mySortBubble(ar, m);
	printMas(ar);
	cout << "Всего шагов цикла: "
		 << m
		 << endl;
	return 0;
}

Вывод программы 11.2:

Элементы исходного массива:
55 75 51 50 43 16 92 20 98 26 49 98 61 74 58 87 13 83 59 95 78 38 98 76 94 93 66 69 64 94 26 72 69 30 22 64 36 15 36 86 83 75 85 96 11 95 83 14 41 43
Элементы модифицированного массива:
11 13 14 15 16 20 22 26 26 30 36 36 38 41 43 43 49 50 51 55 58 59 61 64 64 66 69 69 72 74 75 75 76 78 83 83 83 85 86 87 92 93 94 94 95 95 96 98 98 98
Всего шагов цикла: 1224

Оба алгоритма сортировки имеют примерно одинаковую эффективность. Но всё же это самые медленные алгоритмы с очень низкой эффективностью, хорошо проявляемой на большом количестве элементов массива (> 1000). Существуют гораздо более эффективные алгоритмы. Их разработка выходит за рамки нашего курса.
Если есть необходимость поменять направление сортировки, то для этого всего лишь требуется поменять знак сравнения в инструкции if на противоположный.

Быстрый поиск в массиве

Как уже было сказано, эффективный алгоритм поиска можно реализовать только в упорядоченном массиве. Один из самых простых алгоритмов — это алгоритм бинарного (двоичного) поиска. Идея алгоритма заключается в следующем. Вместо того, чтобы перебирать все элементы массива, сравнивая каждый элемент с исходным числом, массив делится пополам и «средний» элемент сравнивается с искомым. Отсюда делается вывод в какой половине массива нужно продолжать поиск.

size_t myBinSearch(array<int, 50> &mas, int &r, int &x) {
	size_t L = 0, R = mas.size(), q;
	do {
		q = (R + L) / 2;
		if (mas[q] > x)
			R = q;
		else
			L = q;
		r++;
	} while (L < R - 1);
	return L;
}

Функция myBinSearch реализована в виде функции возвращающей значение типа size_t (позицию искомого элемента). Мы не рассматриваем тот случай, когда в массиве имеются несколько равных элементов. Возможная реализация основной программы может быть такой:
Программа 11.3

#include <iostream>
#include <array>
#include "myFunction.h"
using namespace std;

int main() {
	array<int, 50> ar {};
	int m {}, a {};
	size_t d {};
	cout << "Введите число для поиска: ";
	cin >> a;
	myMas(ar);
	mySortBubble(ar);
	printMas(ar);
	d = myBinSearch(ar, m, a);
	cout << "Всего шагов цикла: "
		 << m
		 << endl;
	if (ar[d] == a)
		cout << "Элемент находится на "
		 	 << d
			 << "-ой позиции"
			 << endl;
	else
		cout << "Такого элемента в массиве нет"
			 << endl;
	return 0;
}
Элементы исходного массива:
95 45 84 95 98 78 69 43 22 73 67 43 35 21 33 84 19 46 48 98 37 44 22 44 46 11 66 49 56 70 70 51 15 55 98 65 85 67 98 97 92 66 40 28 39 25 12 49 61 12
Элементы модифицированного массива:
11 12 12 15 19 21 22 22 25 28 33 35 37 39 40 43 43 44 44 45 46 46 48 49 49 51 55 56 61 65 66 66 67 67 69 70 70 73 78 84 84 85 92 95 95 97 98 98 98 98
Всего шагов цикла: 5
Элемент находится на 28-ой позиции

Библиотека обобщенных алгоритмов

Алгоритмы сортировки, рассмотренные выше, конечно не сделают ваши программы эффективными. Стандартная библиотека C++ (STD) имеет в своем арсенале библиотеку обобщенных алгоритмов в которой уже разработаны высокоэффективные алгоритмы для работы с контейнерами (а также с C-массивами), в том числе, алгоритмы поиска и сортировки. Библиотека алгоритмов становится доступной после подключения заголовков:

#include <algorithm> 
#include <functional> 
#include <iterator> 

Примечание. Для классов контейнеров заголовок iterator не включается.
В качестве аргументов эти функции принимают итераторы.
Функция, выполняющая сортировку, называется sort. Эта функция имеет тип void и используется в двух вариантах:

sort(first, last);
sort(first, last, comp);

Первый вариант осуществляет сортировку по возрастанию. Для изменения направления сортировки используется второй вариант. Например, для осуществления сортировки по убыванию необходимо использовать предопределенный функциональный объект (comp) — greater<int>():

sort(first, last, greater<int>());

Поиск элемента равного value осуществляет функция find. Эта функция возвращает итератор указывающий на первый элемент равный value или last, если такой элемент не найден:

find(first, last, value);

Объект (value) может быть как константой, так и переменной.
Приведем пример использования функций sort и find в одной программе.
Программа 11.4

#include <iostream>
#include <algorithm>
#include <ctime>
#include <random>
#include <array>
using namespace std;

int main() {
	array<int, 20> mas;
	default_random_engine rnd(time(0));
	uniform_int_distribution<unsigned> d(10, 99);
	for(auto &i : mas) {
		i = d(rnd);
		cout << i << " ";
	}
	cout << endl;
	auto first = mas.begin();
	auto last = mas.end();
	sort(first, last);
	for(auto &i : mas) cout << i << " ";
	cout << endl;
	int n;
	cout << "n = "; cin >> n;
	auto res = find(first, last, n);
	if (res != last)
		cout << "Элемент найден!" << endl;
	else
		cout << "Элемент не найден!" << endl;
	return 0;
}


Comments are closed