[По полочкам] Алгоритмы сортировок. Часть 1
Вводная часть
Существует большое количество различных сортировок, которые применяются повсеместно в программах. Алгоритмы сортировок помогают сэкономить такие ресурсы, как время работы какой-либо части кода и, соответственно, время человека и память, используемую для выполнения вашей программы. Например:
При редактировании файла нет необходимости держать весь файл в оперативной памяти. Каждой строке присваивается порядковый номер, и после внесения изменений достаточно обновленные строки отсортировать и вставить в сам файл.
Группировка элементов по признакам, которые характеризуются определенным числом или текстовой величиной (символы также поддаются упорядочиванию, например, по расположению их в алфавите или по номеру в таблице символов Юникода)
При сравнении двух и более таблиц или файлов для экономии времени достаточно отсортировать их. Таким образом, не надо «бегать» от одной строки к другой, а анализ будет более удобным и структурированным.
Алгоритмы сортировок применяются в различных областях, причина их использования состоит и в упорядочивании тех или иных структур для простоты понимания человеком, и в оптимизации работы программы по отношению к ресурсам компьютера.
Каждый алгоритм сортировки обладает такой характеристикой, как сложность (худший, средний и лучший случаи) и устойчивость.
Устойчивая сортировка — сортировка, не меняющая относительный порядок сортируемых элементов, имеющих одинаковые ключи, по которым происходит сортировка.
В статье публикуются программные коды сортировок на языке C++, в которых присутствует функция, меняющая местами элементы в массиве:
template
void swap(std::vector& arr, unsigned int A, unsigned int B) {
T temp = arr[A];
arr[A] = arr[B];
arr[B] = temp;
} Простые виды сортировок
В этой части мы познакомимся с некоторыми алгоритмами, которые не применяются в общем случае из-за не особо большой скорости их работы, однако, позволяют вникнуть в некоторые принципы сортировки, используемые в более сложных алгоритмах.
Сортировка обменом (Exchange Sort)
Сначала сравнивается первый элемент со всеми последующими и меняется местами со сравниваемым, если требуется (зависит от условия: сортировка выполняется по возрастанию или по убыванию). Затем аналогичная процедура выполняется для второго, третьего и т.д.
Код на C++:
template
void exchangeSort(std::vector& arr) {
for (unsigned int i = 0; i < arr.size() - 1; i++) {
for (unsigned int j = i + 1; j < arr.size(); j++) {
if (arr[i] > arr[j])
swap(arr, i, j);
}
}
} Сложность: O (n^2) (во всех случаях)
Не является устойчивой
Преимущества и недостатки:
+ Простота реализации
— Медленная
Сортировка выбором (Selection Sort)
Находится минимальный (или максимальный, если сортировка происходит по убыванию) элемент на всем отрезке массива и переставляется в начало этого отрезка. После длина отрезка уменьшается на единицу слева и процедура повторяется.
Код на C++:
template
void selectionSort(std::vector& arr) {
for (unsigned int i = 0; i < arr.size(); i++) {
unsigned int j_min = i;
unsigned int j = i + 1;
for (; j < arr.size(); j++) {
if (arr[j] < arr[j_min])
j_min = j;
}
if (j_min != j)
swap(arr, i, j_min);
}
} Сложность: O (n^2) (во всех случаях)
Не является устойчивой
Преимущества и недостатки:
+ Простота реализации
— Медленная
Сортировка пузырьком (Bubble Sort)
Происходит проход по массиву с обменом местами соседних элементов, если требуется (зависит от условия: сортировка выполняется по возрастанию или по убыванию), до тех пор, пока массив не будет полностью отсортирован.
Код на С++:
template
void bubbleSort(std::vector& arr) {
bool swapped;
do {
swapped = false;
for (unsigned int i = 0; i < arr.size() - 1; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
swapped = true;
}
}
} while (swapped);
} Сложность: O (n) — лучший случай
O (n^2) — средний и худший случаи
Является устойчивой
Преимущества и недостатки:
+ Простота реализации
— Медленная
Сортировка вставками (Insertion Sort)
Первый элемент считается отсортированной частью массива. Последующие элементы переносятся в отсортированную часть на нужную позицию. Таким образом, при каждом переносе отсортированная часть увеличивается на один элемент.
Код на C++:
template
void insertionSort(std::vector& arr) {
for (unsigned int i = 1; i < arr.size(); i++) {
if (arr[i] < arr[i - 1]) {
unsigned int j = i;
while ((j > 0) && (arr[j] < arr[j - 1])) {
swap(arr, j, j - 1);
j--;
}
}
}
} Сложность: O (n) — лучший случай
O (n^2) — средний и худший случаи
Является устойчивой
Преимущества и недостатки:
+ Простота реализации
+ Быстрая на частично упорядоченных последовательностях
— Медленная в общем случае
Мини-заключение
Рассмотренные алгоритмы имеют достаточно небольшие скорости сортировки, поэтому в проектах следует использовать, например, сортировку Шелла (Shell Sort) или быструю сортировку (Quick Sort). Эти виды сортировок будут разобраны в следующей части.
Ссылка на код с сортировками
