Сортировка методом пузырька.

↑

▷ Содержание

⇐ ПредыдущаяСтр 10 из 31Следующая ⇒

Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает – массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.

В качестве примера рассмотрим сортировку по возрастанию массива из 10 целых чисел. Массив формируется датчиком случайных чисел, генерирующим значения от 0 до 9.

Var

i, j, n, t: integer;

a: array [1..10] of integer;

Begin

{Инициализация датчика случайных чисел}

randomize;

n:= 10;

{Заполнение массива и вывод его на экран}

for i:= 1 to n do

a[i]:= Random(10);

WriteLn('Исходный массив');

for i:=1 to n do

Write(a[i],' ');

WriteLn;

{Сортировка массива методом пузырька}

for i:=1 to n-1 do

for j:=1 to n-i do

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

Begin

t:=a[j];

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

a[j+1]:=t;

end;

{Вывод на экран отсортированного массива}

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

for i:=1 to n do

Write(a[i],' ');

WriteLn;

ReadLn;

End.

Сортировка методом поиска минимума (максимума).

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

Основная идея алгоритма следующая: на i -м шаге итерации среди элементов массива a[i]…a[n] ищется минимальный (максимальный) элемент массива и меняется местами с a[i]. На следующем шаге i увеличивается на единицу и процедура поиска повторяется. Всего надо сделать n-1 итераций, где n – число элементов массива.

При использовании данного алгоритма сортировки предыдущая задача будет выглядеть следующим образом:

Var

i, j, n, t, min: integer;

a: array [1..10] of integer;

Begin

{Инициализация датчика случайных чисел}

randomize;

n:= 10;

{Заполнение массива и вывод его на экран}

for i:=1 to n do

a[i]:=Random(10);

WriteLn('Ishodnyi massiv');

for i:=1 to n do

Write(a[i],' ');

WriteLn;

{Сортировка массива методом поиска минимума}

for i:=1 to n-1 do

Begin

min:=a[i];

for j:=i+1 to n do

if min>a[j] then

Begin

min:=a[j];

t:=a[j];

a[j]:=a[i];

a[i]:=t;

end;

end;

{Вывод на экран отсортированного массива}

WriteLn('Otsortirovannyi massiv');

for i:=1 to n do

Write(a[i],' ');

WriteLn;

ReadLn;

End.

Сортировка методом вставки.

В данном алгоритме используется методика «вставки» очередного элемента массива в уже отсортированную часть массива в нужную позицию.

Основная идея следующая: на i -ом этапе итерации производится вставка j -того элемента массивав нужную позицию среди элементов a[1], a[2],..., a[j-1], которые уже упорядочены (j = i - 1). После этой вставки первые j элементов массива a будут упорядочены.

При использовании данного алгоритма сортировки предыдущая задача будет выглядеть следующим образом:

Var

i,j,n, key: integer;

a: array [1..10] of integer;

Begin

{Инициализация датчика случайных чисел}

randomize;

n:=10;

{Заполнение массива и вывод его на экран}

for i:= 1 to n do

a[i]:= Random(10);

WriteLn('Исходный массив');

for i:= 1 to n do

Write(a[i],' ');

WriteLn;

{Сортировка массива методом вставки}

for i:= 2 to n do

begin

key:=a[i];

j:= i – 1;

while (j >= 1) and (a[j] > key) do

Begin

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

j:= j – 1;

a[j+1]:= key;

end;

end;

{Вывод на экран отсортированного массива}

WriteLn('Otsortirovannyi massiv');

for i:= 1 to n do

Write(a[i],' ');

WriteLn;

ReadLn;

End.

Записи и файлы

Данные типа записи

Запись – это сложный тип данных, представляющий собой структуру, состоящую из фиксированного числа компонент, называемых полями. При этом в разных полях могут быть данные разных типов. Данные типа запись описываются следующим образом:

Type

tr = record

f11, f12,…, f1l: t1;

f21, f22,…, f2m: t2;

…

fk1, fk2,…,fkn: tk;

end;

Var

mp: tr;

Здесь tr – имя типа; mp – имя записи; l – число полей типа t1; m – число полей типа t2; n – число полей типа tk; fij – имена полей (элементов записи); служебные слова record, end – выполняют роль операторных скобок, открывающей и закрывающей соответственно.

Обращение к элементу записи (полю) fij осуществляется следующим образом: mp.fij, где mp – имя записи, fij – имя элемента (поля). Между именем записи и именем поля ставится точка.

Например, описать сведения о книге как данные типа запись. Пусть требуется хранить о книге следующие сведения: шифр книги (shg), название книги (ng), авторы (avt), год издания (GI).

Type

kniga = record

shg: string[10];

ng: string[100];

avt: string[100];

gi: integer;

end;

Var

a: kniga;

Begin

…

