Н.П. Трифонов, В.Н. Пильщиков - Задания практикума на ЭВМ (972293), страница 3
Текст из файла (страница 3)
Это означает, что местом для q является i-я позиция. Поэтомуэлементы Xi, …, Xk − 1 сдвигаются на одну позицию вправо и в освободившуюся i-ю позицию вставляется q.2) БИНАРНЫЕ ВСТАВКИ. Величина q сравнивается со средним элементомподпоследовательности X1, X2, ..., Xk − 1. Если q меньше этого элемента, то место для q ищется тем же способом в левой половине подпоследовательности,иначе - в правой половине. Когда место для q будет найдено, правые (от этого места) элементы сдвигаются на одну позицию вправо, а в освободившуюся позицию вставляется q.СОРТИРОВКА ОБМЕНАМИВ методах сортировки обменами переставляются элементы неупорядоченных пар, т.е.таких пар, в которых левый элемент больше правого.
В зависимости от порядка перебора пар различаются следующие методы.1) МЕТОД ПУЗЫРЬКА. По очереди просматриваются пары соседних элементов (X1 и X2, X2 и X3, X3 и X4 и т.д.) и в неупорядоченных парах (Xi > Xi+1) переставляются элементы; в результате просмотра всей последовательности еемаксимальный элемент окажется на своем окончательном месте - в конце.Далее аналогичная процедура применяется ко всем элементам последовательности, кроме последнего. (Замечание: если при очередном просмотрепоследовательности не было ни одной перестановки, то последовательностьуже упорядочена и потому следует прекратить сортировку.)2) ЧЕЛНОЧНАЯ СОРТИРОВКА (метод просеивания).
Здесь также сравниваются пары X1 и X2, X2 и X3 и т.д., но только до обнаружения неупорядоченнойпары Xk > Xk+1. В этом случае осуществляется «движение назад»: сравниваются и переставляются пары Xk + 1 и Xk, Xk и Xk − 1 и т.д. до тех пор, пока Xk + 1не попадет на свое место, т.е. пока не окажется упорядоченной подпоследовательность из k + 1 первых элементов. Далее возобновляется «движениевперед»: сравниваются пары Xk + 1 и Xk + 2, Xk + 2 и Xk + 3 и т.д.СОРТИРОВКА ПРОСТЫМ ВЫБОРОМВ сортировке простым выбором находится минимальный (максимальный) элемент последовательности и он переставляется с первым (последним) элементом. Далее аналогичная процедура применяется ко всем элементам, кроме первого (последнего).
И такдалее.11Трифонов Н.П., Пильщиков В.Н. Практикум на ЭВММЕТОД ШЕЛЛАПусть k — целое от 1 до n/2. Независимо друг от друга упорядочиваются (одним изописанных выше методов, например, простых вставок) подпоследовательности из элементов, отстоящих друг от друга на k позиций:Xi, Xi + k, Xi + 2k, Xi + 3k, ... (i = 1, 2, ..., k)Затем k уменьшается и процесс повторяется заново.
Последний шаг обязательно должен быть выполнен при k = 1.Значение k можно менять разными способами, один из них таков: вначале k равно (целой части от) n/2, а затем k каждый раз уменьшается вдвое.БЫСТРАЯ СОРТИРОВКАВыбирается некоторый элемент (например, средний) и все элементы последовательности переставляются так, чтобы выбранный элемент оказался на своем окончательномместе, т.е. чтобы слева от него были только меньшие или равные ему элементы, а справа — только большие или равные. Затем этот же метод применяется к левой и правойчастям последовательности, на которые ее разделил выбранный элемент. (Замечание:если в части оказалось два-три элемента, то упорядочивать ее следует более простымспособом.)Требуемая перестановка элементов выполняется так.
Выбранный элемент копируется внекоторую переменную q. Последовательность просматривается слева направо, пока невстретится элемент, больший или равный q, а затем просматривается справа налево доэлемента, меньшего или равного q. Оба этих элемента меняются местами, после чегопросмотры с обоих концов последовательности продолжаются со следующих элементов, и т.д. В итоге выбранный элемент окажется в той позиции, где просмотры сошлись, это и есть его окончательное место.Быструю сортировку можно реализовать рекурсивно и нерекурсивно. Во втором случаеграницы одной из двух частей (лучше - более длинной), на которые выбранный элементразделил последовательность, запоминаются в стеке, а другая часть упорядочиваетсяописанным способом.
После ее упорядочения из стека извлекаются границы первойчасти, и теперь уже она упорядочивается.СОРТИРОВКА СЛИЯНИЕМОсновная идея такой сортировки — разделить последовательность на уже упорядоченные подпоследовательности (назовем их «отрезками») и затем объединять эти отрезкиво все более длинные упорядоченные отрезки, пока не получится единая упорядоченная последовательность. Отметим, что при этом необходима дополнительная память(массив Y [1..n]).Различаются следующие варианты сортировки слиянием.1) ПРОСТОЕ СЛИЯНИЕ. Считается, что вначале отрезки состоят только из одного элемента, и они сливаются в отрезки из двух элементов (из X1 и X2, из X3и X4, ...), которые переносятся в массив Y.
На втором этапе соседние двухэлементные отрезки (Y1, Y2 и Y3, Y4; Y5, Y6 и Y7, Y8; ...) объединяются в отрезкииз 4 элементов, которые записываются в массив X. На третьем этапе строятсяотрезки из 8 элементов, и они заносятся в массив Y, и т.д.2) ЕСТЕСТВЕННОЕ СЛИЯНИЕ. Берутся наиболее длинный (по неубыванию)отрезок в начале массива X и наиболее длинный (также по неубыванию, нопри просмотре справа налево) отрезок в конце массива, и они сливаются в12Методическое пособиеодин отрезок, который записывается в начало массива Y.
Затем сливаютсяследующие максимально длинные отрезки с обоих концов, и полученный отрезок записывается (справа налево) в конец массива Y. Третьи по порядку отрезки после слияния записываются снова в начало Y (вслед за первым объединенным отрезком), четвертые — в конец Y (перед вторым объединеннымотрезком) и т.д.
Первый этап сортировки оканчивается, когда все элементыиз X будут перенесены в массив Y. На втором этапе применяется та же процедура, только массивы X и Y меняются ролями. И так далее.Замечание: в обоих вариантах следует учитывать, что в конце концов упорядоченныеэлементы должны оказаться в массиве X.13Трифонов Н.П., Пильщиков В.Н. Практикум на ЭВМЗадание 4. ЯЗЫК ПАСКАЛЬ. ИНТЕРФЕЙСПРОГРАММЫ СОРТИРОВКИ.4.1. ПОСТАНОВКА ЗАДАЧИТребуется дополнить программу сортировки, реализованную в задании 3, подсистемойдиалогового взаимодействия с пользователем (интерфейсом), которая с помощью экранных окон, меню и других средств упрощает общение пользователя с этой программой. Работу с экраном подсистема должна осуществлять в текстовом режиме.Объединенная система должна предусматривать следующие возможности.— Пользователь должен иметь возможность выбрать из нескольких предъявленныхему методов сортировки тот метод, которым затем будут упорядочиваться последовательности.— Пользователь должен иметь возможность задавать свою длину последовательностей, которые будут упорядочиваться выбранным методом.— В системе должна быть предусмотрена возможность работы в двух режимах —отладки и счета.
В режиме отладки пользователь сам вводит элементы (даты)последовательности, которая должна быть упорядочена, а в ответ система демонстрирует пошаговую работу процедуры сортировки для этой последовательности (это нужно для показа правильности работы процедуры). В режиме счетасистема должна работать так же, как и в задании 3: должна сформировать несколько последовательностей заданной длины, отсортировать их и вывести наэкран таблицу результатов.— Система должна позволять пользователю менять сделанный им ранее выбор(метода, длины или режима) и должна повторять свою работу при новом выборе.— При вводе длины и элементов последовательности пользователь должен иметьвозможность редактировать вводимую информацию.4.2.
ВОЗМОЖНЫЕ СЦЕНАРИИ РАБОТЫ С СИСТЕМОЙНиже описаны два возможных сценария работы пользователя с системой. Любой изних можно взять за основу и со своими изменениями реализовать в задании.Сценарий 1.Этап 1. Выбор метода.Работа системы начинается с очистки экрана и показа на нем списка названий различных (не менее 4-5) методов сортировки. Пользователь выбирает один из них либо прекращает работу с системой.Этот список должен быть реализован в виде вертикального меню — в виде окна (закрашенного своим цветом прямоугольника), в котором друг под другом выписаны названия методов (см.
рис. 1). Вначале должно быть выделено (высвечено особым цветом) первое из этих названий, а затем при нажатии пользователем клавиши со стрелкойвниз или вверх система должна выделить следующее или предыдущее (по кругу) название, сняв выделение текущего названия.14Методическое пособиеОдновременно с меню методов на экране (в его нижней строке) должен высвечиватьсятекст, подсказывающий пользователю, что он должен сейчас делать, какие клавишиможет нажимать и что они означают. Подсказка может быть, например, такой:ВЫБЕРИТЕ МЕТОД: ↓,↑–сдвиг Enter-выбор Esc-выходНажатие пользователем клавиши Enter означает, что он выбрал тот метод, название которого сейчас выделено. (Замечание: поскольку в системе реализовано лишь два методасортировки, то при выборе нереализованного метода система должна как-то сообщитьоб этом, например звуковым сигналом или выдачей сообщения «Метод не реализован»и позволить пользователю выбрать иной метод.
Желательно реализованные методыкак-то пометить, например звездочкой.)Нажатие клавиши Esc означает конец работы с системой.На этом этапе система не должна реагировать на другие клавиши, а курсор долженбыть невидимым.Этап 2. Выбор режима.После того как пользователь выбрал метод сортировки, система спрашивает его о режиме дальнейшей работы — режиме отладки или режиме счета.
Пользователь выбирает нужный режим, но может и вернуться на предыдущий этап. В нижней строке экранадолжна высвечиваться соответствующая подсказка.Запрос режима может быть реализован следующим образом. В свободной части экранапоявляется окно с текстом «РЕЖИМ: ОТЛАДКА» (см. рис. 1). Если пользователь нажимает клавишу пробела, тогда слово «ОТЛАДКА» заменяется на слово «СЧЕТ»; приновом нажатии этой клавиши снова появляется слово «ОТЛАДКА» и т.д. Нажатие клавиши Enter означает выбор того режима, название которого указано сейчас в окне.Допустимо также нажатие клавиши Esc, что означает отказ от выбора режима и возвратна предыдущий этап (с удалением окна режима и восстановлением подсказки, соответствующей предыдущему этапу).
На иные клавиши система в это время не должна реагировать. Курсор должен быть невидимым.Этап 3. Выбор длины.При любом выбранном режиме система далее спрашивает у пользователя, последовательности какой длины он желает упорядочивать. В режиме счета длина может меняться от 1 до 100, а в режиме отладки — от 1 до 15.Запрос длины можно реализовать так. На экране появляется окно с текстом «ДЛИНА(<=15): » (или «<=100» в режиме счета), за которым следует «поле ввода» — 3-4 позиции, в которые пользователь будет вводить длину (система не должна разрешать емувыходить за рамки этого поля). Курсор на этом этапе видим и показывает позицию, вкоторую пользователь вводит очередной символ (вначале это первая позиция поля ввода, а затем курсор сдвигается вправо по мере ввода числа). В нижней строке экранадолжна высвечиваться соответствующая подсказка.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
