Розглядаються обчислювальні процеси (ОП) як простих, так і ефективних сортувань. Для наочності ОП представляються схемами алгоритмів. У кожному процесі виділяються макрооперації (МО), які є функціонально закінченими фрагментами ОП. Списки МО для кожної сортування зводяться воєдино і узагальнюються, тобто зводяться до мінімуму МО. Це дозволяє розглядати більшість ОП сортувань в рамках виділених МО. Ключові слова: сортування, обчислювальний процес, схема алгоритму, макрооперація. Рассматриваются вычислительные процессы (ВП) как простых, так и эффективных сортировок. Для наглядности ВП представляются схемами алгоритмов. В каждом процессе выделяются макрооперации (МО), которые являются функционально законченными фрагментами ВП. Списки МО для каждой сортировки сводятся воедино и обобщаются, то есть сводятся к минимальному количеству МО. Это позволяет рассматривать большинство ВП сортировок в рамках выделенных МО. Ключевые слова: сортировка, вычислительный процесс, схема алгоритма, макрооперации. The paper dwells computation process (CP) array sorting from the simple to the efficient. Computation process present's as a block flowchart for clarity. Each process are extracted macro operations (MO), which are functionality finished pieces of CP. Lists of MO for each sorting algorithm put it together and summarized - minimizing number of MO. This approach will allow careful consideration most CP as it applies to dedicated MO.
Обычно функция упорядочения не вычисляется по какому-то специальному правилу, а содержится в каждом элементе в виде явной компоненты (поля). Её значение называют ключом элемента. Ключ в алгоритмах сортировки – единственная существенная компонента.
Эффективность алгоритма, реализующего тот или иной метод сортировки массивов, определяется двумя основными требованиями – экономичное использование памяти и быстродействие алгоритма. Первое требование означает, что переупорядочение элементов нужно выполнить на том же месте памяти; удобная мера быстродействия алгоритма получается при подсчёте числа С необходимых сравнений ключей и М пересылок элементов. Эти числа определяются некоторыми функциями от числа n сортируемых элементов.
Методы, сортирующие элементы на том же месте, можно разбить на 3 основных класса, в зависимости от лежащего в их основе принципа: сортировка вставками, сортировка выбором, сортировка обменом.
Определение. Макрооперацией мы будем называть функционально законченный фрагмент вычислительного процесса.
Выделение макроопераций из ВП обосновывается интуитивно понятным утверждением. Утверждение. Большое множество ВП может быть построено на основе небольшого числа МО. В применении к сортировкам это означает выделение МО из ВП как простых, так и эффективных сортировок, имея в виду в дальнейшем построение для каждой МО соответствующего фрагмента сети Петри, сборки фрагментов в общую сеть Петри для данного ВП и её моделирование на предмет получения безошибочной модели для конкретной сортировки. Простые сортировки
В работе [
По аналогии с [
Для моделей вводится базовое понятие «граница», разделяющая готовую и входную подпоследовательности. При этом используются уточнения: текущая, следующая и начальная границы. Граничным элементом является элемент, стоящий непосредственно за границей.
Во всех моделях рассматривается некое текущее состояние процесса сортировки и указывается новое положение границы, а также начальное, стартовое её положение. В понятие «модель» входит также способ организации процесса упорядочивания элементов массива, т.е. метод сортировки.
Рис. 1. Модели простых сортировок В методе простых вставок для текущего граничного элемента x ищется подходящее место в готовой подпоследовательности, для чего используется двойное неравенство: аj-1≤ x ≤ aj. Поскольку x может оказаться на первой позиции, а в этом случае отсутствует левая часть двойного неравенства, вводится фиктивный элемент a0, называемый «барьером». Для гарантированного попадания x на первую позицию принимают a0 = x.
В методе простого выбора ищется минимальный элемент am (minel) во входной подпоследовательности, который сравнивается с текущим граничным элементом ai. Если он оказывается меньшим по значению граничного элемента, am < ai, то они обмениваются местами.
В методе простого обмена (метод «пузырька») процесс протекает следующим образом. Сравнивается пара рядом стоящих элементов, начиная с конца последовательности. Если правый элемент пары оказывается меньше левого её элемента, aj < aj-1, то они обмениваются местами. Затем левый элемент уточнённой пары становится правым элементом новой пары элементов. Таким путём меньший по величине элемент продвигается влево, пока не встретит элемент с ещё меньшим значением. Тогда он останавливается перед ним и «передаёт ему эстафету». Элемент с наименьшим на данном проходе значением продвигается до граничного элемента. Ясно, что за один проход возможно перемещение нескольких элементов.
Во всех трёх методах после определения нового элемента готовой подпоследовательности граница передвигается вправо. Так проходит процесс до последнего элемента входной подпоследовательности. Стартовые положения границ для данных методов показаны на рисунке 1.
На рис. 2, 3, 4 подробно показаны схемы алгоритмов (СА), построенные в соответствии с рассмотренными моделями процессов сортировки. В частности, показаны счётчики итераций для внутренних и внешних циклов. Пунктиром во всех трёх схемах представлен внутренний цикл (тело внешнего цикла).
На основе СА проведен анализ процессов сортировки на предмет выделения МО для сортировок
выбором и обменом (для сортировок вставками такой анализ выполнен в [
Рис. 2. Схема алгоритма простых вставок
Приведём список МО для СА простых вставок из [
Рис. 3. Схема алгоритма для сортировки простым выбором Рис. 4. Схема алгоритма сортировки простыми обменами Из приведенных списков сортировок выделены общие для них МО: «Ввод массива», «Вывод массива», «Присваивание»; «Присваивание с вычислением», МО «Перемещение границы» (счётный цикл). Эффективные сортировки
Рассмотрим более сложные сортировки: Шелла, быструю и пирамидальную (рис. 5, 6) [
При построении СА для эффективных сортировок мы используем обобщённое представление блоков. А) Б) Рис. 5. Схема алгоритма сортировки Шелла (А) и алгоритма пирамидальной сортировки (Б)
Рис. 6. Схема алгоритма быстрой сортировки Приведём словесные описания СА (рис. 5, (А), 5, (Б), 6) и списки МО для эффективных сортировок. Сортировка Шелла Словесное описание 0. Ввод исходного массива. 1. Формирование списка шагов. 2. Главный цикл перебора шагов из списка. А) для данного шага h в цикле формируются h подсписков; Б) перебор подсписков. Для данного подсписка проводится сортировка вставками; В) производится сборка подсписков в общий список (массив).
3. Проверяется исчерпание списка. В случае положительного ответа алгоритм заканчивает работу и выводится результат. Иначе – переход на п. 2, где из списка выбирается следующий шаг. 1) МО «Ввод исходных данных» и МО «Вывод результатов»; 2) МО «Присваивание» для определения индекса и значения осевого элемента; 3) МО «Присваивание с вычислением» для определения изменения индекса осевого элемента; 4) МО «Сравнение» для сравнения осевого элемента с остальными элементами списка, а также левой и правой границ сортируемого списка; 5) МО «Обмен» для обмена местами двух элементов; 6) МО «Перемещение границы» (счётный цикл; граничным является осевой элемент); 7) МО "Разделение списка" (массива). Пирамидальная сортировка Словесное описание 0. Ввод исходного массива. 2. Главный цикл перебора шагов из списка.
1. Построение пирамиды – бинарного дерева, для которого значение каждого корня поддерева больше значений его обоих потомков
А) для данного шага i в цикле выполняется присоединение корня сформированной пирамиды к отсортированной последовательности;
Б) перестройка пирамиды, данные для нее берутся из оставшейся части неотсортированной последовательности; 3. Проверяется исчерпание списка. В случае положительного ответа алгоритм заканчивает работу и выводится результат. Иначе – переход на п. 2, где из списка выбирается следующий шаг. 1) МО «Ввод исходных данных» и МО «Вывод результатов»; 4) МО «Обмен элементов» листа поддерева и его корня; 6) МО «Присваивание» – непосредственно для самой вставки.
2) МО «Присваивание с вычислением» для определения индекса середины массива, требуется для построения полной (или близкой к полной) пирамиды; 3) МО «Поиск максимального элемента» при анализе соответствия листьев поддеревьев их корням; 5) МО «Перемещение границы» (счетный цикл) для определения места вставки элемента из корня пирамиды в отсортированную подпоследовательность; Систематизация МО
В работе выполнена сборка списков МО для каждой сортировки и проведен анализ МО на предмет их объединения в обобщенный список.
Общие МО: ввода, вывода, присваивания, присваивания с вычислением, перемещения границы. Частные МО: МО «Сравнить – выполнить» с вариантами - сравнить элементы – обменять (переставить) элементы; - сравнить особый элемент с текущим элементом – сдвинуть текущий элемент вправо (влево); - сравнить минимальный элемент с текущим элементом – присвоить минимальному элементу значение текущего элемента.
МО «Поиск особого элемента» с вариантами: - минимальный; - максимальный; - опорный (осевой) – выбор по правилу. МО «Обмен элементов» с вариантами: - пара рядом стоящих элементов; - граничный и текущий элементы; - граничный и особый элементы; - элементы в листе поддерева и в его корне. Обобщённые МО: - МО «Разделение списка (подсписка)»; - МО «Объединение подсписков». - МО «Поиск подходящего места» – это МО «Сравнить – сдвинуть» с конкретизацией; - МО «Частичное упорядочение массива» – это попарное сравнение и обмен в счётном цикле на текущем проходе массива; Заключение
В работе рассмотрены с единой позиции модели простых сортировок, в которых базовым является понятие «граница». Вычислительные процессы (ВП) для простых и избранных сложных (эффективных) сортировок представлены в виде схем алгоритмов. Из ВП этих сортировок выделены МО, которые собраны в соответствующие списки. Эти списки систематизированы путем объединения в общий список с последующей его минимизацией. Специфической для рассмотренных сортировок, как и следовало ожидать, является МО «Сравнить – переставить». Кроме того, для сложных сортировок специфической является МО "Формирование подсписков".
Приведенные модели и СА простых сортировок представляют самостоятельный интерес. Некоторые МО могут быть использованы и в других ВП, не только в процессах сортировок. Дальнейшего анализа требуют вопросы организации ввода-вывода, инициализации, рекурсии и др.