Файл: Общие сведения об алгоритмах сортировки.pdf

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

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

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

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

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

Практически каждый алгоритм сортировки можно разбить на 3 части:

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

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

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

Глава 1. Общие сведения об алгоритмах сортировки

Что такое сортировка

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

Применение сортировки

По утверждению Д.Кнута, наиболее важные применения сортировки следующие:

a) группировка – задача, требующая собрать вместе все элементы с одинаковым значением какого-либо признака. Например, если имеется 10000 расположенных в случайном порядке элементов, причем таких, что значения многих из них совпадают. Предположим, нам нужно упорядочить эту последовательность так, чтобы соседние позиции занимали элементы с равными значениями. Это и есть задача сортировки в самом широком смысле этого слова. Такая задача может быть решена путем сортировки файла в узком смысле слова, т.е. расположением элементов в неубывающем (или невозрастающем) порядке элемент1, элемент2, … элемент10000. Эффективность этой процедуры довольно низкая, что и объясняет изменение первоначального смысла слова "сортировка".

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

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

История

Уже в XIX веке появились первые прототипы современных методов сортировки. В 1890 году американец Герман Холлерит создал первый статистический табулятор для ускорения обработки данных переписи населения в США. Он представлял собой электромеханическую машину, которая была предназначена для автоматической обработки информации, хранящейся на перфокартах. Машины Холлерита имела специальный «сортировальный ящик». Ящик состоял из 26 внутренних отделений. Работа оператора заключалась в том, чтобы вставить перфокарту и опустить специальную рукоятку. Благодаря отверстиям, пробитым на перфокарте, определённая электрическая цепь замыкалась, и показание связанного с ней циферблата увеличивалось на единицу. В тот же момент открывалась соответствующая крышка сортировального ящика, одна из 26, и перфокарта перемещалась в соответствующее отделение, затем крышка закрывалась. Таким образом удавалось обрабатывать более 50 карт в минуту, что превышало ручную обработку данных в 3 раза. Холлерит усовершенствовал свою машину к переписи 1900 года. Теперь подача карт была автоматизирована. Работа сортировальной машины Холлерита основывалась на методах поразрядной сортировки. На машину был оформлен патент. Причем была обозначена сортировка «по отдельности для каждого столбца», но сам порядок сортировки не определён. В 1894 Джоном Гором был получен патент на аналогичную машину. Здесь уже упоминалась сортировка со столбца десятков. В конце 1930-х годов впервые появляется в литературе метод сортировки, начиная со столбца единиц. К этому времени сортировальные машины уже позволяли обрабатывать до 400 карт в минуту.

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

В 1945 году была разработана программа сортировки методом слияния. Автор Джон фон Нейман применил ее для тестирования ряда команд для EDVAC. Тогда же немецкий инженер Конрад Цузе разработал программу для сортировки методом простой вставки. К этому времени уже появились быстрые специализированные сортировальные машины, в сопоставлении с которыми и оценивалась эффективность разрабатываемых ЭВМ. Первым опубликованным обсуждением сортировки с помощью вычислительных машин стала лекция Джона Мокли, прочитанная им в 1946 году. Мокли показал, что сортировка может быть полезной также и для численных расчетов, описал методы сортировки простой вставки и бинарных вставок, а также поразрядную сортировку с частичными проходами. Позже организованная им совместно с инженером Джоном Эккертом компания «Eckert–Mauchly Computer Corporation» выпустила некоторые из самых ранних электронных вычислительных машин BINAC и UNIVAC.

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

К 1952 году на практике уже применялись многие методы внутренней сортировки, но теория была развита сравнительно слабо. В октябре 1952 года Даниэль Гольденберг привёл пять методов сортировки с анализом наилучшего и наихудшего случаев для каждого из них. В 1954 году Гарольд Сьюворд развил идеи Гольденберга, а также проанализировал методы внешней сортировки. Говард Демут в 1956 году рассмотрел три абстрактные модели задачи сортировки: с использованием циклической памяти, линейной памяти и памяти с произвольным доступом. Для каждой из этих задач автор предложил оптимальные или почти оптимальные методы сортировки, что помогло связать теорию с практикой. Из-за малого числа людей, связанных с вычислительной техникой, эти доклады не появлялись в «открытой литературе». Первой большой обзорной статьёй о сортировке, появившейся в печати в 1955 году, стала работа Дж. Хоскена, в которой он описал всё имевшееся на тот момент оборудование специального назначения и методы сортировки для ЭВМ, основываясь на брошюрах фирм-изготовителей. В 1956 году Э. Френд в своей работе проанализировал математические свойства большого числа алгоритмов внутренней и внешней сортировки, предложив некоторые новые методы.

После этого было предложено множество различных алгоритмов сортировки: например, вычисление адреса в 1956 году; слияние с вставкой, обменная поразрядная сортировка, каскадное слияние и метод Шеллав 1959 году, многофазное слияние и вставки в дерево в 1960 году, осциллирующая сортировка и быстрая сортировка Хоара в 1962 году, пирамидальная сортировка Уильямса и обменная сортировка со слиянием Бэтчера в 1964 году. В конце 60-х годов произошло и интенсивное развитие теории сортировки. Появившиеся позже алгоритмы во многом являлись вариациями уже известных методов. Получили распространение адаптивные методы сортировки, ориентированные на более быстрое выполнение в случаях, когда входная последовательность удовлетворяет заранее установленным критериям.

Оценка алгоритмов сортировки

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

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

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

Устойчивость – это параметр, который отвечает за то, что сортировка не меняет взаимного расположения равных элементов.

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

Рисунок 1. Результат устойчивой сортировки

Взаимное расположение равных элементов с ключом 1 и дополнительными полями "a", "b", "c" осталось прежним: элемент с полем "a", затем - с "b", затем - с "c".

Рисунок 2. Результат неустойчивой сортировки

Взаимное расположение равных элементов с ключом 1 и дополнительными полями "a", "b", "c" изменилось.

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

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

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

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

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

Внешняя сортировка – при использовании этого алгоритма для упорядочивания данных подключается внешняя память, как правило, жесткие диски. Внешняя сортировка разработана для обработки больших списков данных, которые не помещаются в оперативную память. Обращение к различным носителям накладывает некоторые дополнительные ограничения на данный алгоритм: доступ к носителю осуществляется последовательным образом, то есть в каждый момент времени можно считать или записать только элемент, следующий за текущим; объем данных не позволяет им разместиться в ОЗУ.