Курс лекций 20 часов

Скачать 1.37 Mb.

Название	Курс лекций 20 часов
страница	14/21
Дата публикации	21.09.2013
Размер	1.37 Mb.
Тип	Лекция

100-bal.ru > Информатика > Лекция

1 ... 10 11 12 13 14 15 16 17 ... 21

Сортировка методом простого обмена

Сортировка методом простого обмена может быть применена для любого массива. Этот метод заключается в последовательных просмотрах массива слева направо ( от начала к концу ) и обмене местами соседних элементов, расположенных “неправильно”, то есть таких, что i < j, а a[i] > a[j]. Опишем этот метод подробнее.

Начнем просмотр с первой пары элементов ( a[1] и a[2] ), если первый элемент этой пары больше второго, то меняем их местами, иначе оставляем без изменения. Затем берем вторую пару элементов ( a[2] и a[3] ), если a[2] > a[3], то меняем их местами и так далее. На первом шаге будут просмотрены все пары элементов массива a[i] и a[i+1] для i от 1 до n-1. В результате максимальный элемент массива переместится в конец массива.

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

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

Отсортируем по возрастанию методом простого обмена массив из 5 элементов: 5 4 8 2 9

Длина текущей части массива - n-k+1, где k - номер просмотра, i - номер проверяемой пары; номер последней пары - n-k. За вертикальной чертой располагаются отсортированные элементы.
Первый просмотр: рассматривается весь массив.
i = 1 5 > 4 8 2 9

обмен
i = 2 4 5 < 8 2 9

нет обмена
i = 3 4 5 8 > 2 9

обмен

i = 4 4 5 2 8 < 9

нет обмена
9 стоит на своем месте.
Второй просмотр: рассматриваем часть массива с первого до четвертого элемента.
i = 1 4 < 5 2 8  9

нет обмена
i = 2 4 5 > 2 8  9

обмен
i = 3 4 2 5 < 8  9

нет обмена
8 стоит на своем месте.
Третий просмотр: рассматриваемая часть массива содержит три первых элемента.

i = 1 4 > 2 5  8 9

обмен

i = 2 2 4 < 5  8 9

нет обмена
5 стоит на своем месте.
Четвертый просмотр: рассматриваем последнюю пару.

i = 1 2 4 < 5  8 9

нет обмена
4 стоит на своем месте.
Для самого маленького элемента ( 2 ) остается только одно место - первое.

Итак, наш массив отсортирован по возрастанию элементов методом простого обмена. Этот метод называют также методом “пузырька”. Название это происходит от обратной интерпретации, при которой в процессе выполнения сортировки более “ легкие ” элементы ( элементы с заданным свойством ) мало - помалу всплывают на “поверхность”.
Программа “пузырьковой” сортировки.
program n2;const n=5;type ar=array [1..n] of integer;

var i:integer;

a:ar;
procedure sorting2(var a:ar);

var k,i,t:integer;

{k - номер просмотра (изменяется от 1 до n-1)

i - номер рассматриваемой пары

t - промежуточная переменная для перестановки местами элементов}

begin

for k:=1 to n-1 do

{цикл по номеру просмотра}

for i:=1 to n-k do

if a[i]>a[i+1] then

{перестановка элементов}

begin

t:=a[i];

a[i]:=a[i+1];

a[i+1]:=t;

end;

end;

begin

writeln('Введите исходный массив:');

for i:=1 to n do read(a[i]);

sorting2(a);

writeln('Отсортированный массив:');

for i:=1 to n do write(a[i],' ');

writeln;

end.

1 ... 10 11 12 13 14 15 16 17 ... 21

Похожие:

	Курс лекций по дисциплине «Уголовно-исполнительное право» для специальности 030503 Правоведение Данный курс лекций рассчитан на 50 часов для базового уровня профессионального образования и един для всех форм обучения		Экономическая теория Курс состоит из 39 часов лекций, 20 часов семинаров и 52 часов самостоятельной работы студентов, которая включает подготовку к семинарским...
	Курс лекций по «экологии» нгпи. 40 часов лекций + зачет и экзамен Агаджанян Н. А., Никитюк Б. А., Полунин Н. Н. Экология человека и интегративная антропология. — М. — Астрахань, 1996. — 224 с		Самостоятельная работа обучающихся 34 часа Аудиторная работа по дисциплине... Учебно-методический комплекс дисциплины обсужден и утвержден на заседании кафедры зарубежной филологии
	Программа курса физики для студентов геологического факультета (вечернее... Курс рассчитан на 60 лекционных часов: 1 семестр 10 лекций по 4 часа, 2 семестр 10 лекций по 2 часа. Два экзамена		Программа элективного курса «Биотехнология вчера и сегодня» Курс интегрированный, затрагивает вопросы, находящиеся на стыке биологии с другими науками, прежде всего с медициной, химией, географией....
	Рабочая программа ♫ Тематика и планы семинарских занятий ♫ Элективный курс «История западноевропейской музыки» читается студентам-культурологам IV года обучения. Программа предусматривает...		Программа курса Курс расcчитан на 100 академических часов (1 акад час ~ 45 мин): 17 лекций(172=34часа) и 11 практических занятий(116=66 часов)....
	Дисциплина "Логистика" входит в состав цикла специальных дисциплин.... Курс лекций ориентирован на современные экономические условия и складывающиеся рыночные отношения в Российской Федерации		Программа дисциплины «менеджмент» для студентов специальности ( направления)... Учебная дисциплина «Менеджмент» входит в раздел «Профессиональный цикл. Базовая (общепрофессиональная) часть» фгос по направлениям...
	Рассмотрен и рекомендован к утверждению Данный курс лекций рассчитан на 50 часов для базового уровня профессионального образования и един для всех форм обучения		В. Н. Майсак 2011 год Данный курс лекций рассчитан на 50 часов для базового уровня профессионального образования и един для всех форм обучения
	Педиатрический факультет Федерации для педиатрических факультетов высших медицинских учебных заведений, офтальмология преподается в 8-9 семестре обучения...		Учебно-методический комплекс «Уголовно-исполнительное право» Данный курс лекций рассчитан на 50 часов для базового уровня профессионального образования и един для всех форм обучения
	Курс лекций по истории и философии науки утверждено Редакционно-издательским... Глотова В. В. Краткий курс лекций по истории и философии науки: учеб пособие / В. В. Глотова. Воронеж: фгбоу впо «Воронежский государственный...		Рабочая программа по офтальмологии кафедры офтальмологии педиатрического факультета Федерации для педиатрических факультетов высших медицинских учебных заведений, офтальмология преподается в 8-9 семестре обучения...

Школьные материалы