Методические указания и задания к лабораторным работам по курсу "алгоритмы и структуры данных "




НазваниеМетодические указания и задания к лабораторным работам по курсу "алгоритмы и структуры данных "
страница3/19
Дата публикации28.09.2013
Размер1.39 Mb.
ТипМетодические указания
vbibl.ru > Информатика > Методические указания
1   2   3   4   5   6   7   8   9   ...   19
^


{описание типов}

Const Nmax=100;


Type

Rec=Record

kl : integer;

Inf : string [10];

End;

Table-=Array [1..Nmax] Of Rec;

. . . . . . . . . .

Procedure bubble (Var T:Table; n:integer);

{T – имя таблицы; n – размер таблицы (количество записей)}
^

{kl – ключ записи (поле сортировки)}


Var

i, k, m: integer;

pr: boolean;


zap: rec;

Begin

k:=n-1; r:=true; m:=0;

while (k>=1) and pr do

begin

pr:=false;

for i:=1 to k do

if T[i].kl > T[i+1].kl then

begin

zap:=T[i];

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

T[i+1]:=zap;

m:=i;

pr:=true;

end;

k:=m-1;

end

end;

Рисунок 1 – Процедура сортировки таблицы методом "пузырька"
^

Шейкер – сортировка



Метод "пузырька" можно улучшить, если менять направления следующих один за другим проходов таблицы. Этот вариант метода назван шейкер – сортировкой. Его выгодно использовать в тех случаях, когда "легкие" пузырьки расположены в исходной таблице на противоположном ("тяжелом") конце.

Рассмотрим работу этого метода на том же примере, что и в методе "пузырька":


^ Начальные ключи

Проходы


1

2

3

4

15

15

1

1

1

23

8

15

8

3

8

16

8

15

8

16

3

16

3

15

3

1

3

16

16

1

20

20

20

20

20

23

23

23

23


Шейкер – сортировка выполняется быстрее, чем сортировка "пузырьком" (число сравнений равно, примерно, (n*n)/4+n ).
Метод вставки с прямым включением
Метод вставки с прямым включением основывается на следующем утверждении: перед рассмотрением записи R[i] (i=2, 3, …, n) предыдущие записи R[1], R[2], ..., R[i-1] уже упорядочены (K[1]<=K[2]<=...<=K[i-1]), и для R[i] среди них должно быть найдено соответствующее место.
Рассмотрим i й шаг сортировки. Если K[i]<K[i-1], то запись R[i] запоминается в рабочей переменной (например, RAB), и ее ключ сравнивается поочередно с ключами записей R[j] (j=i-1, i-2, ..., 1) до тех пор, пока выполняется условие K[i]j] или достигнут левый конец упорядоченной подтаблицы (j=0). Выполнение условия K[i]>=K[j] означает, что запись RAB нужно вставить между R[j] и R[j+1]. Чтобы подготовить место для вставки (позиция (j+1)), операции сравнения нужно чередовать с операциями перемещения записей на одну позицию (R[j+1]=R[j]). Завершается i-й шаг операцией R[j+1]=RAB.

Ниже показано выполнение i-го шага вставки. Ключевое значение записи R[i], равное 6, сравнивается с предыдущими ключами, и при необходимости записи перемещаются:


Процедура сортировки таблицы методом вставки с прямым включением имеет вид:
{описание типов}

Const Nmax=100;

^ Type rec=record

kl: integer;

inf: string[10]

end;

Table=Array[1..Nmax] of rec;

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

procedure VST (var T:Table; n:integer);

{Т- имя таблицы, n – размер таблицы, сортировка по полю kl}

var

i, j: integer;

rab: rec;

begin

for i:=2 to n do

if T[i].klthen

begin

rab:=T[i];

j:=i-1;

while (j>0) and (rab.kldo

begin

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

j:=j-1

end;

T[j+1]:= rab;

еnd;

end;
Количество операций сравнения для метода вставки определяется по формуле C = n (n – 1)/4. При достаточно большом n можно принять C = n2/4. Максимальное количество перестановок при использовании этого метода равно, примерно, n2/4.
Метод вставки обычно используется тогда, когда нужно внести записи в упорядоченную таблицу. Новая запись должна быть вставлена в таблицу таким образом, чтобы существующая упорядоченность не нарушилась.
1   2   3   4   5   6   7   8   9   ...   19

Похожие:

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconФизика методические указания к лабораторным работам 10, 31
Козлов В. А., Курушин А. Д., Серов Е. А. Физика. Методические указания к лабораторным работам 10, 31 // Под общ ред доц. С. Г. Стоюхина....

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания и задания к лабораторным работам по курсам “
Дискретные структуры“, “Теория алгоритмов и вычислительных процессов“ (для студентов специальностей 050102 “Программное обеспечение...

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания к лабораторным наборам предназначены для студентов,...
Металлургическая гидроаппаратура: Методические указания к лабораторным работам / Санкт-Петербургский государственный горный институт...

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания к лабораторным работам по дисциплине «Автоматизация...
Сапр простейшей структуры на основе расчета и анализа критериев эффективности с использованием имитационных моделей

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания к лабораторным работам по курсу “
В прологе предусматриваются основные арифметические операции +, -, /, ×, mod, div. Чтобы заставить систему выполнить присваивание...

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания к лабораторным работам по дисциплине «Программирование»
Тема: Разработка классов, создание конструкторов и деструкторов. Использование статических членов класса

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconУчебное пособие к лабораторным работам
Автоматизированные информационно-управляющие системы: учебное пособие к лабораторным работам / Л. С. Казаринов, Т. А. Барбасова,...

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconКонтрольные задания по курсу «Экономико-математическое моделирование»...
Контрольные задания по курсу «Экономико-математическое моделирование» и методические указания к их выполнению

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconКонтрольные задания по курсу «Экономико-математическое моделирование»...
Контрольные задания по курсу «Экономико-математическое моделирование» и методические указания к их выполнению

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания и контрольные задания к выполнению контрольных...
В методических указаниях приведены программа изучения курса, контрольные вопросы, контрольные задания и методические указания по...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
vbibl.ru
Главная страница