Файл: Методы сортировки данных: эволюция и сравнительный анализ. Примеры использования (Классификация алгоритмов сортировки).pdf

Введение

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

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

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

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

Хотя в настоящее время уже можно уверенно заявить, что все самые быстрые алгоритмы «общей» сортировки (то есть, такой сортировки, когда в массиве сортируемых данных, эти самые данные могут быть абсолютно любыми), уже придуманы, однако все более обостряется необходимость разработки алгоритмов «специализированной сортировки», то есть, сортировки, которую можно ускорить путем использования особенностей входных данных.

Самый простой пример такой сортировки – это сортировка сотовых телефонов сотрудников. Если телефоны представлены в виде строк вида «+79125748188», и мы уверены, что в нашей компании используются лишь телефоны из России (это «особенность входных данных»), то все наши телефоны будут иметь 12 символов, и начинаться на «+79». Следовательно, эти символы можно исключить из проведения сортировки, тем самым ее ускорив (оставим за скобками что в таком случае можно было бы просто не хранить эти символы в базе данных).

Из бумажных источников лучше всего методы сортировки описаны у Дональда Кнута в третьем томе его известной монографии «Искусство программирования» [3]. Кроме того, существует не менее известная книга [4], в которой также содержится много информации посвящено различным видам сортировок.

1. Классификация алгоритмов сортировки

Алгоритмы сортировки можно классифицировать по множеству критериев, самым очевидным из которых является быстрота выполнения сортировки [1].

Однако оценить быстроту алгоритма «непосредственно» (по времени выполнения на некотором наборе данных, или числу шагов) практически невозможно, так как различные алгоритмы могут иметь разную скорость работы в зависимости от исходных данных – например, один алгоритм может очень быстро работать в случае, когда данные «почти упорядочены», а другой наоборот – лучше приспособлен к очень перемешанным данным. Кроме того, алгоритмы могут выполняться на компьютерах с различной скоростью процессора и системой команд, что также влияет на быстроту их выполнения.

В связи с этим при оценке быстроты алгоритмов, как правило, используют лишь порядок времени выполнения. Порядок изображается как зависимость от исходного количества сортируемых величин. Например, порядок означает, что сортировка имеет квадратичную зависимость времени выполнения от количества сортируемых величин. То есть, если мы увеличим количество величин с 10 до 20 (в два раза), то время выполнения увеличится в раза. Очевидно, что алгоритмы с таким порядком выполнения не очень практичны для больших объемов данных, так как время выполнения увеличивается гораздо быстрее, чем объем исходных данных. Как правило, данные сортировки (а также сортировки с еще худшим порядком выполнения, таким как или даже ), применяются лишь в трех случаях:

1. Когда объем исходных данных настолько мал, что можно выбрать практически любой алгоритм сортировки, а более медленно работающий алгоритм оказывается проще реализовать;
2. Если данный алгоритм более понятен для понимания человеком, то можно применять его в целях обучения;
3. Данный алгоритм может быть придуман исключительно с целью показать его возможность, без оглядки на эффективность (такие алгоритмы описаны в пункте 5).

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

Кроме времени выполнения логично классифицировать алгоритмы по объему требуемой памяти (кроме, собственно, исходного массива с данными). Требования к дополнительной памяти невозможно описать в байтах, поэтому они, как и быстрота алгоритма, описываются асимптотически. Алгоритм, которому вообще не нужна дополнительная память классифицируется как , а алгоритм, которому нужна память порядка количества сортируемых величин можно обозначить как .

Еще одним критерием, по которому можно классифицировать алгоритмы, является их устойчивость. Довольно часто при сортировке элемент с одним и тем же значением, например, «5» может встретиться несколько раз (например, если это оценка студента). Если при сортировке алгоритм может поменять несколько таких элементов местами (что, в принципе, логично, так как одна пятерка ничем не лучше другой), то такой алгоритм называется «неустойчивым». С другой стороны, алгоритм, который никогда не меняет местами (не меняет порядок) элементов с одинаковыми значениями, называется «устойчивым». Устойчивость алгоритмов – это не всегда требуемое их свойство, однако иногда оно очень необходимо.

Как правило, устойчивые алгоритмы в каких-то своих характеристиках (например, по порядку времени выполнения, или объему необходимой памяти) уступают неустойчивым, однако если требование устойчивости необходимо, то следует использовать именно их.

2. Эволюция алгоритмов сортировки

Как было указано во введении, алгоритмы сортировки используются уже очень давно. Однако основные исследования в данной области начались с появлением ЭВМ. Уже в 1940-х годах выходят первые статьи об алгоритмах сортировки данных. Чаще всего в данное время данные сортировались слиянием или вставками. Оба данных алгоритма имеют сложность [2].

В следующих десятилетиях, в 50-70х годах, уже после того, как появились первые языки высокого уровня (такие как Фортран и Кобол), началось бурное развитие новых алгоритмов. Появляются такие алгоритмы, как Сортировка Шелла, Быстрая Сортировка и Пирамидальная Сортировка. Многие из разработанных тогда алгоритмов используются и поныне.

С 1970 по 1990 год происходит еще один всплеск интереса к различным методам сортировки, связанный с дальнейшим уменьшением размера ЭВМ, и началом использования в них БИС (больших интегральных схем). Хотя кардинально новых методов в данное время не появилось, однако возрос интерес к комбинированию старых методов и улучшению их производительности. Например, именно в это время появляется алгоритм Плавной Сортировки, который во многом похож на алгоритм Пирамидальной Сортировки, однако существенно его дополняет. Еще один такой алгоритм - TimSort, хотя и появился немного позже (в 2002 году), в настоящее время стал стандартом для реализации в библиотеках языков программирования – например, данный метод используется в языках Python и Java (в варианте OpenJDK) [6].

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

В дальнейшем, кроме обычной сортировки данных (путем помещения данных в массив, и его обработки) начала развиваться и сортировка данных, которые имеют некоторые особенности. Основных «особенностей» здесь можно выделить две – сортировка данных, не входящих в оперативную память компьютера (очень больших объемов данных, например, в базах данных, хранящихся на жестком диске, например [8]), и сортировка данных, не являющихся независимыми друг от друга.

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

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

3. Алгоритмы неустойчивой сортировки

Рассмотрим чаще всего используемые алгоритмы неустойчивой сортировки. Для каждого из них укажем порядок скорости, а также потребляемой памяти:

• Сортировка выбором (скорость , память );
• Сортировка Шелла (скорость от до , память );
• Быстрая сортировка (скорость от до , память );
• Пирамидальная сортировка (скорость , память );

Рассмотрим каждый из этих методов сортировки подробнее:

3.1 Сортировка выбором

Сортировка выбором является самым простым вариантом сортировки массива. Допустим, наш массив должен быть упорядочен по возрастанию. Это означает, что первым в нем должен оказаться минимальный элемент. Мы можем довольно просто его найти – нужно один раз пробежать по массиву – для этого нужно времени. После того, как мы нашли минимальный элемент, мы можем просто обменять его местами с первым элементом (либо оставить на месте, если первый элемент и оказался минимальным).

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