Информатика. Курс лекций. Громов Ю.Ю - 92 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

Здесь N – счетчик, параметр ДлинаСписка – количество элементов в списке, а точки указывают место, где должна
располагаться составленная нами выше процедура.
Полный текст программы сортировки на языке псевдокода приведен на рис. 4.11. Не вдаваясь в подробности, можно
сказать, что эта программа сортирует список, многократно повторяя следующие действия: "Элемент извлекается из списка, а
затем вставляется на надлежащее ему место". Именно по причине многократного повторения вставки элементов в список
данный алгоритм получил название сортировки методом вставки (insertion sort).
Обратите внимание, что представленная на рис. 4.11 структура содержит Цикл, помещенный внутрь другого цикла.
Внешний цикл представлен первой инструкцией while, а внутренний цикл – второй инструкцией while. Каждое выполне-
ние тела внешнего цикла приводит к тому, что внутренний цикл инициализируется и выполняется до тех пор, пока не будет
выполнено условие его окончания. Таким образом, однократное выполнение тела внешнего цикла будет сопровождаться
многократным выполнением тела внутреннего цикла.
Рис. 4.11. Алгоритм сортировки методом вставки, написанный на псевдокоде
При инициализации управления внешним циклом начальное значение счетчика N устанавливается с помощью инструк-
ции
N ← 2;
Операция модификации этого цикла включает увеличение значения счетчика N в конце тела цикла с помощью инст-
рукции
N ← N + 1.
Условие окончания внешнего цикла выполняется, когда значение счетчика N превысит длину сортируемого списка.
Управление внутренним циклом инициализируется, когда опорный элемент извлекается из списка и в нем образуется
пустое место. Операция модификации включает перемещение расположенных выше элементов на пустое место вниз, в ре-
зультате чего свободное место перемещается вверх по списку. Условие окончания выполняется, когда пустое место или на-
ходится непосредственно под именем, которое по алфавиту размещается выше опорного значения, или же достигает верхней
позиции списка.
Вопросы для самопроверки
1. Преобразуйте показанную на рис. 4.6 процедуру последовательного поиска так, чтобы она могла работать с неот-
сортированными списками.
2. Перепишите приведенную ниже программу на псевдокоде так, чтобы в ней использовались повторяющиеся инструкции
repeat-until.
Z ← 0;
X ← 1;
while (X < 6) do
{Z ← Z + X;
X ← X + 1}
3. Предположим, что процедура сортировки методом вставки, представленная на рис 4.11, была применена к списку
George, Cheryl, Alice и Bob. Опишите, как будет выглядеть список каждый раз по окончании выполнения тела внешней
структуры while.
4. Почему не следует заменять фразу "по алфавиту размещается ниже" в инструкции while на рис. 4.11 на
фразу "по алфавиту размещается ниже или эквивалентно"?
5. Вариантом алгоритма сортировки методом вставки является выборочная сортировка (selection sort). Каждый раз вы-
бирается наименьший элемент списка и помещается на первое место. Затем выбирается наименьший элемент из оставшихся
элементов списка и помещается на второе место в списке. Многократно выбирая наименьший элемент из оставшейся части
списка и перемещая его вперед, мы увеличиваем отсортированную часть списка, находящуюся вначале, тогда как его конеч-
ная часть, состоящая из неотсортированных элементов, сжимается. С помощью нашего псевдокода напишите процедуру
сортировки списка с использованием алгоритма выборочной сортировки, аналогичную процедуре, представленной на рис.
4.11.
6. Другой известный алгоритм сортировки – сортировка методом пузырька (bubble sort). Он основан на процессе по-
вторяющегося сравнения двух стоящих рядом имен и перестановки их местами, если они находились относительно друг
procedure Сортировка (Список)
N ← 2;
while (N ≤ ДлинаСписка) do
{выбрать N-й элемент как ОпорныйЭлемент;
переместить ОпорныйЭлемент во временное
хранилище,
оставив в списке пустое место;
while (над пустым местом есть имя, и оно >
ОпорныйЭлемент) do
{переместить имя, находящееся над пустым
местом, вниз,
оставив в его прежней позиции пустое
место}
поместить ОпорныйЭлемент на пустое место в
списке;
N ← N + 1}

Страницы