Преподаватель который помогает студентам и школьникам в учёбе.

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

Содержание:

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Данный тип сортировки не требует дополнительной памяти, кроме самого массива, поэтому его сложность по памяти равна .

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

3.2 Сортировка Шелла

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

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

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

Именно она позволяет добиться скорости выполнения порядка . Выбрав другое количество и размер отрезков можно получить другую асимптотическую скорость выполнения.

Например, если в массиве 14 объектов (), согласно вышеприведенной формуле, мы выбираем следующие проходы ():

Проход каждые 6 единиц ();
Проход каждые 3 единицы ();
Проход каждые 2 единицы ();
Проход каждую единицу (), обычная сортировка вставками;

Покажем выполнение такой сортировки на примере массива из четырнадцати элементов (33,95,16,82,24,65,35,19,74,55,39,44,94,67).

Вначале мы сортируем подмассивы с шагом шесть. Таких подмассивов будет также шесть – (33,35,94), (95,19,67), (16,74), (82,55), (24,39), (65,44). Для сортировки данных подмассивов понадобится четыре перестановки (две для второго подмассива, одна для четвертого и одна для шестого). В итоге мы получим подмассивы (33,35,94), (19,67,95), (16,74), (55,82), (24,39), (44,65). Вновь объединим их, и получим массив: (33,19,16,55,24,44,35,67,74,82,39,65,94,95).

Теперь сортируем массивы с шагом три. Таких подмассивов будет также три – (33,55,35,82,94), (19,24,67,39,95), (16,44,74,65). Для сортировки данных подмассивов понадобится три перестановки (одна для первого подмассива, одна для второго и одна для третьего). В итоге мы получим подмассивы (33,35,55,82,94), (19,24,39,67,95), (16,44,65,74). Вновь объединим их, и получим массив: (33,19,16,35,24,44,55,39,65,82,67,74,94,95).

Теперь сортируем массивы с шагом два. Таких подмассивов будет также два – (33,16,24,55,65,67,94), (19,35,44,39,82,74,95). Для сортировки данных подмассивов понадобится четыре перестановки (две для первого подмассива, и две для второго). В итоге мы получим подмассивы (16,24,33,55,65,67,94), (19,35,39,44,74,82,95). Вновь объединим их, и получим массив: (16,19,24,35,33,39,55,44,65,74,82,95).

Наконец отсортируем наш массив с шагом 1, обычной сортировкой вставками. Получим массив (16,19,24,33,35,39,44,55,65,74,82,95) за две перестановки.

Итого, нам понабилось сделать перестановок. Если бы мы сортировали обычными вставками, то на весь процесс ушло бы около 40 перестановок. Наш метод позволил выполнить сортировку практически в три раза быстрее.

Однако в итоге, несмотря на то, что метод, как правило, работает быстрее чем обычная сортировка вставками, он потерял свойство устойчивости. В самом деле, теперь одинаковые значения массива могут попасть в разные «подмассивы», и сортироваться по отдельности. В результате, они вполне могут оказаться поменянными местами. Однако если требования устойчивости не стоит, данным методом вполне можно пользоваться.

3.3 Быстрая сортировка

Быстрая сортировка является, наверное, самой часто используемой сортировкой, так как, с одной стороны, является достаточно быстрой, а с другой – имеет реализацию в стандартной библиотеке практически любого языка программирования.

Процесс быстрой сортировки состоит из трех шагов.

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

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

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

3.4 Пирамидальная сортировка

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

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

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

После того, как мы переставили элементы исходного массива таким образом, чтобы они образовали бинарное сортирующее дерево, в его корне мы получаем самое маленькое, или наоборот, самое большое значение исходного массива. Мы можем просто взять его, и обменять с последним элементом. Тогда (при условии, что исходно в массиве было элементов), мы получим один (последний) отсортированный элемент, и элементов, которые «почти» образуют бинарное сортирующее дерево. Оно подходит всем условиям для того, чтобы являться таким деревом кроме одного – в его корне стоит элемент, который ранее находился последним, а не то, которое требуется согласно пункту 3. Поэтому бинарному дереву будет требоваться «перебалансировка» - его упорядочивание, достигаемое путем перемещения корневого элемента в нужное место. Эта перебалансировка можно быть выполнена за шагов, то есть, является довольно быстрой. После выполнения перебалансировки можно повторить данный алгоритм, получив еще один элемент отсортированного массива. Повторив данный алгоритм раз, мы получим полностью отсортированный массив.

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

