Трифонов Н.П._ В.Н. Пильщиков - _Практикум на ЭВМ_ (1108423), страница 3
Текст из файла (страница 3)
В методах сортировки обменами переставляются элементы неупорядоченных пар, т.е. таких пар, в которых левый элемент больше правого. В зависимости от порядка перебора пар различаются следующие методы.
а) МЕТОД ПУЗЫРЬКА. По очереди просматриваются пары соседних элементов (X1 и X2, X2 и X3, X3 и X4 и т.д.) и в неупорядоченных парах (Xi>Xi+1) переставляются элементы; в результате просмотра всей последовательности ее максимальный элемент окажется на своем окончательном месте - в конце. Далее аналогичная процедура применяется ко всем элементам последовательности, кроме последнего. (Замечание: если при очередном просмотре последовательности не было ни одной перестановки, то последовательность уже упорядочена и потому следует прекратить сортировку.)
б) ЧЕЛНОЧНАЯ СОРТИРОВКА (метод просеивания). Здесь также сравниваются пары 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 и т.д.
СОРТИРОВКА ПРОСТЫМ ВЫБОРОМ
В сортировке простым выбором находится минимальный (максимальный) элемент последовательности и он переставляется с первым (последним) элементом. Далее аналогичная процедура применяется ко всем элементам, кроме первого (последнего). И так далее.
МЕТОД ШЕЛЛА
Пусть 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]).
Различаются следующие варианты сортировки слиянием.
а) ПРОСТОЕ СЛИЯНИЕ. Считается, что вначале отрезки состоят только из одного элемента, и они сливаются в отрезки из двух элементов (из X1 и X2, из X3 и X4, ...), которые переносятся в массив Y. На втором этапе соседние двухэлементные отрезки (Y1, Y2 и Y3, Y4; Y5, Y6 и Y7, Y8; ...) объединяются в отрезки из 4 элементов, которые записываются в массив X. На третьем этапе строятся отрезки из 8 элементов, и они заносятся в массив Y, и т.д.
б) ЕСТЕСТВЕННОЕ СЛИЯНИЕ. Берутся наиболее длинный (по неубыванию) отрезок в начале массива X и наиболее длинный (также по неубыванию, но при просмотре справа налево) отрезок в конце массива, и они сливаются в один отрезок, который записывается в начало массива Y. Затем сливаются следующие максимально длинные отрезки с обоих концов, и полученный отрезок записывается (справа налево) в конец массива Y. Третьи по порядку отрезки после слияния записываются снова в начало Y (вслед за первым объединенным отрезком), четвертые - в конец Y (перед вторым объединенным отрезком) и т.д. Первый этап сортировки оканчивается, когда все элементы из X будут перенесены в массив Y. На втором этапе применяется та же процедура, только массивы X и Y меняются ролями. И так далее.
Замечание: в обоих вариантах следует учитывать, что в конце концов упорядо-ченные элементы должны оказаться в массиве X.
ЗАДАНИЕ 4. ЯЗЫК ПАСКАЛЬ.
ИНТЕРФЕЙС ПРОГРАММЫ СОРТИРОВКИ.
ПОСТАНОВКА ЗАДАЧИ
Требуется дополнить программу сортировки, реализованную в задании 3, подсистемой диалогового взаимодействия с пользователем (интерфейсом), которая с помощью экранных окон, меню и других средств упрощает общение пользователя с этой программой. Работу с экраном подсистема должна осуществлять в текстовом режиме.
Объединенная система должна предусматривать следующие возможности.
- Пользователь должен иметь возможность выбрать из нескольких предъявленных ему методов сортировки тот метод, которым затем будут упорядочиваться последовательности.
- Пользователь должен иметь возможность задавать свою длину последователь-ностей, которые будут упорядочиваться выбранным методом.
- В системе должна быть предусмотрена возможность работы в двух режимах - отладки и счета. В режиме отладки пользователь сам вводит элементы (даты) последо-вательности, которая должна быть упорядочена, а в ответ система демонстрирует пошаговую работу процедуры сортировки для этой последовательности (это нужно для показа правильности работы процедуры). В режиме счета система должна работать так же, как и в задании 3: должна сформировать несколько последовательностей заданной длины, отсортировать их и вывести на экран таблицу результатов.
- Система должна позволять пользователю менять сделанный им ранее выбор (метода, длины или режима) и должна повторять свою работу при новом выборе.
- При вводе длины и элементов последовательности пользователь должен иметь возможность редактировать вводимую информацию.
ВОЗМОЖНЫЕ СЦЕНАРИИ РАБОТЫ С СИСТЕМОЙ
Ниже описаны два возможных сценария работы пользователя с системой. Любой из них можно взять за основу и со своими изменениями реализовать в задании.
Сценарий 1.
Этап 1. Выбор метода.
Работа системы начинается с очистки экрана и показа на нем списка названий различных (не менее 4-5) методов сортировки. Пользователь выбирает один из них либо прекращает работу с системой.
Этот список должен быть реализован в виде вертикального меню - в виде окна (закрашенного своим цветом прямоугольника), в котором друг под другом выписаны названия методов (см. рис. 1). Вначале должно быть выделено (высвечено особым цветом) первое из этих названий, а затем при нажатии пользователем клавиши со стрелкой вниз или вверх система должна выделить следующее или предыдущее (по кругу) название, сняв выделение текущего названия.
Одновременно с меню методов на экране (в его нижней строке) должен высвечиваться текст, подсказывающий пользователю, что он должен сейчас делать, какие клавиши может нажимать и что они означают. Подсказка может быть, например, такой:
ВЫБЕРИТЕ МЕТОД: ↓,↑–сдвиг Enter-выбор Esc-выход
Нажатие пользователем клавиши Enter означает, что он выбрал тот метод, название которого сейчас выделено. (Замечание: поскольку в системе реализовано лишь два метода сортировки, то при выборе нереализованного метода система должна как-то сообщить об этом, например звуковым сигналом или выдачей сообщения "Метод не реализован", и позволить пользователю выбрать иной метод. Желательно реализованные методы как-то пометить, например звездочкой.)
Нажатие клавиши Esc означает конец работы с системой.
На этом этапе система не должна реагировать на другие клавиши, а курсор должен быть невидимым.
Этап 2. Выбор режима.
После того как пользователь выбрал метод сортировки, система спрашивает его о режиме дальнейшей работы - режиме отладки или режиме счета. Пользователь выбирает нужный режим, но может и вернуться на предыдущий этап. В нижней строке экрана должна высвечиваться соответствующая подсказка.
Запрос режима может быть реализован следующим образом. В свободной части экрана появляется окно с текстом "РЕЖИМ: ОТЛАДКА" (см. рис. 1). Если пользователь нажимает клавишу пробела, тогда слово "ОТЛАДКА" заменяется на слово "СЧЕТ"; при новом нажатии этой клавиши снова появляется слово "ОТЛАДКА" и т.д. Нажатие клавиши Enter означает выбор того режима, название которого указано сейчас в окне.
Допустимо также нажатие клавиши Esc, что означает отказ от выбора режима и возврат на предыдущий этап (с удалением окна режима и восстановлением подсказки, соответствующей предыдущему этапу). На иные клавиши система в это время не должна реагировать. Курсор должен быть невидимым.
Этап 3. Выбор длины.
При любом выбранном режиме система далее спрашивает у пользователя, последова-тельности какой длины он желает упорядочивать. В режиме счета длина может меняться от 1 до 100, а в режиме отладки - от 1 до 15.
Запрос длины можно реализовать так. На экране появляется окно с текстом "ДЛИНА (<=15): " (или "<=100" в режиме счета), за которым следует "поле ввода" - 3-4 позиции, в которые пользователь будет вводить длину (система не должна разрешать ему выходить за рамки этого поля). Курсор на этом этапе видим и показывает позицию, в которую пользователь вводит очередной символ (вначале это первая позиция поля ввода, а затем курсор сдвигается вправо по мере ввода числа). В нижней строке экрана должна высвечиваться соответствующая подсказка. Экран в этот момент может выглядеть так:
| ┌─────────────────────┐ ┌──────────────────┐ │ методы сортировки: │ │ режим: отладка │ │ Бинарные вставки │ └──────────────────┘ │ Метод пузырька (*)│ │ Простой выбор │ ┌──────────────────┐ │ МЕТОД ШЕЛЛА (*) │ │ длина (<=15): _ │ │ Естест.слияние │ └──────────────────┘ └─────────────────────┘ СТРОКА С ПОДСКАЗКОЙ |
Рис. 1
При вводе числа (до нажатия клавиши Enter) пользователь должен иметь возможность вносить изменения в набранный текст. Рекомендуется использовать следующие клавиши для редактирования вводимого текста:
← , → - перемещение курсора на одну позицию влево или вправо (без выхода за границы поля ввода)
Del - удаление символа, на который указывает курсор (со сдвигом влево на одну позицию правой части уже набранного текста)
Backspace - удаление символа слева от курсора (если только курсор не находится в начале поля ввода) со сдвигом на одну позицию влево самого курсора и правой части уже набранного текста
Ins - переключение с режима вставки на режим замены или наоборот (начальный режим - вставка)
(Замечание. В режиме замены введенный символ заменяет на экране тот символ, на который указывает курсор, а в режиме вставки часть текста (от курсора и вправо) сдвигается на одну позицию вправо и в освободившуюся позицию вставляется введенный символ. Далее (в любом режиме) курсор перемещается на одну позицию вправо, если только он не находится в конце поля ввода.)
При вводе длины нажатие клавиши Enter (при любом положении курсора) означает, что ввод окончен. Система должна считать набранные цифры и перевести их в соответствующую числовую величину. Если число набрано верно и не выходит за определенный диапазон, то система переходит к следующему, четвертому, этапу своей работы, а иначе она должна каким-то образом сообщить об ошибке и предоставить пользователю возможность исправить ранее набранную длину.
Помимо указанных выше клавиш система должна реагировать и на клавишу Esc, нажатие которой означает отказ от ввода и возврат системы на предыдущий этап (с удалением окна длины и восстановлением прежней подсказки).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
