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

Содержание:

Введение

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

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

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

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

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

Глава 1. Данные

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

Например, толковый словарь Ожегова [7.] даёт такое определение данных: «1.Сведения, необходимые для какого-нибудь вывода, решения. По официальным данным. Цифровые данные. 2. Свойства, способности, качества как условия или основания для чего-нибудь. Хорошие голосовые данные. Иметь все данные для научного роста».

В толковом словаре Ушакова [8.] «данные — Сведения, обстоятельства, служащие для какого-нибудь вывода, решения. Получены данные, что здесь скрывается преступник. Нет достаточных данных для возбуждения уголовного преследования»

В экономическом словаре Райсберга и Лозовского [9.] написано следующее: «данные - 1) факты и характеризующие их числовые, количественные показатели: имена, даты событий сведения об экономических процессах, местах действия; 2) сведения, обработанные Специальным образом для принятия решений, информация».

Согласно ГОСТ 17657-79 [1.] «данные - сведения, являющиеся объектом обработки в информационных человеко-машинных системах.»

Согласно ГОСТ 15971-90 [2.] «данные - информация, представленная в виде, пригодном для обработки автоматическими средствами при возможном участии человека».

Согласно ГОСТ 34.320-96 [3.] «данные -информация, представленная в формализованном виде, пригодном для передачи, интерпретации или обработки с участием человека или автоматическими средствами».

Согласно ГОСТ Р ИСО/МЭК 12119-2000 [4.] «данные - представление информации в формализованном виде, пригодном для передачи, интерпретации или обработки.».

Согласно ГОСТ Р 52292-2004 [5.] «4.2.1 данные: Интерпретируемое формализованным способом представление информации, пригодное для коммуникации, интерпретации или обработки.».

Согласно ISO/IEC/IEEE 24765-2010 [6.] «Данные — зарегистрированная информация; представление фактов, понятий или инструкций в форме, приемлемой для общения, интерпретации, или обработки человеком или с помощью автоматических средств».

В Большом Энциклопедическим словаре [10.] написано: «данные - в информатике информация, представленная в формализованном виде, что обеспечивает возможность ее хранения, обработки и передачи…».

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

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

Глава 2. Этапы развития методов сортировки данных

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

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

Впервые проблема сортировки данных в больших массивах появилась в США в середине XIX века. В 1840 году там был создан центральный офис переписи населения, в который собирались данные со всех штатов. Обработка такого количества информации требовала огромных затрат труда и времени. Так, обработка данных полученных от переписи населения 1880 года потребовала привлечения сотен служащих и длилась семь с половиной лет.

В связи с этим, перед переписью 1890 года, для решения проблемы сортировки данных в очень больших массивах был проведен конкурс на лучшее электромеханическое оборудование, которое сделало бы сортировку данных более точной, быстрой и дешевой. Выиграл конкурс американский инженер-изобретатель Герман Холлерит [11.]. Он изобрел оборудование для работы с перфокартами – электронную табулирующую систему, известную как Hollerith Electric Tabulating System [12.].

Использование способа табулирования [13.] оказалось настолько эффективно, что полная обработка данных переписи 1890 года заняла всего два с половиной года, то есть в три раза меньше времени, чем при ручной обработке.

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

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

Существуют два варианта поразрядной сортировки: least significant digit (LSD) и most significant digit (MSD) [14.]. В первом случае сначала сортируются младшие разряды, а затем старшие. При этом получается следующий порядок: короткие ключи идут раньше длинных, при равном размере сортируются по алфавиту. Это необходимо для сортировки числовых данных. При MSD наоборот, сначала идет сортировка старших разрядов, потом младших. При этом получается алфавитный порядок, подходящий для сортировки строк.

Следующий этап развития методов сортировки данных начался с появлением первых электронных вычислительных машин в 1940-х.

Существуют свидетельства, что первой программой для ЭВМ с хранимой программой (с архитектурой Джона фон Неймана) была именно программа сортировки [15.].

Быстродействие ЭВМ вызвало рост интереса к новым, приспособленным к машинной обработке методам сортировки данных. В 1946 году вышла статья Джона Уильяма Мочли [16.] об алгоритмах сортировки данных. В этой статье рассматривался целый ряд новых алгоритмов сортировки, в том числе метод бинарных вставок.

До середины 1950-х годов наибольшей популярностью пользовались модификации сортировки слиянием и вставками.

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

В 1959 году Дональд Левис Шелл [17.Error: Reference source not found] изобрел метод сортировки с убывающим шагом. Идея этой сортировки заключается в сортировке данных находящихся на некотором расстоянии d друг от друга в несколько шагов, с сокращением этого расстояния на каждом последующем шаге. Завершается сортировка Шелла упорядочиванием элементов при d = 1.