a.shg:= ‘ВМ-991’;

a.ng:= ‘Информатика 2002’;

a.avt:= ‘Алексеев А.П.’;

a.gi:= 2002;

end.

Элементы массива также могут иметь тип запись. Для обращения к полям элемента массива указывают mp[i].fij, где mp – имя элемента массива, i – номер элемента массива; fij – имя элемента записи (поля). Например, требуется описать сведения о 10-ти книгах:

Var

a: array [1..10] of kniga;

Begin

…

a[1].shg:= ‘831.3 а45’;

a[1].ng:= ‘информатика 2002’;

a[1].avt:= ‘алексеев а.п.’;

a[1].gi:= 2002;

End.

Примеры программ, работающих с данными типа запись.

Пример 1. Составить программу, которая вводит о каждом студенте следующие данные: номер зачетки, фамилия, оценка за контрольную. Данные оформить как массив из 10 записей. Элементы массива имеют тип запись. Вывести сведения о студентах, у которых оценка больше средней оценки.

Type

st = record

nz: string [6];

fio: string [20];

ok: real;

end;

Var

a: array [1..10] of st;

sr: real;

k, i: integer;

Begin

{присвоение сумме оценок значения 0}

sr:= 0;

for i:= 1 to 10 do

Begin

{ввод данных}

Write(‘Номер зачетки=’);

ReadLn(a[i].nz);

Write (‘Фамилия=’);

ReadLn(a[i].fio);

Write(‘Оценка=’);

ReadLn(a[i].ok);

{суммирование оценок}

sr:= sr + a[i].ok

end;

{расчет средней оценки}

sr:= sr/10;

WriteLn(‘Средняя оценка=’, sr:5:2);

WriteLn(‘Список студентов, у которых оценка

выше средней’);

{вывод сведений о студентах, у которых оценка больше

средней по группе}

for i:= 1 to 10 do

if a[i].ok > sr then

WriteLn(a[i].nz,’ ‘, a[i].fio,’ ‘, a[i].ok:3:1);

{вывод списка всех студентов}

WriteLn(‘Общий список’);

for i:= 1 to 10 do

WriteLn(a[i].nz,’ ‘, a[i].fio,’ ‘, a[i].ok:3:1);

ReadLn;

End.

Для удобства работы с переменными типа записи используется оператор присоединения with, формат которого:

with x do op;

где х – имя записи, ор – оператор. При этом в операторе ор при ссылках на элементы записи имя х опускается.

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

Type

stud = record

shg: string [7];

fio: string [20];

f, m,c: integer;

cr: real

end;

Var

st: array [1..25] of stud;

k, i: integer;

s: real;

Begin

{ввод количества студентов}

Write(‘Введите количество студентов=’);

ReadLn(k);

{ввод в цикле исходных данных}

for i:= 1 to k do

with st[i] do

Begin

Write(‘’);

ReadLn(shg);

Write(‘’);

ReadLn(fio);

Write(‘’);

ReadLn(f, m, c);

{расчет среднего балла студента}

cr:= (f + m + c)/3;

end;

{расчет среднего балла по группе}

s:=0;

for i:= 1 to k do

s:= s + st[i].cr;

s:= s/k;

WriteLn(‘Средний балл по группе=’, s:5:2);

{вывод сведений о студентах с высоким баллом}

Writeln(‘Студенты со средним баллом больше

среднего балла по группе’);

for i:= 1 to k do

with st[i] do

if cr > s then

WriteLn(shg, ’ ‘, fio,’ ‘, cr:5:2);

{вывод сведений о всех студентах}

WriteLn(‘Общий список’);

for i:= 1 to k do

with st[i] do

WriteLn(shg, ’ ‘, fio, ’ ‘, cr:5:2);

End.

Работа с файлами

Под файлом понимается либо именованная область на носителе информации (локальном, сетевом или съемном диске), содержащая данные определенного вида.

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

Для организации ввода-вывода информации в файл в программе используются специальные переменные файлового типа. Переменные файлового типа описываются следующим образом:

Var

имя переменной: file of тип элементов файла;

Например,

Var

a: file of integer;

b: file of real;

В отличие от массива длина файла, то есть количество элементов, не задается, место элемента не определяется индексом.

С каждой переменной файлового типа связано понятие текущего указателя. Текущий указатель указывает на некоторый конкретный элемент файла. Все действия с файлами (чтение из файла, запись в файл) производятся поэлементно, причем в этих действиях участвует тот элемент файла, на который указывает указатель. В результате совершения операций текущий указатель может перемещаться.

Все элементы файла считаются пронумерованными, начальный элемент имеет нулевой номер.

Познавательные статьи:



Алгоритмические операторы Matlab

Конструирование и порядок расчёта дорожной одежды

Исследования учёных: почему помогают молитвы?

Почему терпят неудачу многие предприниматели?