Прямой выбор

Алгоритмический язык Паскаль
Базовые структуры языков программирования Структура Паскаль - программы < 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






Информация о работе «Алгоритмический язык Паскаль»
Раздел: Информатика, программирование
Количество знаков с пробелами: 274963
Количество таблиц: 85
Количество изображений: 0

Похожие работы

Скачать
168304
7
26

... .....-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. Описание массивов В языке Паскаль можно обрабатывать не только отдельные переменные, но и их совокупности. Одной из таких совокупностей (структурированных) данных является массив. ...

Скачать
112819
0
0

... . Объясните, для чего служат разрешения и привилегии в Windows NT. Зав. кафедрой --------------------------------------------------   Экзаменационный билет по предмету СИСТЕМНОЕ ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ Билет № 22 Перечислите возможности и инструменты системы программирования Microsoft Developer Studio. Укажите для чего предназначается буфер в системах ввода-вывода, ...

Скачать
91405
0
0

... с внешнего устройства (из входного файла) в основную память ЭВМ, операция вывода - это пересылка данных из основной памяти на внешнее устройство (в выходной файл). Файлы на внешних устройствах часто называют физическими файлами. Их имена определяются операционной системой. В программах на языке Паскаль имена файлов задаются с помощью строк. Например, имя файла на диске может иметь вид: ...

0 комментариев


Наверх