Народ, всем привет. Сортировка это одна из самых распространённых задач в программировании, хоть многие в начале пути этого не замечают. Но почти в любом приложении, будь то база данных, веб-сервис или мобильное приложение, часто требуется упорядочить данные, по алфавиту, по числам, по дате и т.д. И именно поэтому изучение алгоритмов, в том числе сортировки, позволяют организовать данные в определённом нужном нам порядке, как-то их обработать и все такое прочее.
Это пока вы молоды вы учитесь писать Hello World и пишете свой первый калькулятор, где не нужны подобные алгоритмы. А потом, устроившись на настоящую работу, где чаще всего работают с массивами данных (причем с большими) начинается изобретение велосипеда и придумывание методов сортировки самостоятельно. А они уже все давно написаны. Чаще всего сортировку применяют в:
- в банковских, финансовых организациях, при работе с цифрами
- поисковых системах, упорядочивание результатов по релевантности.
- интернет-магазинах, сортировка товаров по цене, рейтингу, популярности.
- базах данных, индексирование, ускорение запросов.
- графика, глубинная сортировка (Z-ordering).
Что такое сортировка?
Сортировка — это процесс упорядочивания элементов списка или массива по определённому критерию. Например, числа можно отсортировать по возрастанию или убыванию, строки — в алфавитном порядке, а записи — по дате или имени.
Алгоритмы сортировки делятся на несколько категорий, в зависимости от сложности и эффективности (скорости, затрат памяти и т.д.) Сегодня мы поговорим про самые простые, но на них проще всего учиться и понять суть. В следующих частях мы продолжим уже с более эффективными и востребованными алгоритмами.
1. Простые (обучающие):
- Сортировка пузырьком (Bubble Sort)
- Сортировка вставками (Insertion Sort)
- Сортировка выбором (Selection Sort)
2. Эффективные (используются на практике):
- Быстрая сортировка (Quick Sort)
- Сортировка слиянием (Merge Sort)
- Пирамидальная сортировка (Heap Sort)
3. Специализированные:
- Поразрядная сортировка (Radix Sort)
- Подсчётом (Counting Sort)
- Bucket Sort (сортировка корзинами)
Если Вам нравятся наши статьи, и вы хотите отблагодарить автора (на развитие канала), нам будет очень приятно!
Сортировка пузырьком
Сортировка пузырьком одна из самых малоэффективных, зато простых, она просто проходит по массиву многократно, сравнивая соседние элементы и меняя их местами, если они стоят в неправильном порядке (например, если сортировка по возрастанию и левый элемент больше правого, меняет их местами). В результате на каждой итерации крупнейший (или наименьший) элемент "всплывает" в конец массива — как пузырёк в воде. Отсюда и название.
Давайте на примере, допустим, у нас есть массив: [5, 2, 4, 1, 3] и мы хотим отсортировать его по возрастанию.
Первая итерация:
- сравниваем 5 и 2 → 5 > 2 → меняем → [2, 5, 4, 1, 3]
- сравниваем 5 и 4 → 5 > 4 → меняем → [2, 4, 5, 1, 3]
- сравниваем 5 и 1 → 5 > 1 → меняем → [2, 4, 1, 5, 3]
- сравниваем 5 и 3 → 5 > 3 → меняем → [2, 4, 1, 3, 5]
- теперь 5 — на своём месте.
Вторая итерация:
- сравниваем 2 и 4 → 2 < 4 → ничего не делаем
- сравниваем 4 и 1 → 4 > 1 → меняем → [2, 1, 4, 3, 5]
- сравниваем 4 и 3 → 4 > 3 → меняем → [2, 1, 3, 4, 5]
- (5 уже не трогаем)
Третья итерация:
- сравниваем 2 и 1 → 2 > 1 → меняем → [1, 2, 3, 4, 5]
- сравниваем 2 и 3 → уже порядок → ничего не делаем
- сравниваем 3 и 4 → порядок → ничего не делаем
Четвёртая итерация:
- сравниваем 1 и 2 → порядок → ничего не делаем
- сравниваем 2 и 3 → порядок → ничего не делаем
Теперь массив отсортирован. У данной сортировки очень низкая эффективность, так как даже для такого маленького массива происходит слишком много итераций и сравнений. Поэтому, использовать данный алгоритм можно лишь для обучения (первое знакомство с сортировками, чисто попробовать) и для очень маленьких массивов. А вот если важна производительность лучше не надо.
Сортировка вставками
Сортировка вставками работает по принципу, похожему на сортировку карт в руке: мы перебираем элементы по одному и вставляем каждый в нужное место среди уже отсортированных. Иными словами, на каждой итерации:
- берётся очередной элемент из "неотсортированной части".
- он сравнивается с элементами "отсортированной части" слева.
- пока элемент меньше, происходит сдвиг, и в нужное место вставляется текущий элемент.
Теперь давайте на примере. Допустим, у нас есть массив [5, 2, 4, 1, 3]
Шаг 1: берем первый элемент – это 2 (ну 5 пропускаем, понятно)
- Сравниваем с 5 → 2 < 5 → сдвигаем 5 вправо, вставляем 2 на его место → [2, 5, 4, 1, 3]
Шаг 2: берем следующий элемент - это 4
- Сравниваем с 5 → 4 < 5 → сдвигаем 5
- Сравниваем с 2 → 4 > 2 → остановка, тут все верно, поэтому вставляем 4 → [2, 4, 5, 1, 3]
Шаг 3: следующий элемент 1
- Сравниваем с 5 → 1 < 5 → сдвигаем
- Сравниваем с 4 → 1 < 4 → сдвигаем
- Сравниваем с 2 → 1 < 2 → сдвигаем
- Вставляем 1 в самое начало → [1, 2, 4, 5, 3]
Шаг 4: последний элемент 3
- Сравниваем с 5 → 3 < 5 → сдвигаем
- Сравниваем с 4 → 3 < 4 → сдвигаем
- Сравниваем с 2 → 3 > 2 → остановка, вставляем 3 → [1, 2, 3, 4, 5]
Готово! Массив отсортирован. Данный алгоритм вполне жизнеспособен, и подходит для маленьких массивов (до 30-50 элементов) и когда нужна стабильная сортировка. Но все же, когда важна высокая производительность на случайно перемешанных данных и у вас большие объёмы данных, я не советую.
Сортировка выбором
Сортировка выбором работает следующим образом. Мы каждый раз находим наименьший элемент в неотсортированной части массива и меняет его местами с первым элементом этой части. Повторяем процесс со следующей неотсортированной позицией, пока весь массив не будет отсортирован. Таким образом, сортировка разделяет массив на две части, левую — уже отсортированную, и правую — ещё нет.
Допустим, у нас есть все тот же массив [5, 2, 4, 1, 3]
- Шаг 1: ищем минимальный среди [5, 2, 4, 1, 3] → это 1, и ставим его на первое место, то есть меняем 1 и 5 → [1, 2, 4, 5, 3]
- Шаг 2: опять ищем минимальный среди уже оставшейся правой неотсортированной части [2, 4, 5, 3] → это 2. Он уже на месте, поэтому ничего не делаем
- Шаг 3: ищем минимальный среди [4, 5, 3] → это 3, ставим его на первое место неотсортированной части, то есть меняем 4 и 3 → [1, 2, 3, 5, 4]
- Шаг 4: ну и снова ищем минимальный среди [5, 4] → это 4, меняем 5 и 4 → [1, 2, 3, 4, 5]
Готово — массив отсортирован по возрастанию. Тут сложность все равно заключается в том, что каждый раз в правой неотсортированной части вам нужно будет делать «перебор» значений и искать минимальное. Но каждый раз уже в меньшем массиве, чем в предыдущий раз. Поэтому алгоритм также не эффективный, и подходит в основном для обучения.
Хотите знать больше? Читайте нас в нашем Telegram – там еще больше интересного: новинки гаджетов, технологии, AI, фишки программистов, примеры дизайна и маркетинга.