В 1960 году Чарльз Энтони Ричард Хоар [18.] предложил метод быстрой сортировки. Несмотря на то, что эта сортировка разработана более полувека назад, она и сейчас широко применяется и является одной из самых эффективных. В этом алгоритме в массиве выбирается опорный элемент, находящийся в пределах массива, после чего происходит разделение массива на 2 части: в одной части находятся элементы меньшие, чем опорный, в другой равные или превышающие его. Для каждого полученного подмассива процедура повторяется пока в подмассиве остается 2 и более элементов. В итоге получится отсортированная последовательность.

В 1964 году Дж. У. Дж. Уильямс [19.] предложил метод пирамидальной сортировки. В алгоритме этой сортировки на каждом шаге цикла находится и устанавливается в конец массива наибольший элемент, после чего цикл продолжается без этого элемента.

Итоги этого этапа эволюции алгоритмов сортировки подвел в 1973 году Дональд Эрвин Кнут в своей фундаментальной монографии «Искусство программирования», методам сортировки и поиска он посвятил третий том своего трёхтомника [20.].

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

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

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

Таким образом, в эволюции алгоритмов сортировки данных можно выделить 5 этапов.

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

Второй этап – с начала 1940-х годов до середины 1950-х годов. На смену счетно-перфораторным машинам пришли ЭВМ первого поколения, были разработаны новые алгоритмы сортировки данных. Произошло разделение алгоритмов на внутренние и внешние.

Третий этап – с середины 1950-х годов до середины 1970-х. Для него было характерно активное развитие алгоритмов сортировки, многие из которых используются до сих пор.

Четвертый этап – с середины 1970-х годов до середины 1990-х. Модификация существующих алгоритмов развития и разработка новых связанные с появлением вычислительных центров, объединяющих мощности отдельных вычислительных машин. Начало исследования задач сортировки в классе параллельных алгоритмов.

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

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

Глава 3. Методы сортировки численных данных

Сортировка представляет собой процесс упорядочения множества подобных информационных объектов в порядке возрастания или убывания их значений. Например, список i из n элементов будет отсортирован в порядке возрастания значений элементов, если i <= i <= ... <= i.

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

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

Количество алгоритмов сортировки достаточно велико. В третьем томе монографии Дональда Кнута "Искусство программирования для ЭВМ" [20.] рассматривается более двадцати (примерно 25) алгоритмов сортировки. В настоящее время это число ещё больше увеличилось, и, вместе с экзотическими и мало распространёнными алгоритмами, приближается к 40 (и даже уже превышает 40, а с модификациями ещё больше, 42-44, скорее всего и эти цифры заниженные). Все эти алгоритмы можно классифицировать по нескольким признакам.

1. В зависимости от того, сортируются данные в оперативной памяти машины (ОЗУ) или во внешнем ЗУ, сортировка бывает внутренней или внешней (В настоящее время, благодаря огромной памяти компьютеров, этот признак стал несущественным)

2. В зависимости от того, какая структура данных подвергается сортировке, может быть сортировка массива, связного списка, дерева (пирамиды), графа.

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

4. По особенностям функциональной реализации алгоритмы сортировки делятся на группы:

А. Основные:
− сортировка перестановками (обменная);
− сортировка выбором (отбором);
− сортировка вставками;
Б. Неосновные:
− сортировка подсчетом;
− сортировка слиянием;
− распределяющая сортировка.

5. По широте применения − универсальные (большинство перечисленных выше групп алгоритмов) и алгоритмы для конкретных случаев.

6. По признаку перестановки совпадающих данных в процессе сортировки − алгоритмы, не меняющие порядок следования совпадающих ключей (иногда такие алгоритмы не совсем удачно называют "устойчивыми" или "стабильными"), например, сортировка вставками, и меняющие порядок следования ("неустойчивые").

7. По характеру зависимости времени работы от размера N структуры данных:

− алгоритмы, время работы которых пропорционально второй степени от количества данных -квадратичные (это самые простые);

− алгоритмы, время работы которых пропорционально k степени от количества данных, где 1<k<2 (например, k = 1,6667 или k = 1,5 или k = 1,27 и т.п. − это алгоритм Шелла); возможен также случай, когда k = 3 − это один из самых неудачных и неэффективных алгоритмов, который получил название глупая сортировка (или дурацкая сортировка);

− алгоритмы, время работы которых пропорционально логарифму от количества данных по основанию 2 (log2N) − логарифмические (например, быстрая сортировка или пирамидальная сортировка).

Возможны также некоторые другие принципы разделения алгоритмов сортировки.

При таком большом разнообразии важными оказываются критерии выбора алгоритма:

− средняя скорость сортировки (среднее время, удельная скорость);

− скорость в лучшем и худшем случаях (или минимальное и максимальное время);

