Задания практикума на ЭВМ (1110686), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

4. Абрамов В.Г., Трифонов Н.П., Трифонова Г.Н. Введение в язык Паскаль. - М.: Наука, 1988.

5. Епанешников А.М., Епанешников В.А. Программирование в среде Turbo Pascal 7.0 - М.: "ДИАЛОГ-МИФИ", 2000.

КРАТКОЕ ОПИСАНИЕ МЕТОДОВ СОРТИРОВКИ

СОРТИРОВКА ВСТАВКАМИ

Идея методов сортировки вставками состоит в том, что в ранее упорядоченную подпоследовательность X₁, X₂, ..., X_k-1 вставляется X_k так, чтобы упорядоченными оказались уже k первых элементов исходной последовательности. В зависимости от способа поиска места для элемента q=X_k различаются следующие методы.

а) ПРОСТЫЕ ВСТАВКИ. Если q<X_k-1, то величина q по очереди сравнивается с X_k-1, X_k-2, ..., пока не будет найдена такая пара элементов X_i-1 и X_i, что X_i-1≤q<X_i. Это означает, что местом для q является i-я позиция. Поэтому элементы X_i, …, X_k-1 сдвигаются на одну позицию вправо и в освободившуюся i-ю позицию вставляется q.

б) БИНАРНЫЕ ВСТАВКИ. Величина q сравнивается со средним элементом подпоследовательности X₁, X₂, ..., X_k-1. Если q меньше этого элемента, то место для q ищется тем же способом в левой половине подпоследовательности, иначе - в правой половине. Когда место для q будет найдено, правые (от этого места) элементы сдвигаются на одну позицию вправо, а в освободившуюся позицию вставляется q.

СОРТИРОВКА ОБМЕНАМИ

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

а) МЕТОД ПУЗЫРЬКА. По очереди просматриваются пары соседних элементов (X₁ и X₂, X₂ и X₃, X₃ и X₄ и т.д.) и в неупорядоченных парах (X_i>X_i+1) переставляются элементы; в результате просмотра всей последовательности ее максимальный элемент окажется на своем окончательном месте - в конце. Далее аналогичная процедура применяется ко всем элементам последовательности, кроме последнего. (Замечание: если при очередном просмотре последовательности не было ни одной перестановки, то последовательность уже упорядочена и потому следует прекратить сортировку.)

б) ЧЕЛНОЧНАЯ СОРТИРОВКА (метод просеивания). Здесь также сравниваются пары X₁ и X₂, X₂ и X₃ и т.д., но только до обнаружения неупорядоченной пары X_k>X_k+1. В этом случае осуществляется "движение назад": сравниваются и переставляются пары X_k+1 и X_k, X_k и X_k-1 и т.д. до тех пор, пока X_k+1 не попадет на свое место, т.е. пока не окажется упорядоченной подпоследовательность из k+1 первых элементов. Далее возобновляется "движение вперед": сравниваются пары X_k+1 и X_k+2, X_k+2 и X_k+3 и т.д.

СОРТИРОВКА ПРОСТЫМ ВЫБОРОМ

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

МЕТОД ШЕЛЛА

Пусть k - целое от 1 до n/2. Независимо друг от друга упорядочиваются (одним из описанных выше методов, например, простых вставок) подпоследовательности из элементов, отстоящих друг от друга на k позиций:

X_i, X_i+k, X_i+2k, X_i+3k, ... (i=1, 2, ..., k)

Затем k уменьшается и процесс повторяется заново. Последний шаг обязательно должен быть выполнен при k=1.

Значение k можно менять разными способами, один из них таков: вначале k равно (целой части от) n/2, а затем k каждый раз уменьшается вдвое.

БЫСТРАЯ СОРТИРОВКА

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

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

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

СОРТИРОВКА СЛИЯНИЕМ

Основная идея такой сортировки - разделить последовательность на уже упорядоченные подпоследовательности (назовем их "отрезками") и затем объединять эти отрезки во все более длинные упорядоченные отрезки, пока не получится единая упорядоченная последовательность. Отметим, что при этом необходима дополнительная память (массив Y[1..n]).

Различаются следующие варианты сортировки слиянием.

а) ПРОСТОЕ СЛИЯНИЕ. Считается, что вначале отрезки состоят только из одного элемента, и они сливаются в отрезки из двух элементов (из X₁ и X₂, из X₃ и X₄, ...), которые переносятся в массив Y. На втором этапе соседние двухэлементные отрезки (Y₁, Y₂ и Y₃, Y₄; Y₅, Y₆ и Y₇, Y₈; ...) объединяются в отрезки из 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

Характеристики

Список файлов учебной работы