Из-за достоинств данного алгоритма (быстрота и отсутствие необходимости в дополнительной памяти), он довольно широко применяется. Например, можно отметить применение его в ядре операционной системы Linux [9]

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

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

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

Однако иногда данные гарантии необходимы, и приходится использовать именно устойчивую сортировку. Например, у нас есть массив, в который мы записываем ФИО участника, а также количество задач, которые он решил на некоторой олимпиаде. Как только какой-либо участник решал очередную задачу, его данные заносились в этот массив (либо, если он уже там присутствовал, то данные о нем удалялись, и заносились снова с увеличенным количеством решенных им задач). Теперь, если мы отсортируем данный массив по количеству решенных задач (например, желая определить первые три места для награждения), может получиться так, что несколько первых мест (скажем, пять) решат одинаковое количество задач (допустим, все, которые были на олимпиаде). В таком случае, как правило, первое место отдают тому участнику, который решил задачи быстрее всех (то есть, участнику, которого внесли в массив быстрее других, который имеет в нем меньший номер). Если бы сортировка была неустойчивой, то в данном случае первые пять мест могли бы перепутаться как угодно. Хотя, конечно, все эти пять мест решили одинаковое количество задач, тем не менее, согласно регламенту соревнования, их нужно различать.

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

Сортировка пузырьком (скорость , память );
Сортировка перемешиванием (скорость , память );
Сортировка вставками (скорость , память );
Сортировка слиянием (скорость , память );
Метод TimSort (скорость , память ).

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

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

4.1 Сортировка пузырьком

Алгоритм сортировки пузырьком (или пузырьковой сортировки) состоит в повторяющихся проходах по массиву. Если размер массива, который необходимо отсортировать составляет элементов, то по массиву необходимо пройти раз.

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

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

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

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

4.2 Сортировка перемешиванием

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

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

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

4.3 Сортировка вставками

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

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

Отобразим действие данного вида сортировки на примере. Допустим, у нас есть массив из четырех элементов 1-5-3-2. Попробуем его отсортировать.

Шаг №1. Работаем с первым элементом массива «1». Так как других элементов пока нет, оставим его на своем месте;
Шаг №2. Работаем со вторым элементом массива «5». Он больше чем уже отсортированный массив «1», поэтому также оставим его на своем месте;
Шаг №3. Работаем с третьим элементом массива «3». Он меньше, чем последний элемент уже отсортированного массива «1-5», поэтому сдвигаем его влево. Теперь первые три элемента массива «1-3-5»:
Все еще работаем с третьим (теперь уже вторым) элементом массива «3». Это значение больше чем следующее в отсортированном
массиве – «1», поэтому оставляем его на своем месте;
Шаг №4. Работаем с четвертым элементом массива «2». Он меньше, чем последний элемент уже отсортированного массива «1-3-5», поэтому сдвигаем его влево. Теперь первые четыре элемента массива «1-3-2-5»:
Все еще работаем с четвертым (теперь уже третьим) элементом массива «2». Это значение все еще больше чем следующее в отсортированном массиве – «3», поэтому снова сдвигаем его влево. Теперь первые четыре элемента массива «1-2-3-5»;
Все еще работаем с четвертым (теперь уже вторым) элементом массива «2». Это значение больше чем следующее в отсортированном
массиве – «1», поэтому оставляем его на своем месте.
Мы взяли все элементы с первого до четвертого, поэтому массив отсортирован. Действительно, «1-2-3-5» это числа, расположенные по возрастанию.

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

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

4.4 Сортировка слиянием

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

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

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

Рассмотрим реализацию данного алгоритма на примере. Допустим, у нас есть массив из восьми (степень двойки) элементов, равных
«6-5-3-1-8-7-2-4». Необходимо отсортировать данный массив по возрастанию.

Шаг №1. Делим данную последовательность на две равных
части – «6-5-3-1» и «8-7-2-4». Вызываем для первой части «6-5-3-1» ту же процедуру сортировки.

Шаг №1.1. Делим данную нам последовательность «6-5-3-1» на две равных части – «6-5» и «3-1». Вызываем для первой части «6-5» ту же процедуру сортировки;

Шаг №1.1.1. Так как в переданной нам последовательности всего два члена - «6-5», сравним их, и обменяем местами – «5-6»;

Шаг №1.2. Вызовем для второй части «3-1» ту же процедуру сортировки;