− естественность поведения;

− переставляются ли элементы с совпадающими значениями (ключами).

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

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

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

Кроме перечисленных критериев при выборе алгоритма следует принимать во внимание:

− размер структуры данных, которую предстоит сортировать (некоторые алгоритмы, высокоэффективные в средних случаях, например быстрая сортировка, не показывают своей высокой эффективности для массивов малого размера);

− степень исходной упорядоченности сортируемых данных;

− требования к необходимой памяти (разным алгоритмам может требоваться объём памяти машины, пропорциональный количеству данных или квадрату от этого колчества);

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

Наиболее известные алгоритмы сортировки

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

1.1. Сортировка пузырьком (англ. Bubble sort) ;

1.2. Сортировка перемешиванием (англ. Cocktail sort);

1.3. Гномья сортировка (англ. Gnome sort);

1.4. Сортировка вставками (англ. Insertion sort);

1.5. Сортировка слиянием (англ. Merge sort) ;

1.6. Сортировка с помощью двоичного дерева (англ. Tree sort);

1.7. Сортировка Timsort (англ. Timsort) — комбинированный алгоритм (используется сортировка вставками и сортировка слиянием;

1.8. Сортировка подсчётом (англ. Counting sort);

1.9. Блочная сортировка (Корзинная сортировка, англ. Bucket sort);

1.10. Поразрядная сортировка (она же цифровая сортировка).

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

2.1. Сортировка выбором (англ. Selection sort);

2.2. Сортировка Шелла (англ. Shell sort);

2.3. Сортировка расчёской (англ. Comb sort);

2.4. Пирамидальная сортировка (сортировка кучи, англ. Heapsort);

2.5. Плавная сортировка (англ. Smoothsort);

2.6. Быстрая сортировка (англ. Quicksort);

2.7. Интроспективная сортировка (англ. Introsort), сочетание быстрой и пирамидальной сортировки;

2.8. Терпеливая сортировка (англ. Patience sorting);

2.9. англ. Stooge sort — рекурсивный алгоритм сортировки с временной сложностью.

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

3.1. Bogosort. Произвольно перемешать массив, проверить порядок.

3.2. Сортировка перестановкой . Для каждой пары осуществляется проверка верного порядка и генерируются всевозможные перестановки исходного массива.

3.3. Глупая сортировка (Stupid sort)

4. Требующие специального аппаратного обеспечения

4.1. Bead Sort;

4.2. Блинная сортировка (англ. Pancake sorting) .

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

5.1. Блочная сортировка (Корзинная сортировка, англ. Bucket sort);

5.2. Лексикографическая или поразрядная сортировка (англ. Radix sort);

5.3. Сортировка подсчётом (англ. Counting sort)

6. Прочие алгоритмы сортировки

6.1. Топологическая сортировка

6.2. Внешняя сортировка

Глава 4. Примеры программной реализации сортировок

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

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

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

Пример процедуры, реализующей алгоритм сортировки методом пузырька (Arr - массив для сортировки с начальным индексом 0, n - размерность массива [29.].

procedure SortPuz (var Arr : array of Integer; n : Integer);
var
i : Integer;
Temp : Integer;
Flag : Boolean;
begin
repeat
Flag := False;
for i := 0 to n - 1 do
if Arr [i] > Arr [i + 1] then begin
Temp := Arr [i];
Arr [i] := Arr [i + 1];
Arr [i + 1] := Temp;
Flag := True;
end;
until Flag = False;
end;

void bubble_sort(int *a, int length)
{
for (int i = 0; i < length-1; i++) {
bool swapped = false;
for (int j = 0; j < length-i-1; j++) {
if (a[j] > a[j+1]) {
int b = a[j];
a[j] = a[j+1];
a[j+1] = b;
swapped = true;
}
}
if(!swapped)
break;
}
}

Шейкерная сортировка

Алгоритм сортировки пузырьком можно немного улучшить, сделав следующее:

Внутренний цикл можно модифицировать так, чтобы он поочерёдно просматривал массив то с начала, то с конца. Модифицированный таким образом алгоритм называется сортировкой перемешиванием или шейкерной сортировкой. По сути, она является разновидность пузырьковой сортировки, вот только в то время, как минимальные значения плывут к одному концу массива, максимальные идут к его дну. Итог, разумеется, один — массив становится упорядоченным.

Этот метод может использоваться для сортировки больших массивов; в том числе — расположенных не в оперативной памяти, а на жёстком диске.

Время выполнения в данном случае заметно меньше.

Вот образец кода: [30.]

while e>s do
begin
for i:=s to e-1 do
if X[i]>X[i+1] then
begin
tmp:=X[i];
X[i]:=X[i+1];
X[i+1]:=tmp;
end;
for i:=e downto s+1 do
if X[i]<x [i-1] then
begin
tmp:=X[i];
X[i]:=X[i-1];
X[i-1]:=tmp;
end;
s:= s+1;
e:= e-1;
end;

Здесь S — первый элемент массива, а E — последний. В данном коде по умолчанию эти значения уже известны. Когда максимальный элемент встал в один конец, а минимальный в другой, то промежуток сортировки сужается на единицу с обоих концов массива — S:=S+1; E:=E-1.

Сортировка методом нахождения минимального элемента

Ещё один вариант сортировки, более быстрый, чем метод пузырька. Заключается он в следующем: при каждом просмотре массива находим минимальный элемент и меняем местами его с первым на первом проходе, со вторым - на втором и т.д. [31.]

procedure SortMin (var Arr : array of Integer; n : Integer);
var
i, j : Integer;
Min, Pos, Temp : Integer;
begin
for i := 0 to n - 1 do begin
Min := Arr [i];
Pos := i;
for j := i + 1 to n do
if Arr [j] < Min then begin
Min := Arr [j];
Pos := j;
end;
Temp := Arr [i];
Arr [i] := Arr [Pos];
Arr [Pos] := Temp;
end;
end;

Гномья сортировка

Хотя гномам этот способ известен уже много столетий, человеческая раса о нём узнала совсем недавно. Уже 55 лет как человечество использовало сортировку слиянием, прошло 40 лет как стала известна быстрая сортировка, уже 35 лет как разработана пирамидальная сортировка – и вот, только в 2000 году, этот бесхитростный, практически детский приём, был впервые описан Диком Груном [32.]:

Гномья сортировка основана на технике, используемой обычным голландским садовым гномом (нидерл. tuinkabouter). Это метод, которым садовый гном сортирует линию цветочных горшков. По существу он смотрит на следующий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперёд; если нет следующего горшка, он закончил.

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

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

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

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

Временная сложность у этой сортировки пропорционально квадрату от количества данных, но не это главное. Сортировка вставками, судя по всему — наиболее эффективный вариант для почти отсортированных массивов. Этот факт используется в некоторых сложных алгоритмах сортировки. Таких, как FlashSort [33.], там при помощи вероятностного распределения быстро создаётся почти отсортированный массив, который затем доупорядочивается сортировкой вставками. Сортировка вставками используется в финальной части JSort [34.], где путём построениянеполной кучи массив оперативно почти сортируется. Timsort [35.] начинает сортировку массива с нахождения в нём почти упорядоченных отрезков, они также сортируются вставочным методом, а затем объединяются модифицированной сортировкой слиянием.

Хотя сортировка вставками сама по себе работает медленно, потенциал у алгоритма огромен [36.].

procedure SortInsert (var Arr : array of Integer; n : Integer);
var
i, j, Temp : Integer;
begin
for i := 1 to n do begin
Temp := Arr [i];
j := i - 1;
while Temp < Arr [j] do begin
Arr [j + 1] := Arr [j];
Dec (j);
if j < 0 then
Break;
end;
Arr [j + 1] := Temp;
end;
end;

Поиск перебором

Чтобы найти какие-то данные в неупорядоченном массиве, применяется алгоритм простого перебора элементов. Следующая функция возвращает индекс заданного элемента массива. Её аргументы: массив с первым индексом 0, количество элементов в массиве и искомое число. Если число не найдено, возвращается -1. [37.]

function SearchPer (Arr : array of Integer; n, v : Integer) : Integer;
var
i : Integer;
begin
Result := -1;
for i := 1 to n do
if Arr [i] = v then begin
Result := i;
Exit;
end;
end;

Бинарный поиск

При поиске в упорядоченном массиве можно применить гораздо более быстрый метод поиска - бинарный. Суть его в следующем: В начале переменная Up указывает на самый маленький элемент массива (Up := 0), Down - на самый большой (Down := n, где n - верхний индекс массива), а Mid - на средний. Дальше, если искомое число равно Mid, то задача решена; если число меньше Mid, то нужный нам элемент лежит ниже среднего, и за новое значение Up принимается Mid + 1;и если нужное нам число меньше среднего элемента, значит, оно расположено выше среднего элемента, и Down := Mid - 1. Затем следует новая итерация цикла, и так повторяется до тех пор, пока не найдётся нужное число, или Up не станет больше Doun. [38.]

function SearchBin (Arr : array of Integer; v, n : Integer) : Integer;
var
Up, Down, Mid : Integer;
Found : Boolean;
begin
Up := 0; Down := n;
Found := False; Result := -1;
repeat
Mid := Trunc ((Down - Up) / 2) + Up;
if Arr [Mid] = v then
Found := True
else
if v < Arr [Mid] then
Down := Mid – 1
else
Up := Mid + 1;
until (Up > Down) or Found;
if Found then
Result := Mid;
end;

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

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

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

procedure QuickSort(var X: array of integer; min,max: Integer);
Var
i, j, mid, tmp: integer;
Begin
if min<max then
begin
mid:=X[min];
i:=min-1;
j:=max+1;
while i<j do
begin
repeat i:=i+1;
until X[i]>=mid;
repeat j:=j-1;
until X[j]< =mid;
if i<j then
begin
tmp:=X[i];
X[i]:=X[j];
X[j]:=tmp;
end;
end;
QuickSort(X, min, j);
QuickSort(X, j+1, max);
end;
end;

Сортировка методом Шелла

Сортировку Шелла придумал Дональд Шелл в 1959 году. Метод Шелла (англ. Shell sort) Сортировка Шелла— алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Дональда Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга; иными словами — это сортировка вставками, но с предварительными «грубыми» проходами.

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

Временная сложность у «шелла» – достаточно сложный вопрос. Дело в том, что до сих пор нет строгой формулы, по которой строится оптимальный числовой ряд изменяющихся расстояний между элементами в подгруппах. Последовательность строится эмпирически, на основании многочисленных тестов с различными входными данными и последнее наилучшее уточнение для вышеупомянутых «дельт» было определено в 2001 году:

1, 4, 10, 23, 57, 132, 301, 701. [40.]

Эффективность сортировки Шелла, — в определённых случаях, — обеспечивается тем, что элементы «быстрее» встают на свои места (в простых методах сортировки, — например, пузырьковой, — каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, а при сортировке Шелла — это число может быть больше).

Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка — она имеет ряд преимуществ:

Отсутствие потребности в памяти под стек;

Отсутствие деградации при неудачных наборах.

Реализация на C [41.]
// BaseType - любой перечисляемый тип
// typedef int BaseType – пример
void ShellsSort(BaseType *A, unsigned N)
{
BaseType t;
for(unsigned k = N/2; k > 0; k /= 2)
for(unsigned i = k; i < N; i += 1)
{
t = A[i];
unsigned j;
for(j = i; j >= k; j -= k)
{
if(t < A[j-k])
A[j] = A[j-k];
else
break;
}
A[j] = t;
}
}

Сортировка подсчётом

Особый метод, где собственно не используются привычные для нас операции сравнения элементов. Алгоритм работает невероятно быстро, если элементами массива являются целые числа, со значениями, которые занимают, относительно узкий диапазон. Пока выполняются эти условия, алгоритм работает отлично. Для примера можно привести результат сортировки 1 миллиона элементов со значением от 1-10000, на том же компьютере с процессором Pentium-133. Время быстрой сортировки было равно 3,93 секунды, результат же сортировки подсчётом был 0,37 секунды, то есть быстрее в 10 раз.[42.]

procedure CountingSort(var X: array of integer; min, max: integer);
var
counter: array[0..100000] of integer;
i, j, index: Integer;
begin
// для всех элементов массива
// указываем значение ноль
for i:=0 to high(counter)
do tmpX[i]:=0;
for i:=min to max
do counter[ar[i]]:=counter[ar[i]]+1;
// устанавливаем значение
// в правильную позицию
index:=min;
for i:=min to high(counter)-1 do
begin
for j:=0 to counter[i]-1 do
begin
ar[index]:=i;
index:=index+1;
end;
end;
end;

Глупая сортировка

Глупая сортировка (англ. Stupid sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Время работыагоритма пропорционально третьей степени от количества элементов. [43.]

В действительности под глупыми сортировками часто подразумевают совершенно другие алгоритмы, в частности Bogosort [44.]. Термин «глупая сортировка» очень перегружен и лучше избегать его использования, или по крайней мере уточнять, о какой именно глупой сортировке идёт речь в том или ином контексте.

Имеет нечто общее с сортировкой пузырьком: идёт поиск от начала массива, текущий элемент сравнивается со следующим, если следующий меньше, то производится обмен и возврат в начало цикла.

Пример реализации на С

// A - сортируемый массив, n - количество элементов
void stupidSort(int *A, int n)
{
int i = 0, tmp;
while (i < n - 1)
{
if (A[i+1] < A[i])
{
tmp = A[i];

A[i] = A[i+1];
A[i+1] = tmp;
i = 0;
}
else i++;
}
}

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

Пирамидальная сортировка ( англ. Heapsort, «Сортировка кучей» [45.]) — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за время, пропорциональное (n log n) операций при сортировке n элементов.

Может рассматриваться как усовершенствованная сортировка пузырьком, в которой элемент всплывает) / тонет) по многим путям.

Пирамидальная сортировка была предложена Дж. Уильямсом в 1964 году.

Достоинства:

- имеет доказанную оценку худшего случая;

- сортирует на месте, то есть практически не требует дополнительной памяти.

Недостатки:

- сложен в реализации;

- неустойчив;

- на почти отсортированных массивах работает столь же долго, как и на хаотических данных.

На одном шаге выборку приходится делать хаотично по всей длине массива — поэтому алгоритм плохо сочетается с кэшированием и подкачкой памяти.

Методу требуется «мгновенный» прямой доступ; не работает на связанных списках и других структурах памяти последовательного доступа.

Из-за сложности алгоритма выигрыш получается только на больших n. На небольших n (до нескольких тысяч) быстрее сортировка Шелла.

Пример реализации:

static void HeapSort(int[] a)
{
int i;
int temp;
for (i = a.Length / 2 - 1; i >= 0; i--)
{
shiftDown(a, i, a.Length);
}

for (i = a.Length - 1; i >= 1; i--)
{
temp = a[0];
a[0] = a[i];
a[i] = temp;
shiftDown(a, 0, i);

}
}

static void shiftDown(int[] a, int i, int j)
{
bool done = false;
int maxChild;
int temp;

while ((i * 2 + 1 < j) && (!done))
{
if (i * 2 + 1 == j - 1)
maxChild = i * 2 + 1;
else if (a[i * 2 + 1] > a[i * 2 + 2])
maxChild = i * 2 + 1;

Else
maxChild = i * 2 + 2;

if (a[i] < a[maxChild])
{
temp = a[i];
a[i] = a[maxChild];
a[maxChild] = temp;
i = maxChild;
}
else
{
done = true;
}
}
}

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

Быстрая сортировка, сортировка Хоара (англ. QuickSort), часто называемая qsort (по имени в стандартной библиотеки языка Си) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.

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

Общая идея алгоритма состоит в следующем:

Выбрать из массива элемент, называемый опорным. Это может быть любой из элементов массива или же число, вычисленное на основе значений элементов; от выбора этого числа сильно зависит эффективность алгоритма.

Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на три непрерывных отрезка, следующие друг за другом: «меньшие опорного», «равные» и «большие». [39.]

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

На практике массив обычно делят не на три, а на две части: например, «меньшие опорного» и «равные и большие»; такой подход в общем случае эффективнее, так как упрощает алгоритм разделения.

Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:

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

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

Два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива, соответственно.

Вычисляется значение опорного элемента m по одной из стратегий.

Индекс l последовательно увеличивается до тех пор, пока l-й элемент не окажется больше или равен опорному.

Индекс r последовательно уменьшается до тех пор, пока r-й элемент не окажется меньше или равен опорному.

Если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент.

Если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно, изменяется именно индекс опорного элемента и алгоритм продолжает своё выполнение.

Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.

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

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

Достоинства и недостатки

Достоинства:

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

Прост в реализации.

Хорошо сочетается с механизмами кэширования и виртуальной памяти.

Допускает естественное распараллеливание (сортировка выделенных подмассивов в параллельно выполняющихся подпроцессах).

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

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

Недостатки:

- сильно деградирует по скорости при неудачных входных данных.

- прямая реализация в виде функции с двумя рекурсивными вызовами может привести к ошибке переполнения стека.

- неустойчив.

Улучшения

Улучшения алгоритма направлены, в основном, на устранение или смягчение вышеупомянутых недостатков, вследствие чего все их можно разделить на две группы: придание алгоритму устойчивости и «защита от худшего случая» — устранение деградации производительности и переполнения стека вызовов из-за большой глубины рекурсии при неудачных входных данных.

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

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

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

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

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

Недостаток всех усложнённых методов выбора опорного элемента — дополнительные накладные расходы; впрочем, они не так велики.

Во избежание отказа программы из-за большой глубины рекурсии могут применяться следующие методы:

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

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

Разбивать массив не на две, а на три части.

Глава 5. Сравнение алгоритмов сортировки

Алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования памяти:

Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах мощности входного множества A. Если на вход алгоритму подаётся множество A, то обозначим n = |A|. Для типичного алгоритма хорошее поведение — это O(n log n) и плохое поведение — это O(n2). Идеальное поведение для упорядочения — O(n).

Свойства и классификация

Устойчивость (англ. stability) — устойчивая сортировка не меняет взаимного расположения элементов с одинаковыми ключами.

Естественность поведения — эффективность метода при обработке уже упорядоченных или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.

Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов упорядочения два:

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

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

Внешняя сортировка оперирует запоминающими устройствами большого объёма, но не с произвольным доступом, а последовательным (упорядочение файлов), то есть в данный момент «виден» только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам упорядочения, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным во внешней памяти производится намного медленнее, чем операции с оперативной памятью.

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

Объём данных не позволяет им разместиться в ОЗУ.

Также алгоритмы классифицируются по:

потребности в дополнительной памяти или её отсутствию;

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

Итак, подытожим вышесказанное и выделим для каждого метода свои плюсы и минусы.

Пузырьковая сортировка:

+ быстро работает для почти отсортированных списков;

– медленно работает в остальных случаях.

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

+ быстро сортирует большие списки;

– работает некорректно при большом количестве одинаковых значений.

Сортировка Шейкером:

+ сортирует данные на жёстком диске;

– работает медленнее, чем быстрая сортировка.

Метод Шелла:

+ сортирует дробные числа;

– требует много памяти для хранения временных значений.

Сортировка подсчётом:

+ очень быстро работает, если разброс входных значений не велик;

– медленно работает в случае если разброс составляет >log(N).

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

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

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

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

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

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

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

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

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

Алгоритмы, не основанные на сравнениях, как видно из названия не используют операции сравнения для сортируемых элементов. Наиболее известными из данных алгоритмов являются блочная сортировка, лексикографическая сортировка и сортировка подсчетом. При блочной сортировки требуются знания о природе сортируемых данных, выходящих за рамки функций «сравнить» и «поменять местами», достаточных для сортировки с использованием других элементов. Лексикографическая сортировка подходит для сортировки элементов, состоящих из цепочек над фиксированным алфавитом, на котором задано отношение сравнения. При сортировке подсчетом используется диапазон чисел сортируемого массива подсчета совпадающих элементов.

Эффективны при сортировке подходящего массива входных данных. Низкая эффективность если массив входящих данных слабо подходит для соответствующего алгоритма сортировки.

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

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

Сравнивать алгоритмы сортировки удобно матричным методом, предполагающим сравнение по двум параметрам. При сравнении по устойчивости алгоритмы сортировки делятся на устойчивые и неустойчивые. При сравнении по скорости алгоритмы можно разделить на 3 группы: число операций в которых <n², n² и >n².

Из представленных алгоритмов сортировки большинство входит в три получившихся группы. Это - «Быстрая устойчивая сортировка» (алгоритм сортировки Тима Петерса и сортировка слиянием), «Быстрая неустойчивая сортировка» (интроспективная сортировка, сортировка Шелла, плавная сортировка, терпеливая сортировка, пирамидальная сортировка) и «Медленная устойчивая сортировка» (гномья сортировка, сортировка вставками, сортировка пузырьком, сортировка выбором, сортировка перемешиванием).

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

Глава 6. Сортировка строк

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

Применение данного метода к строкам, представляющим собой числа в естественной записи, выдаёт контринтуитивные результаты: например, «9» оказывается больше, чем «11», так как первый символ первой строки имеет бо́льшее значение, чем первый символ второй. Для исправления этой проблемы алгоритм сортировки может преобразовывать сортируемые строки в числа и сортировать их как числа. Такой алгоритм называется «числовой сортировкой», а описанный ранее — «строковой сортировкой».

Глава 7. Сортировки в программе Excel

В программе Excel предусмотрены следующие методы сортировки.

Можно выполнять сортировку данных по тексту (от А к Я или от Я к А), при необходимости можно выполнить сортировку с учетом регистра, по числам (от наименьших к наибольшим или от наибольших к наименьшим), а также датам и времени (от старых к новым или от новых к старым) в нескольких столбцах. Можно также выполнять сортировку по настраиваемым спискам (таким как состоящий из элементов "Большой", "Средний" и "Маленький") или по формату, включая цвет ячеек, цвет шрифта, а также по значкам. Большинство сортировок применяются к столбцам, но возможно также применить сортировку к строкам. Имеется сортировка по цвету ячейки, цвету шрифта или значку. Предусмотрена сортировка по нескольким столбцам или строкам

Заключение

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

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

1. ГОСТ 17657-79. Передача данных. Термины и определения.
2. ГОСТ 15971-90. Системы обработки информации. Термины и определения
3. ГОСТ 34.320-96. Информационные технологии. Система стандартов по базам данных. Концепции и терминология для концептуальной схемы и информационной базы.
4. ГОСТ Р ИСО/МЭК 12119-2000. Информационная технология. Пакеты программ. Требования качеству и тестирование.
5. ГОСТ Р 52292-2004. Информационная технология. Электронный обмен информацией. Термины и определения.
6. URL: https://ru.wikipedia.org/wiki/Данные . (Дата обращения 11.08.2016).
7. Ожегов С. И., Шведова Н. Ю. Толковый словарь русского языка: 80 000 слов и фразеологических выражений / Российская академия наук. Институт русского языка им. В. В. Виноградова. — 4-е изд., дополненное. — М.: Азбуковник, 1999. — 944 с.
8. проф. Ушаков Д. Н. Орфографический словарь русского языка. — М.: Учпедгиз, 1937. — 162 с.
9. Райзберг Б.А., Лозовский Л.Ш., Стародубцева Е.Б. Современный экономический словарь. — 2-е изд., испр. М.: ИНФРА-М, 1999. 479 с.
10. Большой энциклопедический словарь / Ред. А. М. Прохоров . – 2-е изд., перераб. и доп . – М. : Большая Российская энциклопедия, 2000 . – 1456 с.
11. URL: http://dic.academic.ru/dic.nsf/es/92145/Герман Холлерит (Дата обращения 11.08.2016).
12. URL: https://en.wikipedia.org/wiki/Tabulating_machine (Дата обращения 11.08.2016).
13. Суменко Л.Г. Англо-русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003
14. URL: https://ru.wikipedia.org/wiki/Поразрядная_сортировка (Дата обращения 11.08.2016).
15. URL: http://rain.ifmo.ru/cat/data/theory/school/ses-VectSort-05/pres.pdf. (Дата обращения 11.08.2016).
16. URL: https://ru.wikipedia.org/wiki/Мокли,_Джон (Дата обращения 11.08.2016).
17. URL: https://ru.wikipedia.org/wiki/Шелл,_Дональд (Дата обращения 11.08.2016).
18. URL: https://ru.wikipedia.org/wiki/Хоар,_Чарльз_Энтони_Ричард (Дата обращения 11.08.2016).
19. URL: http://www.tp7.info/ebook/piramid_sort.pdf (Дата обращения 11.08.2016).
20. Дональд Кнут. Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. —М.: «Вильямс», 2007. — С. 824. — ISBN 5-8459-0082-4.
21. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 5-8459-0857-4.
22. Роберт Седжвик. Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск = Algorithms in C. Fundamentals/Data Structures/Sorting/Searching. — СПб.: ДиаСофтЮП, 2003. — С. 672. — ISBN 5-93772-081-4.
23. Magnus Lie Hetland. Python Algorithms: Mastering Basic Algorithms in the Python Language. — Apress, 2010. — 336 с. — ISBN 978-1-4302-3237-7.
24. URL: http://www.moluch.ru/archive/56/7702/ (Дата обращения 11.08.2016).
25. URL: http://www.moluch.ru/archive/55/7474/ (Дата обращения 11.08.2016).
26. URL: http://www.intuit.ru/studies/courses/12181/1174/lecture/25257 (Дата обращения 11.08.2016).
27. Дупленко А. Г. Сравнительный анализ алгоритмов сортировки данных в массивах // Молодой ученый. — 2013. — № 8. — С. 50–53.
28. Никитин Ю. Б. Сложность алгоритмов сортировки на частично упорядоченных множествах: автореферат дис. … канд. физ.-мат. наук: 01.01.09 / Никитин Юрий Борисович. — Москва, 2001. — 80 с.
29. URL: http://articles.org.ru/docum/sort.php (Дата обращения 11.08.2016).
30. URL: https://ru.wikipedia.org/wiki/Сортровка_перемешиванием (Дата обращения 11.08.2016).
31. URL: http://articles.org.ru/docum/sort.php (Дата обращения 11.08.2016).
32. URL: https://ru.wikipedia.org/wiki/Гномья_сортировка (Дата обращения 11.08.2016).
33. URL: https://habrahabr.ru/post/280848/ (Дата обращения 11.08.2016).
34. URL: https://habrahabr.ru/post/221095/ (Дата обращения 11.08.2016).
35. URL: https://ru.wikipedia.org/wiki/Timsort (Дата обращения 11.08.2016).
36. URL: https://ru.wikipedia.org/wiki/Сортировка_вставками (Дата обращения 11.08.2016).
37. URL: https://ru.wikipedia.org/wiki/Метод_перебора (Дата обращения 11.08.2016).
38. URL: https://ru.wikipedia.org/wiki/Двоичный_поиск (Дата обращения 11.08.2016).
39. URL: https://ru.wikipedia.org/wiki/Быстрая_сортировка (Дата обращения 11.08.2016).
40. URL: http://www.pvsm.ru/algoritmy/50063/print/ (Дата обращения 11.08.2016).
41. URL: https://ru.wikipedia.org/wiki/Сортировка_Шелла (Дата обращения 11.08.2016).
42. URL: https://ru.wikipedia.org/wiki/Сортировка_подсчётом (Дата обращения 11.08.2016).
43. URL: https://ru.wikipedia.org/wiki/Глупая_сортировка (Дата обращения 11.08.2016).
44. URL: https://ru.wikipedia.org/wiki/Bogosort (Дата обращения 11.08.2016).
45. URL: https://ru.wikipedia.org/wiki/Пирамидальная_сортировка (Дата обращения 11.08.2016).