В работе программиста важное значение занимаю две вещи: алгоритмы и данные, которые специалист видит на экране. Часто эта информация являет собою хаос, который профессионалу нужно упорядочить. Именно тут на помощь приходят алгоритмы сортировки. В этой статье я расскажу об этих структурах, опишу основные виды, приведу понятные примеры для понимания темы.
Место алгоритмов сортировки в программировании
Главные инструменты программистов – алгоритмы и команды – нацелены на выполнение различного рода задач. Они бывают легкие и сложные или простые и многокомпонентные. Большинство простых заданий программист может выполнить за короткий период времени, не прибегая при этом к специальным формулам или алгоритмам. Но бывают такие ситуации, когда решение задачи требует особого подхода. Под этим выражением я подразумеваю применение алгоритмов сортировки. Что же это такое?
Давайте рассмотрим эту тему на примере одной задачки.
Давайте представим, что у нас есть ряд повторяющихся слов.
Например: Красный, зеленый, красный, желтый, черный, желтый, белый, красный, синий, фиолетовый, зеленый, розовый, желтый, красный, белый, синий, фиолетовый, зеленый, розовый, желтый.
Наша основная задача: отсеять те слова, которые повторяются чаще, чем 2 раза.
Чтобы выполнить данную задачу с использованием классической методики, программисту пришлось бы писать сложный, многоступенчатый алгоритм. Проще всего упростить задачу отсортировав массив данных. Сделав это, мы увидим, что все одинаковые слова расположены рядом друг с другом. Этот факт очень сильно упрощает выполнение поставленного условия.
Белый, белый, желтый, желтый, желтый, желтый, зеленый, зеленый, зеленый, красный, красный, красный, красный, розовый, розовый, синий, синий, фиолетовый, фиолетовый, черный, черный.
Как видите, набор слов был отсортирован и выставлен в алфавитном порядке – от А до Я. С новым видом массива данных нам без труда удастся выполнить задачу.
Другой пример:
1,9,4,5,1,2,9,4,8,3,7,1,2,1,7,4,6,2,8,1,2,9,8,3,4,9.
Наша задача: определить какое количество цифр после 7 присутствует в массиве данных.
Применяем метод сортировки, только с условием «по убыванию» т.е. от большего числа к меньшему. Получим следующее:
9,9,9,9,8,8,8,7,7,6,5,4,4,4,4,3,3,2,2,2,2,1,1,1,1,1.
Согласитесь, теперь посчитать количество цифр после 7 стало намного проще.
Ключевое в этом примере то, что мы использовали возможность сортировки по убыванию. Например: при создании сайта с каталогом товаров на продажу, программист разрабатывая этот сайт будет применять именно этот вариант алгоритма, чтобы покупатели смогли отсортировать все товары и сразу перейти к самым дорогим, т.е. более качественным и брендовым.
Противоположным свойству убывая в алгоритмах сортировки служит вариант по возрастанию. Тут, думаю, все предельно ясно: от самого малого цифрового значения, до самого большого. Опять вернусь к примеру с интернет-магазином: используя рабочий алгоритм сортировки по возрастанию потенциальный клиент сможет сразу увидеть самые бюджетные товары, а значит отсеять те товары, которые клиент не намерен был покупать, т.е. дорогие
Основные способы сортировки
На данный момент существуют десятки различных алгоритмов сортирования, а с годами развития индустрии программирования конечное число вариантов только увеличится. Я же остановлюсь на главных видах этого алгоритма и объясню их работу используя понятные примеры.
Существует 6 главных вида алгоритма сортирования:
- Пузырьковая (Bubble sort).
- Вставками (Insertion sort).
- Шелла (Shell sort).
- Слияния (Merge sort).
- Выбора (Selection sort).
- Кучей (Heap sort).
- Быстрая (Quick sort).
Перед описанием каждого вида небольшая ремарка:
Каждый из рассмотренных вариантов алгоритмов сортирует исходный массив данных, переставляет символы местами и использует то пространство, которое было задействовано вместе с начальными данными.
Пузырьковая сортировка
Один из самых простых и понятных вариантов сортировки в программировании. Назвали так этот алгоритм из-за ассоциаций с шариками кислорода в воде Как известно, скопление воздуха на дне – небольшое, но чем выше поднимается шарик О2, тем больших объёмов он становиться. А теперь пример:
Представим, что левая сторона картинки – дно, а правая – водная поверхность. Самый большой шарик с самым большим цифровым значением постепенно движется в сторону водной поверхности, т.е. вправо.
Как вы могли догадаться, каждый новый горизонтальный ряд шариков – это визуализация очередного действия. Шарик с значением 10 может за одно действие совершить одно из двух движений – влево или вправо. Как видно на картинке, с каждым действием шарик с цифрой 10 движется направо. При этом шарик с каждым действием меняется местами с соседними элементами.
А теперь абстрагируемся от воздушных шариков в воде и посмотрим на изображение замечая только цифры. Перед нами массив данных – несколько рядов цифр. Допустим, наша задача поместить цифру 9 в последнем ряду после цифры 10, которая находиться сейчас в крайней правой позиции ряда. Чтобы выполнить эту задачу нам нужно прибегнуть к алгоритму сортировки, а именно к Пузырьковому виду. Сделав это, мы можем применить эту же формулу и на цифру 8, 7, 6 и так далее. Таким образом мы применим алгоритм сортировки ко всем элементам и выполним поставленную задачу, а именно – упорядочим данные в массиве.
Сортировка вставками
Данный вид сортировки похож, на предыдущий, отличие лишь в том, во время сортировки элементы сравниваются с предыдущими и располагаются в подходящей позиции. Смотрите пример:
Сортировка Шелла
Этот вид сортировки является улучшенной версией сортировки вставками. Сортировка Шелла позволяет перемещать не только элементы, которые находятся рядом, но и те, которые расположены на длительном расстоянии. Существует один только нюанс: перед каждым действием происходит проверка всех элементов с целью выявления подходящего для перестановки. Смотрите пример:
Сортировка слиянием
Сложноватый для новичков алгоритм, который чаще всего применяется для структурирования списков. В данном алгоритме доступна возможность слияния (отсюда и названия) меньший по величине данных с большими, чтобы в последствие первые переместить в нужную точку. Чтобы лучше разобраться смотрите графику:
Сортировка выбором
В данном варианте сортировочных алгоритмов основная функция немного отличается от предыдущей, но есть и схожести. Снова приведу иллюстрацию в качестве примера:
Чтобы понять происходящее на картинке, дам вам несколько ключей:
- Слева располагаются самые маленькие цифровые значения (полностью окрашен синим).
- По ходу каждого горизонтального ряда проходит проверка каждого цифрового значения (ободок круга окрашен зеленым, в случае 1 – красным).
- После прохождения проверки всего числового ряда, самая маленькая цифра перемещается в крайнюю левую точку.
Отличия от пузырькового вида в том, что обмен данными происходит всего единожды. Схожесть в том, что количество рядов (проверок) идентична пузырьковой сортировке. Из этого можно сделать вывод, что второй вид алгоритмов сортировки работает быстрее при одинаковом результате с первым вариантом сортировки.
Сортировка кучей
Основной механизм роботы данного вида алгоритмов сортировки заключается в проведении сравнении. Отличительная особенность этой сортировки проявляется в типе сортируемых данных: тут это бинарная куча (внешне похожа на молекулярные связи), а не линейная, как в прошлых вариантах. Данный алгоритм проводит сравнение всех элементов и сортирует их последовательно от маленького до великого. Выглядит это так:
Быстрая сортировка
Исходя из названия, можно предположить, что данный вид сортировки самый быстрый из трех представленных. Как не банально, но это так.
В этой сортировке происходит чередование не соседних элементов, а тех, которые находятся максимально друг от друга. Обратите внимание на пример:
Используя быстрою сортировку можно переместить минимальные данные в левую сторона, а максимальные – в правую. Но здесь я привел пример цифрового ряда, который упорядочен, просто лишь находиться в зеркальном положений. Как тогда использовать быструю сортировку в ситуации, когда все данные перемешаны?
Чтобы ответить на этот вопрос обращусь к самой структуре этого алгоритма. Она выглядит так:
- Происходит выбор одного опорного элемента из массива данных.
- Проводиться перемещение элементов таким образом, чтобы структуры меньше опорной помешались перед ним (слева), а те что больше или равные — за ним (справа).
Данный алгоритм применяется только в случае, если у массива больше одного элемента.
Чтобы закрепить знания, посмотрите на следующий график:
Задачи, приводящие к необходимости сортировки
Частичный ответ на данный пункт стати я уже рассматривал выше на примере с интернет магазином. При создании программ, программисту необходимо максимизировать производительность и минимизировать время, которое тратиться на выполнение поставленной задачи.
На примерах, которые я описал в статье, сортировка производилась чисел и слов, но ее также можно применить к любым данным, с которыми работает специалист. Простые примеры: онлайн-словари, в который все слова отсортированы в алфавитном порядке; телефонные книги, где номера также структурированы; различные каталоги с медиа-контентом (фильмы, сериалы, игры, музыка) распределены все также в алфавитном порядке. Подобная система очень выручает обычного пользователя.
Зачем же тогда использовать разные алгоритмы сортировки? Почему нельзя использовать какой-то один?
Дело в том, что каждый сортировочный алгоритм подходит под конкретную задачу.
Например сортировку слияния используют для структуризации связных списков. А вот для большого массива данных лучше подойдет быстрая сортировка, которая справляется с задачей эффективнее других видов алгоритмов.
Заключение
Алгоритмы сортировки занимают что ни на есть важное место в программировании. С помощью возможностей сортирования, программисту удаётся выполнить сложные задачи, тратя при этом меньше времени, чем используя стандартный алгоритм. Сортировка помогает упростить как работу по созданию продукта, так и непосредственное использование конечным потребителем.