Шаг №1.2.1. Так как в переданной нам последовательности всего два члена - «3-1», сравним их, и обменяем местами – «1-3»;

Шаг №1.3. Мы получили две отсортированных последовательности – «5-6» и «1-3». Объединим их в одну последовательность. Поставим указатели на первые элементы каждой из последовательностей – «5» и «1». Сравним их. Очевидно, что 1 меньше, чем 5, поэтому возьмем элемент «1» из второй последовательности. Сдвинем указатель. Теперь у нас две последовательности – «5-6» и «3», и результирующий массив «1». Точно также добавим остальные элементы в порядке возрастания, и получим массив «1-3-5-6»;

Шаг №2. Вызовем для второй части «8-7-2-4» ту же процедуру сортировки;

Шаг №2.1. Делим данную нам последовательность «8-7-2-4» на две равных части – «8-7» и «2-4». Вызываем для первой части «8-7» ту же процедуру сортировки;

Шаг №2.1.1. Так как в переданной нам последовательности всего два члена - «8-7», сравним их, и обменяем местами – «7-8»;

Шаг №2.2. Вызовем для второй части «2-4» ту же процедуру сортировки;

Шаг №2.2.1. Так как в переданной нам последовательности всего два члена - «2-4», сравним их. Они находятся в нужном порядке, поэтому не будем их трогать;

Шаг №2.3. Мы получили две отсортированных последовательности – «7-8» и «2-4». Объединим их в одну последовательность, как и ранее, используя указатели. В итоге получим массив «2-4-7-8»;

Шаг №3. Мы получили две отсортированных
последовательности – «1-3-5-6» и «2-4-7-8». Объединим их в одну последовательность, как и ранее, используя указатели. В итоге получим массив «1-2-3-4-5-6-7-8». Массив отсортирован.

Как можно видеть, сортировка слиянием действительно позволяет отсортировать массив, причем делает это гораздо быстрее (асимптотически), чем сортировки пузырька, или вставки. Из-за этого данная сортировка используется в реальных программных продуктах, например, в базе данных MySQL для реализации сортировки (при указании ORDER BY в запросе и отсутствии необходимых индексов).

Недостатки данного алгоритма следующие:

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

4.5 Метод сортировки TimSort

Метод TimSort не является «самостоятельным» методом сортировки. Вместо этого он пытается соединить положительные стороны двух методов – сортировки вставками и сортировки слиянием, которые были рассмотрены ранее.

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

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

Перечислим шаги, которые необходимо выполнить для реализации метода.

Вначале определяется минимальный размер «подмассивов», на которые мы будем делить исходный массив. С одной стороны, он не должен быть очень маленьким, иначе придется слишком долго сливать их на последнем шаге. С другой стороны, он не должен быть очень большим, так как мы будем сортировать его методом вставок, а он работает медленно на больших массивах. Были проведены эксперименты, и определено, что лучше всего выбирать значения в диапазоне от 32 до 65. Это число – параметр алгоритма, его можно либо задать в коде, либо каким-то образом определить на основе исходных данных. Обозначим это число как NUM.

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

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

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

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

Из-за того, что алгоритм работает довольно быстро, он начал использоваться во многих серьезных программных продуктах, таких как Python, Java [6] и Android [7].

Однако данный алгоритм обладает тем недостатком, что он довольно сложен, и в его реализации очень легко допустить ошибку, а так как он используется во многих программных продуктах, то речь будет идти о миллиардах пользователей по всему миру. Сам алгоритм был разработан Тимом Петерсом (в честь него он и был назван TimSort) в 2002 году, но в его реализации была допущена досадная ошибка, приводящая к его некорректной работе на специально подобранных входных данных.

Из-за сложности алгоритма, сама ошибка оставалась незамеченной в течение целых 13 лет – с 2002 по 2015 год, причем даже в 2015 году она была найдена не людьми. Было решено использовать специальную программу KeY, чтобы доказать корректность некоторых алгоритмов (в том числе сортировки) формально (то есть, математически строго). Была доказана корректность двух более медленных алгоритмов, но программа так и не смогла доказать корректность алгоритма TimSort. Этим заинтересовались авторы данной программы, и выяснили, что действительно, в реализации данного алгоритма была допущена ошибка [5].

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

5. Непрактичные алгоритмы сортировки

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

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

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

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

