Файл: Алгоритмы сортировки данных. (ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ АЛГОРИТМА СОРТИРОВКИ ДАННЫХ).pdf

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

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

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

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

Алгоритм сортировки, подразумевающий сравнение элементов, расположенных на различных расстояниях друг от друга, называют сортировкой Шелла. В основу метода положена сортировка включениями. По мере реализации алгоритма первоначально осуществляется сравнение и сортировка между собой ключей, отстоящих друг от друга на некотором расстоянии R, после чего процедура повторяется для некоторых меньших значений R. В заключение проводится упорядочивание элементов при R = 1, что полностью эквивалентно обычной сортировке вставками. Выбор значений расстояния R между сравниваемыми элементами может осуществляться по-разному. Для корректной работы метода необходимым условием является лишь то, что последний шаг должен равняться единице. Программирование алгоритма выполняется с использованием двух циклов. Внешний цикл проходит по всем заданным элементам, а внутренний включает два условия проверки: для упорядочения элементов и для предотвращения выхода за пределы массива. Если при каждом проходе используется небольшое число элементов или они находятся в относительном порядке, данный способ сортировки будет сравнительно эффективен.

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

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

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

На рис. 1 представлено устройство для выбора максимального числа. Оно включает в себя три компаратора, логический блок и мультиплексор. Устройство позволяет выбирать максимальное из трех чисел a, b и с, т.е. упорядочивает множество \а.Ь,с\, реализуя функцию /: maх{а,Ь,с}.

Рис. 1. Устройство для выбора максимального из трех чисел

В зависимости от соотношения чисел a, b и с на входы логического блока поступают сигналы d, т, п, которые формируются в соответствии с таблицей (см. табл. 1.1).

Таблица 1.1 - Сигналы во внутренних точках устройства

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

Аналогично строится схема быстрой сортировки чисел. В ней вместо компараторов используются арифметико-логические устройства (ALU), выводы «Перенос» (С) которых соединены с адресными входами (AI) постоянного запоминающего устройства (ROM), которое выполняет функции логического блока. Выводы данных (DO) ПЗУ соединены с адресными входами (AI) четырех мультиплексоров (MUX). Несомненным достоинством этой схемы является возможность параллельной сортировки чисел, так как на выходах мультиплексоров они появятся одновременно, упорядоченные по убыванию или возрастанию. К недостаткам схемы можно отнести большие аппаратные затраты.

Так, например, количество элементов сравнения (АЛУ) определяется как количество сочетаний из п чисел по два:

Поэтому при возрастании количества сортируемых чисел резко возрастает количество компараторов (или АЛУ) и разрядность ПЗУ.

Рис. 1.2. Устройство для быстрой сортировки чисел

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

Рис. 1.3. Схема пирамидальной сортировки чисел

Схема пирамидальной сортировки (рис. 1.3) состоит из блоков выбора наибольшего/наименьшего числа (рис. 1.4).

Рис. 1.4. Блок выбора наибольшего/наименьшего числа из двух

Каждый блок выбора (рис. 1.4) в зависимости от режима сортировки выбирает одно из двух чисел - наибольшее или наименьшее. Он состоит из схемы сравнения, логического блока и буферов с третьим состоянием, включение/отключение которых производится сигналом (CS). Режим сортировки определяется сигналом (max/min).

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

а б

Рис. 1.5. Устройства для сортировки чисел

Оно состоит из оперативного запоминающего устройства (RAM) и двоичного счетчика с возможностью параллельной загрузки (СТ2). Основная идея состоит в том, что каждое число для сортировки представляется единицей, записанной по адресу, равному этому числу. Очевидно, что емкость ОЗУ в этом случае должна быть равна 2" бит, где п - разрядность чисел.

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

Далее производится загрузка ОЗУ числами для сортировки. Для этого счетчик переводится в режим параллельной загрузки данных и фактически представляет собой параллельный регистр. Каждое число, предназначенное для сортировки, подается на вход данных (DI) счетчика и через него на адресные входы (AI) ОЗУ. На вход данных (DI) ОЗУ подается уровень логической единицы, а на вход разрешения записи (Е) - сигнал, разрешающий загрузку данных в ОЗУ. После того как будут загружены все числа, выполняется режим сортировки. Он может выполняться по возрастанию или по убыванию. В случае сортировки по возрастанию импульсный сигнал подается на инкрементирующий вход (+1) счетчика, если выбран режим по убыванию - на декрементирующий (-1) вход. В этом режиме ОЗУ переводится в режим чтения, а счетчик последовательно пробегает все адресное пространство ОЗУ. В случае, если на выходе данных (DO) ОЗУ обнаруживается единица, это означает, что на выходах счетчика (DO) и выходной шине присутствует очередное отсортированное число.

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

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

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

ГЛАВА 2 ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ СОРТИРОВКИ ДАННЫХ С ИСПОЛЬЗОВАНИЕМ ТЕХНОЛОГИИ MPI

2.1 Описание алгоритма

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

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

Сортировка пузырьком (bubblesort) или сортировка простыми обменами - простой алгоритм сортировки, состоящий из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется перестановка элементов. Проходы по массиву повторяются N — 1 раз (N - длина массива) или до тех пор, пока на очередном проходе не окажется, что элементы массива уже отсортированы. Сложность алгоритма сортировки - 0(N²).

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

Сортировка Шелла (Shellsort) - алгоритм сортировки являющийся усовершенствованным вариантом алгоритма сортировки вставками. Идея метода состоит в сравнении элементов, стоящих не только рядом, но и на некотором расстоянии друг от друга. Иными словами - это сортировка вставками с предварительными „грубыми" проходами.

При сортировке Шелла сначала сравниваются и сортируются элементы, отстоящие друг от друга на некотором расстоянии d друг от друга. После этого процедура повторяется для некоторых меньших значений d. Заканчивается процедура при d — 1 (т.е. обычной процедуров вставками). Эффективность сортировки Шелла в определенных случаях обеспечивается тем, что элементы ,,быстрее встают на свои места.