Сортировки

Передача вектора в функцию в качестве параметра

Крупные структуры данных (векторы, строки) лучше передавать в функцию по ссылке. В этом случае не создается копия объекта, а передается только указатель на место его расположения в памяти компьютера. В этом случае функция также может изменять содержимое вектора (строки). Пример прототипа функции сортировки:

void sort(vector <int> & a);

Если функция не изменяет содержимое передаваемого вектора или строки, то лучше передавать их по константнойссылке, добавив слово const в начале описания параметра. Пример прототипа функции линейного поиска:

bool find(const vector <int> & a, int key);

Алгоритмы сортировки квадратичной сложности

Сортировка выбором

В алгоритме сортировки выбором мы находим наибольший элемент в массиве и ставим его на первое место, затем находим наибольший элемент из оставшихся и ставим его на второе место и т.д. Таким образом, в решении имеется цикл for(i = 0; i < n - 1; ++i), внутри которого находится наибольший элемент среди A[i], A[i+1], ..., A[n-1], который устанавливается на место A[i].

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

В алгоритме сортировки вставкой в каждый произвольный момент начальная часть массива уже отсортирована. В решении имеется цикл for(i = 1; i < n; ++i), внутри которого в предположении, что элементы массива A[0], A[1], ..., A[i-1] уже отсортированы, элемент A[i] добавляется в отсортированную часть. Для этого находится позиция, в которую необходимо вставить элемент A[i], затем осуществляется циклический сдвиг фрагмента уже отсортированной части.

Сортировка пузырьком

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

Использование стандартной сортировки

Библиотека STL содержит готовую реализацию сортировки, имеющую сложность релизации \(O(n\log n)\). Для использования функции sort нужно подключить заголовочный файл algorithm:

#include <algorithm>

Для сортировки вектора a по неубыванию нужно вызвать функцию sort следующим образом:

sort(a.begin(), a.end());

Для сортировки в обратном порядке используются так называемые reverse iterators:

sort(a.rbegin(), a.rend());