Но как мы на самом деле реализуем алгоритмы сортировки — используя визуальное представление?
Алгоритмы сортировки принимают списки элементов в качестве входных данных, выполняют определенные операции над этими списками и выдают упорядоченные массивы в качестве выходных данных.
Алгоритмы сортировки могут быть сложными для понимания, и в них легко запутаться. Визуализация алгоритмов сортировки может быть отличным способом лучше понять их работу, развлекаясь.
Зачем вообще нужна сортировка?
Эффективная сортировка важна для канонизации данных и создания удобочитаемого вывода. Кроме того, это важно для оптимизации эффективности других алгоритмов, которые требуют, чтобы входные данные находились в отсортированных списках.
Найти элементы в отсортированном списке проще и быстрее, чем в несортированном. Алгоритмы сортировки можно использовать в программе для сортировки массива для последующего поиска или записи в упорядоченный файл или отчет. При работе с исследовательскими данными сортировка является распространенным методом, используемым для визуализации данных в форме, облегчающей понимание истории, которую рассказывают данные.
Рассмотрим несколько алгоритмов сортировки.
Пузырьковая сортировка
Bubble Sort — это итеративный алгоритм сортировки, имитирующий движение пузырьков в газированной воде. Пузырьки представляют собой элементы структуры данных.
На практике более крупные пузыри достигают вершины быстрее, чем более мелкие, и этот алгоритм работает точно так же. Он перебирает структуру данных и для каждого цикла сравнивает текущий элемент со следующим и меняет их местами, если они находятся в неправильном порядке.
Давайте посмотрим на сложность пузырьковой сортировки.
Сложность в лучшем случае: O(n)
Сложность в наихудшем случае: O(n2)
Средняя сложность случая: O(n2)
Сложность пространства: O(1)
Основным недостатком этого метода сортировки является то, что он требует много времени из-за наихудшего случая O(n2). Таким образом, его можно использовать только для небольшого набора данных и только тогда, когда нам требуется несколько свопов.
Пузырьковая сортировка — простой в реализации алгоритм, но не очень эффективный в реальных сценариях.
Сортировка вставками
Сортировка вставками — это простой алгоритм сортировки, который строит окончательный отсортированный массив по одному элементу за раз.
Алгоритм делит структуру данных на два подсписка: отсортированный и (n-1) набор элементов, которые еще предстоит отсортировать. Первоначально отсортированный подсписок состоит только из одного элемента и постепенно заполняется. Для каждой итерации алгоритм выбирает элемент в несортированном подсписке и вставляет его в нужное место в отсортированном подсписке.
Давайте посмотрим на сложность сортировки вставками.
Сложность в лучшем случае: O(n)
Сложность в наихудшем случае: O(n2)
Средняя сложность случая: O(n2)
Сложность пространства: O(1)
Средняя сложность O(n2), производительность прямо пропорциональна квадрату введенных данных. Проще говоря, время, необходимое для выполнения, будет в квадрате умножаться на размер ввода.
Его действительно легко реализовать, и он эффективен только для небольших структур данных, которые почти отсортированы.
Сортировка выбором
Сортировка выбором — это итеративный алгоритм сортировки на месте, который делит структуру данных на два подсписка: упорядоченный и неупорядоченный.
Алгоритм сортировки выбором сортирует массив, многократно находя минимальный элемент из неупорядоченной части и помещая его в начало. На каждой итерации сортировки выбором минимальный элемент из неупорядоченного подмассива выбирается и перемещается в упорядоченный подсписок.
Давайте посмотрим на сложность сортировки выбором.
Сложность в лучшем случае: O(n2)
Сложность в наихудшем случае: O(n2)
Средняя сложность случая: O(n2)
Сложность пространства: O(1)
Основное преимущество сортировки выбором заключается в том, что она хорошо работает в небольшом списке. Кроме того, не требуется никакого дополнительного временного хранилища помимо того, что необходимо для хранения исходного списка.
Он сохраняет первый k наименьших элементов в своих первых k итерациях. Таким образом, вам не нужно сортировать все данные, чтобы получить первые k-е отсортированные данные.
Сортировка слиянием
Сортировка слиянием — это алгоритм сортировки, основанный на методе «разделяй и властвуй». По сути, он делит данные на разные группы, сортирует данные по группам и объединяет их для получения полных отсортированных данных.
На первом этапе список разбивается до тех пор, пока он не образует отдельные элементы, называемые подсписками. После этого начинается этап «слияния». Здесь подсписки объединены в пары и расположены в соответствии с указанным порядком. Эти парные списки снова объединяются в пары для формирования групп и снова располагаются в соответствии с предполагаемым порядком. Этот процесс происходит до тех пор, пока подсписки не образуют один список.
Давайте посмотрим на сложность сортировки слиянием.
Сложность в лучшем случае: O(nxlogn)
Сложность в наихудшем случае: O(nxlogn)
Средняя сложность обращения: O(nxlogn)
Пространственная сложность: O(n)
Сложность O(nxlogn) обозначает логарифмическое время, которое делает этот метод сортировки быстрее, чем другой. Но из-за пространственной сложности O(n) требуется больше места.
Он отлично подходит для больших наборов данных благодаря низкой временной сложности. Но для этого требуется как минимум в два раза больше памяти, чем для других типов.
Сортировка кучей
Heap Sort — это итеративный алгоритм сортировки на месте, основанный на вспомогательных структурах данных, называемых кучей.
Кучевую сортировку можно рассматривать как улучшенную сортировку выбором. Подобно сортировке выбором, пирамидальная сортировка делит входные данные на отсортированную и несортированную области и итеративно сжимает несортированную область, извлекая из нее самый большой элемент и вставляя его в отсортированную область.
Сортировка кучей работает путем преобразования списка элементов, подлежащих сортировке, в структуру данных кучи, то есть двоичное дерево со свойствами кучи. В бинарном дереве каждый узел имеет не более двух потомков. Узел обладает свойством кучи, если ни один из его потомков не имеет больших значений, чем он сам. Самый большой элемент кучи удаляется и вставляется в отсортированный список. Оставшееся поддерево снова превращается в кучу. Этот процесс повторяется до тех пор, пока не останется ни одного элемента.
Давайте посмотрим на сложность сортировки кучи.
Сложность в лучшем случае: O(nxlogn)
Сложность в наихудшем случае: O(nxlogn)
Средняя сложность обращения: O(nxlogn)
Сложность пространства: O(1)
В то время как другие алгоритмы сортировки могут расти экспоненциально медленнее по мере увеличения количества сортируемых элементов, время, необходимое для выполнения сортировки кучи, увеличивается логарифмически. Это говорит о том, что Heap sort особенно подходит для сортировки огромного набора данных.
Алгоритм сортировки кучи широко используется из-за его эффективности.
Быстрая сортировка
Быстрая сортировка — это алгоритм сортировки, основанный на разделении структуры данных на более мелкие разделы и их рекурсивной сортировке до тех пор, пока структура данных не будет отсортирована.
Это деление на разделы осуществляется на основе одного элемента, называемого стержнем. Все элементы, большие, чем стержень, размещаются с правой стороны конструкции, а меньшие — с левой. Это происходит рекурсивно для двух разделов и так далее.
Этот метод разделения, основанный на опорной точке, называется «разделяй и властвуй».
Давайте посмотрим на сложность быстрой сортировки.
Сложность в лучшем случае: O(nxlogn)
Сложность в наихудшем случае: O(nxlogn)
Средняя сложность случая: O(n2)
Пространственная сложность: O(n)
Он имеет эффективный средний случай по сравнению с любым другим алгоритмом сортировки. Но это не стабильный сорт. Это означает, что порядок равных элементов может не сохраняться.
Быстрая сортировка – один из самых эффективных алгоритмов сортировки, поэтому он также является одним из наиболее часто используемых.
Визуализация алгоритмов.
Визуализатор в основном играет с цветами, чтобы лучше понять, что происходит в алгоритме. Данные здесь представляют собой бары, которые генерируются случайным образом с произвольной высотой.
Когда алгоритм работает, эти полосы или сегменты меняют цвет на три разных цвета — желтый, красный и зеленый, каждый из которых выполняет свою функцию.
Желтый сегмент означает, что алгоритм смотрит на этот конкретный сегмент. Если он меняет определенный сегмент, он будет помечен красным. Если конечная позиция сегмента находится там, где он сейчас находится в отсортированном положении, он будет отмечен зеленым цветом.
После запуска алгоритм отключает все кнопки, чтобы сортировка могла выполняться непрерывно. Цвет и высота соответственно изменяются во время работы алгоритма.
Факторы, которые необходимо учитывать при выборе эффективного алгоритма сортировки.
Знайте, какой алгоритм сортировки соответствует вашей проблемной области.
Благодаря развитию новых технологий и постоянно генерируемым огромным объемам данных всегда существует потребность в более быстрых и эффективных алгоритмах сортировки. Если вы посмотрите на алгоритмы сортировки, вы будете поражены огромным количеством используемых алгоритмов. Но не менее важно выяснить, какой алгоритм лучше всего подходит для ваших данных.
Чтобы выбрать подходящий алгоритм для разных данных, вам нужно знать некоторые свойства ваших входных данных. Основные факторы, которые следует учитывать при выборе алгоритма сортировки в соответствии с вашими потребностями:
Размер данных. Какой объем данных вы собираетесь сортировать? Это поможет вам узнать, нужно ли вам искать алгоритм с очень низкой временной сложностью. Для небольшого набора данных лучше всего подходят пузырьковая сортировка, сортировка вставками и сортировка выбором. При работе с большим набором данных рассмотрите возможность использования слияния, кучи и быстрой сортировки.
Случайность данных. Насколько уже будут отсортированы ваши данные? Будет ли он частично отсортирован? Случайно отсортировано? Это может повлиять на временную сложность алгоритма сортировки. У большинства алгоритмов будут наихудшие и наилучшие случаи — вам нужно убедиться, что вы не используете алгоритм на наборе данных для наихудшего случая.
Пространственная и временная сложность. Любой дизайн алгоритма часто представляет собой компромисс между временем и пространством, алгоритмы с низкой пространственной сложностью могут потребовать больше времени, а алгоритмы с низкой временной сложностью могут потребовать больше места. Временная сложность описывает, как производительность алгоритма меняется по мере увеличения размера набора данных с точки зрения времени. Сложность пространства описывает, сколько места требуется для работы алгоритма.
Стабильность: сохранение относительного порядка равных элементов, присутствующих в моих входных данных. Если для вас важен относительный порядок, вы можете поискать стабильный алгоритм.
«Сортировать то, что вы никогда не будете искать, — пустая трата времени; искать то, что вы никогда не сортировали, просто неэффективно».
