Алгоритмы

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

Так как в задачах поиска операцию сортировки приходится выполнять многократно для очень больших объёмов данных, то критическое значение имеет время сортировки. Поэтому эффективность алгоритма сортировки имеет очень важное значение. Разработано множество алгоритмов сортировки, отличающихся эффективностью в тех или иных наборах данных.

Сортировка данных - это процесс перегруппировки заданного множества объектов в некотором определенном порядке в соответствие с заданным критерием.

Цель сортировки - облегчить последующий поиск элементов в отсортированном множестве.

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

В общем случае методы сортировки разбиваются на 2 класса: сортировка массивов и сортировка последовательностей.

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

Мера эффективности сортировки:

С - число сравнений,

М - число перестановок.

Они являются функциями C = C(n) и M = M(n), где n – число сортируемых элементов.

Сортировка пузырьком - самый естественный, он же самый медленный алгоритм сортировки. Массив чисел просматривается от начала до конца до тех пор, пока любые два рядом стоящих числа не будут расположены по возрастанию. Для этого два неверно расположенные одно относительно другого числа меняются местами. При этом наименьшее число, как пузырёк, постепенно всплывает к началу массива (а наибольшее сразу " тонет" как камень!), отсюда и название алгоритма. Время сортировки пузырьком растёт пропорционально квадрату роста количества элементов в массиве.

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

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

МЕТОДЫ И АЛГОРИТМЫ СОРТИРОВКИ МАССИВОВ

В общем случае “Быстрая сортировка” является самым быстрым алгоритмом. Благодаря своей эффективности, равной O(n log2n), он явно превосходит любой алгоритм порядка O(n2). Судя по результатам испытаний, приведенных в следующей таблице, он также быстрее любой из сортировок порядка O(n log2n), рассмотренных нами в прошлом номере. Обратите внимание, что эффективность «быстрой» сортировки составляет O(n log2n) даже в экстремальных случаях. Зато сортировка посредством поискового дерева становится в этих случаях O(n2) сложной, так как формируемое дерево является вырожденным.

Сначала необходимо задать количество элементов в массиве, и нажать кнопку " Заполнить". Таблица заполняется случайными числами в диапазоне 0 - 999 999.. Можно также загрузить массив из файла, или выгрузить готовый массив в файл (однако массив из более чем 540 000 элементов загрузить не удаётся...). Далее можно выбрать желаемый метод сортировки, затем нажать кнопку " Сортировать".

Во время сортировки продолжительность в секундах отображается в заголовке окна

Предупреждаю, что выбрав для сортировки миллиона чисел метод пузырька, окончания процесса можно не дождаться – > > 54 минуты! Что касается сортировки вставкой, то миллион чисел она сортировала 17 минут! Алгоритм сортировки вставками, ищущая место вставок с помощью метода половинного деления, сокращает время сортировки до 7 минут.