Работу данного алгоритма можно описать следующим образом (считается, что мы пытаемся отсортировать массив по возрастанию значений элементов):

Если в конце списка значение элемента меньше, чем в начале, то поменять первый и последний элементы местами;
Если в сортируемом списке есть хотя бы три элемента, то выполнить следующие три шага, если нет – то сортировка окончена:
- Рекурсивно вызвать процесс сортировки для первых списка;
- Рекурсивно вызвать процесс сортировки для последних списка;
- Снова рекурсивно вызвать процесс сортировки для первых списка.

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

6. Алгоритмы сортировки, не основанные на сравнениях

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

Первым представителем такого вида сортировок можно назвать блочную сортировку. Данная сортировка, прежде чем непосредственно сортировать элементы массива, делит их на несколько корзин (bucket’ов), например, на десять. Если у нас в массиве находятся числа от 0 до 1000, то в первой корзине будут находиться числа от 0 до 100, во второй – от 100 до 200, и так далее. Данное деление можно сделать за время порядка - просто пробежав по массиву от начала до конца. Затем, когда элементы разложены по корзинам, происходит сортировка каждой корзины. При этом используется любой вид сортировки – либо какой-то стандартный, либо блочная сортировка вызывается рекурсивно. После того, как каждая корзина отсортирована, происходит объединение всех элементов в один большой массив. Так как значения каждой корзины располагаются строго друг за другом, то получить итоговый массив можно последовательно объединив корзины.

В чем смысл деления исходного массива на корзины? Дело в том, что алгоритма сортировки любого массива с асимптотическим временем до сих пор не найдено. Следовательно, в любом случае, скорость сортировки массива падает быстрее, чем растет число его элементов. Например, мы сортируем некоторый массив за 10 секунд. Затем мы увеличиваем число элементов массива в 10 раз, но время исполнения увеличится больше чем в десять раз (зависит от алгоритма, но для примера допустим, что в 20 раз, то есть, нам потребуется 200 секунд). Однако если же мы, как и раньше, увеличим размер массива в десять раз, а затем раскидаем данные по десяти корзинам, то каждую из них, как и раньше, можно будет отсортировать за 10 секунд. Итого нам понадобится секунд, что в два раза меньше. Однако тут следует учесть, что на раскладывание данных по корзинам и обратную сборку также требуется время, поэтому итоговое время будет зависеть от числа корзин и распределения исходных данных.

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

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

В случае если в нашем массиве есть лишь N различных элементов, необходимо каким-то способом их пронумеровать от 1 до N (в случае с оценками это делается элементарно – оценки сами представляют собой последовательность от 1 до 5). Далее необходимо создать массив размера N, который заполнить нулями. После этого необходимо пробежать от начала массива до конца (это займет времени), и для каждого найденного значения увеличить значение нужной ячейки только что созданного массива. Например, если выясняется, что ученик получил четвертку, то необходимо увеличить четвертый элемент массива (итоговое количество полученных четверок).

После обхода всего исходного массива мы получим число вхождений каждого из элементов в массив. Затем следует лишь записать в исходный массив нужное количество элементов каждого вида. Например, если выяснилось, что из десяти полученных учеником оценок 2 двойки, 3 тройки, 4 четверки и одна пятерка, то можно просто переписать исходный массив как «2-2-3-3-3-4-4-4-4-5».

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

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

7. Параллельный алгоритм сортировки

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

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

Чтобы понять принцип работы алгоритма, нужно вспомнить, что при классической сортировке слиянием мы делим массив на две половины, каждую из которых сортируем отдельно. В нашем случае мы поступаем точно также, однако делим массив не на две части по количеству элементов, а следующим образом – «нечетные элементы (1-й, 3-й, 5-й, и т.д.) направляются в первую половину некоего временного массива, а четные элементы (2-й, 4-й, 6-й, и т.д.) направляются во вторую половину некоего временного массива». Далее, как и в случае сортировки слиянием, каждую из половинок нужно отсортировать отдельно – как правило, это делается вызовом нашей же сортировки рекурсивно (обратим внимание, что здесь мы и получаем выигрыш в параллельном выполнении, так как каждую половинку можно сортировать параллельно, на своем ядре процессора). Затем, после того, как обе половинки окажутся отсортированными, необходимо их объединить. Это происходит следующим образом – берутся соответствующие элементы из каждой половинки (1-е, 2-е, 3-е, и т.д.), и в зависимости от их значений выстраиваются на четные и нечетные места итогового массива.

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

