[По полочкам] Алгоритмы сортировок. Часть 1

Вводная часть

Существует большое количество различных сортировок, которые применяются повсеместно в программах. Алгоритмы сортировок помогают сэкономить такие ресурсы, как время работы какой-либо части кода и, соответственно, время человека и память, используемую для выполнения вашей программы. Например:

• При редактировании файла нет необходимости держать весь файл в оперативной памяти. Каждой строке присваивается порядковый номер, и после внесения изменений достаточно обновленные строки отсортировать и вставить в сам файл.

• Группировка элементов по признакам, которые характеризуются определенным числом или текстовой величиной (символы также поддаются упорядочиванию, например, по расположению их в алфавите или по номеру в таблице символов Юникода)

• При сравнении двух и более таблиц или файлов для экономии времени достаточно отсортировать их. Таким образом, не надо «бегать» от одной строки к другой, а анализ будет более удобным и структурированным.

Алгоритмы сортировок применяются в различных областях, причина их использования состоит и в упорядочивании тех или иных структур для простоты понимания человеком, и в оптимизации работы программы по отношению к ресурсам компьютера.

Каждый алгоритм сортировки обладает такой характеристикой, как сложность (худший, средний и лучший случаи) и устойчивость.

Устойчивая сортировка — сортировка, не меняющая относительный порядок сортируемых элементов, имеющих одинаковые ключи, по которым происходит сортировка.

В статье публикуются программные коды сортировок на языке C++, в которых присутствует функция, меняющая местами элементы в массиве:

template <typename T>   void swap(std::vector<T>& arr, unsigned int A, unsigned int B) { T temp = arr[A]; arr[A] = arr[B]; arr[B] = temp; }

Простые виды сортировок

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

Сортировка обменом (Exchange Sort)

Сначала сравнивается первый элемент со всеми последующими и меняется местами со сравниваемым, если требуется (зависит от условия: сортировка выполняется по возрастанию или по убыванию). Затем аналогичная процедура выполняется для второго, третьего и т.д.

Код на C++:

template <typename T> void exchangeSort(std::vector<T>& 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 <typename T> void selectionSort(std::vector<T>& 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 <typename T> void bubbleSort(std::vector<T>& 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 <typename T> void insertionSort(std::vector<T>& 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). Эти виды сортировок будут разобраны в следующей части.

Ссылка на код с сортировками