Базовые
структуры
языков программирования
Структура
Паскаль - программы
< 5; 1.2 >
-6.8; 'A' < 'C'; true > false; MO > TH
Операторы
процедур. Ввод/вывод
информации
СТРУКТУРНЫЕ
ОПЕРАТОРЫ.
ОРГАНИЗАЦИЯ
ВЕТВЛЕНИЙ И
ЦИКЛОВ
Организация
циклов. Операторы
повторения
ОРГАНИЗАЦИЯ
ПОДПРОГРАММ.
ПРОЦЕДУРЫ И
ФУНКЦИИ
Функции
пользователя.
Рекурсивные
функции
МАССИВЫ.
ДАННЫЕ ТИПА
ARRAY
Способы
работы с массивами
Массивы
литер
Процедура
STR(преобразование
в строку)
Печать
множеств
Оператор
WITH
Определение
и описание
файла
Основные
приемы работы
с файлами
ССЫЛОЧНЫЙ
ТИП. ПЕРЕМЕННЫЕ
С УКАЗАТЕЛЯМИ
Создание
динамических
переменных.
Процедура NEW
Операции
над указателями
Действия
над динамическими
переменными
Заполнить
поля ELEM значениями
UKSTR^.ELEM:='P';
ПОНЯТИЕ ОБ
ИНФОРМАЦИИ.
ДАННЫЕ. СТРУКТУРЫ
ДАННЫХ
Прямой
выбор
Массив
дан случайным
образом
СТРУКТУРЫ
ПОСЛЕДОВАТЕЛЬНОГО
ДОСТУПА. ЛИНЕЙНЫЕ
СПИСКИ
Стек
Общие
приемы работы
с линейными
списками
ДЕРЕВЬЯ
Основные операции
над деревьями
Некоторые
дополнительные
возможности
работы с динамическими
структурами
Навигация
Прямой выбор
Алгоритмический язык Паскаль
274963
знака
85
таблиц
0
изображений
13.2 Прямой выбор
Суть метода состоит в том, что среди всех элементов массива выбирается наименьший и ставится на первое место, а элемент, занимавший первое место, перемещается на место наименьшего. Затем среди оставшихся элементов от второго до N-го проводится та же операция, а именно: среди элементов массива от второго до N-го выбирается наименьший и перемещается на второе место, а элемент, стоящий на втором месте, занимает место наименьшего.
Эта идея реализуется в виде вложенных циклов: внешний - по I от 1 до N-1; внутренний - по J от I+1 до N.
ОБЩАЯ СХЕМА ПРОГРАММЫ:
for I:=1 to N-1 do
begin
¦ {Запоминание индекса и самого I-го элемента}
¦ for J:=I+1 to N do
¦ begin
¦ {Поиск минимального элемента от I+1 до N}
¦ end;
¦ {Перестановка I-го и минимального элементов}
end.
ОБЩИЙ ВИД ПРОГРАММЫ:
procedure SELECTION (var MM:MAS);
var I,J,K,X: integer;
begin
¦ for I:= 1 to N-1 do
¦ begin
¦ ¦ { Это тело внешнего цикла }
¦ ¦ K:= I; X:= MM[I];
¦ ¦ { Внутренний цикл - поиск MIN элемента }
¦ ¦ for J:= I+1 to N do
¦ ¦ if X > MM[J] then
¦ ¦ begin
¦ ¦ ¦ { Запоминание номера и значения
¦ ¦ ¦ минимального элемента }
¦ ¦ ¦ X:= MM[J];
¦ ¦ ¦ K:= J;
¦ ¦ end;
¦ ¦ { Минимальный и I-й элементы меняются местами}
¦ ¦ MM[K]:= MM[I]; MM[I]:= X;
¦ end;
end.
Проследим работу этой программы на следующем примере:
I=0
| -3 | 2 | 4 | 1 | 6 | 3 |
® исходный массив
I=1
| -3 | 2 | 4 | 1 | 6 | 3 |
® 1-й шаг: ничего не происходит, т.к. минимальный элемент на своем месте
I=2
| -3 | 1 | 4 | 2 | 6 | 3 |
® 2-й шаг: 2-й и 4-й поменялись местами
I=3
| -3 | 1 | 2 | 4 | 6 | 3 |
® 3-й шаг: 3-й и 4-й поменялись местами
I=4
| -3 | 1 | 2 | 3 | 6 | 4 |
® 4-й шаг: 4-й и 6-й поменялись местами
I=5
| -3 | 1 | 2 | 3 | 4 | 6 |
® 5-й шаг: 5-й и 6-й поменялись местами
Всего N-1=5 шагов. Часть из них результативна (2,3,4,5), а первый шаг никаких перестановок не производит. Отметим, однако, что даже при нерезультативных ходах все циклы работают до конца и за время сортировки внутренний цикл выполнится N(N-1)/2 раз.
13.3 Прямой обмен (метод пузырька, всплытие)
Суть его заключается в том, что в отличие от первых двух методов, где просмотр массива шел по увеличению индекса I, т.е. от начала массива к концу, здесь производится проход от конца массива к началу до I-го элемента, и каждый раз, если А[J-1] > А[J], они меняются местами.
В этом методе также есть два вложенных цикла: внешний цикл поидет от 2 до N, а внутренний по J - от N до I:
for I:= 2 to N do
for J:= N downto I do
{ Обмен местами (всплытие) более легкого элемента }
end;
end.
ОБЩИЙ ВИД ПРОГРАММЫ:
procedure BUBLESORT (var MM: MAS);
var I,J,X: integer;
begin
¦ for I:=2 to N do
¦ for J:= N downto I do
¦ if MM[J-1] > MM[J] then
¦ begin
¦ ¦ X:= MM[J-1];
¦ ¦ MM[J-1]:= MM[J];
¦ ¦ MM[J]:= X
end;
end.
Работу программы иллюстрирует пример с тем же исходным массивом, что и ранее:
| I=2 | I=3 | ||||||||||||||
| J=6 | -3 | 2 | 4 | 1 | 3 | 6 | J=6 | -3 | 1 | 2 | 4 | 3 | 6 | ||
| J=5 | -3 | 2 | 4 | 1 | 3 | 6 | J=5 | -3 | 1 | 2 | 3 | 4 | 6 | ||
| J=4 | -3 | 2 | 1 | 4 | 3 | 6 | J=4 | -3 | 1 | 2 | 3 | 4 | 6 | ||
| J=3 | -3 | 1 | 2 | 4 | 3 | 6 | J=3 | -3 | 1 | 2 | 3 | 4 | 6 | ||
| J=2 | -3 | 1 | 2 | 4 | 3 | 6 |
Все остальные обработки при I = 4, 5, 6 идут впустую, т.к. массив уже упорядочен. В других ситуациях может случиться так, что сортировка закончится только на последнем цикле.
13.4 Сравнительная характеристика методов
Все три метода простой сортировки далеки от идеала, однако в некоторых ситуациях их эффективность может оказаться различной. В связи с этим можно выделить следующие случаи:
1. Массив уже отсортирован (но мы не знаем об этом).
Здесь самым быстрым и эффективным следует считать метод прямого включения, т.к. никаких передвижек не произойдет (за счет цикла WHILE, который формально просто не будет работать), а останется только проход по внешнему циклу.
2. Исходный массив упорядочен по убыванию.
Здесь самым лучшим методом является прямой выбор, т.к. вся работа будет проделана за половину ходов (проход до середины):
ПРИМЕР:
| 1 шаг: | 8 | 6 | 4 | 2 | 0 | 2 шаг: | 0 | 6 | 4 | 2 | 8 | ||||
| Результат: | 0 | 2 | 4 | 6 | 8 | ||||||||||
Похожие работы
... .....-46.780 Program Prim24; Var r1,r2:real; BEGIN r1:=-46.78; r2:=-46.78; writeln('r1=',r1:12:3,' r2=',r2:9:4); writeln('_______________________________'); readln; END. 6. Массивы 6. 1. Описание массивов В языке Паскаль можно обрабатывать не только отдельные переменные, но и их совокупности. Одной из таких совокупностей (структурированных) данных является массив. ...
... . Объясните, для чего служат разрешения и привилегии в Windows NT. Зав. кафедрой -------------------------------------------------- Экзаменационный билет по предмету СИСТЕМНОЕ ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ Билет № 22 Перечислите возможности и инструменты системы программирования Microsoft Developer Studio. Укажите для чего предназначается буфер в системах ввода-вывода, ...
... с внешнего устройства (из входного файла) в основную память ЭВМ, операция вывода - это пересылка данных из основной памяти на внешнее устройство (в выходной файл). Файлы на внешних устройствах часто называют физическими файлами. Их имена определяются операционной системой. В программах на языке Паскаль имена файлов задаются с помощью строк. Например, имя файла на диске может иметь вид: ...
0 комментариев