Добавить в массив необходимое число незначащих элементов, чтобы его размер стал степенью двойки. При сортировке по возрастанию можно добавить необходимое число элементов, больше максимального, которые потом убрать;
Вспомнить, что любое число можно представить как сумму степеней двойки. Например, если у нас в массиве 112 элементов, то 112 можно представить как 64+32+16. Таким образом, мы можем отсортировать первые 64 элемента, затем следующие 32, и конечные 16. В итоге нам нужно будет объединить эти три массива.

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

Для данного алгоритма в [10] были проведены замеры скорости. Тестировались случайные данные различной длины (от 100 до 1.000.000.000 элементов массива, являющихся беззнаковыми целыми числами). Сам алгоритм выполнялся на различном числе потоков (от 4 до 16) на 8-ядерном компьютере Intel Core i7-3770 (4 физических ядра, и 8 виртуальных). Результаты исследования приведены ниже:

Таблица 1

Число элементов	Быстрая сортировка, секунд	Бэтчер, 4 потока, секунд	Бэтчер, 8 потоков, секунд	Бэтчер, 16 потоков, секунд
100	0,000000	0,000038	0,000580	0,005325
10.000	0,002000	0,000453	0,000769	0,005556
1.000.000	0,162000	0,048263	0,046195	0,046001
100.000.000	15,365000	4,462410	2,883859	3,016563
1.000.000.000	-	-	1224,588937	1384,172118

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

Если число элементов невелико, то параллельная сортировка выполняется хуже обычной быстрой сортировки;
При увеличении числа элементов, параллельная сортировка становится быстрее классической, причем чем больше элементов сортируется, тем на большее число потоков лучшее ее делить;
Попытка использовать больше потоков (16), чем есть ядер в системе (8) приводит лишь к ухудшению временных характеристик (хотя и не очень сильных).

Заключение

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

Однако уже сейчас можно понять, что идеального метода сортировки не существует. Каждый из них (кроме тех, что описаны как непрактичные) имеет свои области применения. Даже медленные алгоритмы вроде сортировки пузырьком могут служить в качестве учебного пособия при обучении по данной теме. Хотя основные методы сортировки были изобретены довольно давно, но нельзя сказать, что данная область остановилась в развитии. Во-первых, иногда (хотя и не так быстро, как раньше) все еще появляются новые методы – например, TimSort в 2002 году. Кроме того, проводятся исследования относительно того, какие алгоритмы сортировки лучше всего можно распараллелить на несколько ядер или процессоров.

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

Список использованных источников

Бумажные источники

Дупленко А. Сравнительный анализ алгоритмов сортировки данных в массивах. – Молодой Ученый, №8, 2013, часть 1, с. 50-53
Дупленко А. Эволюция способов и алгоритмов сортировки данных в массивах. – Молодой Ученый, №9, 2013, часть 1, с. 17-19
Кнут Д. Искусство программирования. Том 3. Сортировка и поиск. – М.: Издательский дом «Вильямс», 2019. – 832 с.
Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. – М.: Издательский дом «Вильямс», 2013, 1328 с.

Электронные источники

Stijn de Gouw Proving that Android’s, Java’s and Python’s sorting algorithm is broken (and showing how to fix it) – [электронный ресурс] - http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/
Замена сортировки слиянием на сортировку TimSort в исходном коде языка Java в 2009 году – [электронный ресурс] - https://www.webcitation.org/6AQdENbYS?url=http://hg.openjdk.java.net/
jdk7/tl/jdk/rev/bfd7abda8f79
Использование сортировки TimSort в операционной системе Android версии 6.0.1 – [электронный ресурс] - https://android.googlesource
.com/platform/libcore/+/android-6.0.1_r77/luni/src/main/java/java/util/
TimSort.java
Исходный код функции filesort в коде базы данных MySQL, использующий внешнюю сортировку на диске – [электронный ресурс] - https://github.com/mysql/mysql-server/blob/4869291f7ee258e136ef03f5
a50135fe7329ffb9/sql/filesort.cc
Исходный код функции sort в ядре Linux, использующий пирамидальную сортировку – [электронный ресурс] - https://github.com/torvalds/linux/blob/8a72f3820c4d14b27ad5336aed00063a7a7f1bef/lib/sort.c
Сеть обменной сортировки со слиянием Бэтчера – [электронный ресурс] - https://habr.com/ru/post/275889/