РЕАЛИЗАЦИЯ АЛГОРИТМОВ СОРТИРОВКИ

Цель работы Овладеть техникой составления программ упорядочивания данных.

Задачи работыНаучиться реализовывать алгоритмы сортировки данных.

Обеспечивающие средства Сборник описаний практических работ, персональный компьютер, конспект лекций.

Задание Составить программы, реализующие различные алгоритмы сортировки данных для предложенных заданий, отладить их и сохранить.

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

Технология работы

1. Ознакомьтесь с теоретическим материалом, необходимым для выполнения работы:

Сортировка представляет собой процесс упорядочения элементов в массиве по возрастанию или убыванию их значений. Если в массиве есть одинаковые элементы, то говорят о сортировке по неубыванию или по невозрастанию. Следует знать:

· сортировка массивов – одно из наиболее важных действий над массивами в системах сбора и поиска информации, т.к. в отсортированных массивах найти нужную информацию можно гораздо быстрее по сравнению с несортированными;

· существует множество различных алгоритмов сортировки, которые значительно отличаются друг от друга по скорости работы;

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

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

Существует большое количество алгоритмов сортировки, но все они базируются на трех основных:

· сортировка обменом;

· сортировка выбором;

· сортировка вставкой.

Сортировка методом «пузырька» (обменом)

Суть обменной сортировки заключается в том, что упорядоченный список B′ получается из B систематическим обменом пары рядом стоящих элементов, не отвечающих требуемому порядку, пока такие пары существуют.

Наиболее простой метод систематического обмена соседних элементов с неправильным порядком при просмотре всего списка слева направо определяет пузырьковую сортировку: максимальные элементы как бы всплывают в конце списка.

Сортировка выбором

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

Сортировка вставкой

Требуется упорядочить массив B, состоящий из N элементов. Пусть B₁, B₂, …, B_i-1 уже отсортированная часть массива B, а B_i, B_i+1, …, B_n не отсортированная. Идея метода:

1) выбираем очередной элемент B_i (начинаем с i=1);

2) в упорядоченной части массива находим k-ое место, такое чтобы при вставке на это место элемента B_i порядок не нарушился;

3) все элементы начиная с B_k–го до B_i-1 сдвигаем на одну позицию вправо и вставляем элемент B_i на k-ое место;

4) повторяем пункты 1-3 до тех пор пока i < N.

2. Выполните следующие упражнения:

Задания уровня 1

Упражнение 1. Программа с процедурами сортировки простого выбора и простой вставки.

Type

Mas = Array [1 .. n] Of Integer;

Var A: Mas;

Procedure SetRandomMas ( Var A: Mas ); {Задание случайного массива}

Var i: Integer;

Begin

Randomize;

For i := 1 To n Do A[i] := Random (100);

End;

Procedure OutPutMas ( Var A: Mas ); {Вывод массива на экран}

Var i: Integer;

Begin

For i := 1 To n Do Write( A[i]:3 );

WriteLn;

End;

Procedure SortVybor ( Var A: Mas ); {Сортировка выбором}

Var i, k, m, j,Temp, Min: Integer;

Begin

For i := 1 To n Do

Begin

Min := A[i];

k := i;

For j := i+1 To n Do

If A[j] < Min Then Begin Min := A[j]; k := j; End;

Temp := Min;

For m := k-1 DownTo i DoA[m+1] := A[m];

A[i] := Temp;

End;

End;

Procedure SortVstav ( Var A: Mas ); {Сортировка вставкой}

Var i, k, j, Temp: Integer;

Begin

For i := 1 To n-1 Do

Begin

If A[i+1] < A[i] Then

Begin

j := i;

While (A[j] > A[i+1]) And (j >0) Do j := j – 1;

k := j + 1;

Temp := A[i+1];

For j := i DownTo k Do A[j+1] := A[j];

A[k] := Temp;

End;

End;

End;

Begin

ClrScr;

SetRandomMas(A);

OutPutMas(A);

SortVstav(A);

OutPutMas(A)

End.

2. Запустите программу на выполнение и проверьте её работу:Ctrl-F9

3. Для просмотра результатов выполненной программы необходимо нажать:Alt-F5

4. Сохраните программу на своем диске:<F2> A:\P8PR1

3. Выполнить самостоятельно:

Задания уровня 2

1. Написать программу, реализующую алгоритм пузырьковой сортировки, причем просмотр элементов должен вестись наоборот (справа налево). Записать программу под именем P8PR2

2. Написать процедуру сортировки простым выбором, в которой выбирается не минимальный, а максимальный элемент. Сохранить программу под именем P8PR3

Задания уровня 3

4.Запрограммируйте сортировку выбором в виде процедуры. Поиск наименьшего числа сделайте ее внутренней функцией. Сохранить программу под именем P8PR4

3. Написать свои программы сортировки массива для изученных алгоритмов сортировки. Сохраните программы.

4. Окончание работы:

1. Сохранить созданные программы.

2. Подготовить ответы на контрольные вопросы.

3. Показать работу преподавателю.

4. Завершить работу TURBO PASCAL.

Контрольные вопросы:

1. Что называют сортировкой?

2. Как выглядит постановка задачи по сортировке массива?

3. На какие части можно разбить любой алгоритм сортировки?

4. Какие виды сортировки вы знаете?

5. На каких основных видах сортировки базируются остальные алгоритмы сортировки?

6. В чем заключается идея сортировки методом «пузырька»?

7. Объясните суть метода сортировки вставкой.

8. Объясните суть метода сортировки посредством выбора.

9. В чем заключается идея сортировки методом Хоара?

10. В чем заключается сущность метода Шелла?

ПРАКТИЧЕСКАЯ РАБОТА №9

СОСТАВЛЕНИЕ ПРОГРАММ С ИСПОЛЬЗОВАНИЕМ МНОЖЕСТВ

В TURBO PASCAL

Цель работы Овладеть техникой составления программы с использованием множеств, её компиляции и записи на диск под заданным именем.

Задачи работыНаучиться применять основные принципы алгоритмизации и программирования в решении задач, использующих в качестве исходных данных множества.

Обеспечивающие средства Сборник описаний практических работ, персональный компьютер, конспект лекций.

Задание Составить программы для предложенных заданий, используя множества, отладить их и сохранить.

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

Технология работы

1. Ознакомьтесь с теоретическим материалом, необходимым для выполнения работы:

Множество - это набор элементов одинакового типа, которые рассматриваются как единое целое. Элементы множества не пронумерованы, следовательно, нельзя обратиться к отдельному элементу множества по его индексу. Поэтому множества используются в тех задачах, где порядок следования элементов данных не имеет значения.

Тип элементов множества называется базовым типом множества. Область значений типа множества – набор всевозможных подмножеств, составленных из элементов базового типа.

В языке Turbo Pascal имеются ограничения на базовый тип. Это может быть только порядковый тип, количество значений которого не превышает 256. Из простых типов к ним относятся char, byte, boolean. Разрешается использовать перечисляемый тип и диапазон.

Это существенные ограничения, которые не позволяют использовать множества в серьезных задачах обработки данных. Все же для ряда задач применение множеств может обеспечить серьезные преимущества по сравнению с использованием других структур данных – массивов или строк.

Для задания типа множества используются зарезервированные слова Set и Of, а затем указываются элементы этого множества, как правило, в виде перечисления или диапазона.

Множества могут быть описаны двумя способами:

1) Type имя_типа = Set Of базовый тип;

Var имя_множества: имя_типа;

2) Var имя_множества: Set Of базовый тип;

Исходя из особенностей внутреннего представления множеств, можно сделать два основных вывода:

· в множестве не может быть одинаковых элементов, что согласуется и с нашими математическими знаниями;

· все операции над множествами выполняются значительно эффективней, чем над другими структурами данных.

Нельзя вводить значения во множественную переменную оператором ввода и выводить оператором вывода. Множественная переменная может получить конкретное значение только в результате выполнения оператора присваивания следующего формата:

< множественная переменная > := < множественное выражение >

Пример: A := [50, 100, 150, 200]; B := [′m′, ′n′, ′ k′]; C := [True, False]; D := A;

Кроме того, выражения могут включать в себя операции над множествами.

При работе с множествами допускается использование следующих операций:

· отношения (=, <>, >=, <=);

· объединения множеств (+);

· пересечения множеств (*);

· разности множеств (-);

· проверка принадлежности элемента множеству (in).

2. Выполните следующие упражнения:

Задания уровня 1

Упражнение 1. Пусть дана строка символов с точкой в конце строки. Необходимо определить число различных букв, входящих в данную строку.

Var

M: Set Of Char;

Str: String;

c: Char;

i, n: Integer;

Begin

M:=[]; { M – пустое множество}

n:=0; {переменная, считающая количество различных букв в строке}

WriteLn (′Введите строку′);

ReadLn (Str); {ввод строки}

For i:=1To Length (Str) Do

If not (Str[i] In M) Then

Begin

M:=M+[Str[i]]; {формирование множества, содержащего все буквы, входящие в строку}

n:=n+1;

End;

WriteLn (′Количество различных элементов в строке равно′, n)

End.

2. Запустите программу на выполнение и проверьте её работу:Ctrl-F9

3. Для просмотра результатов выполненной программы необходимо нажать:Alt-F5

4. Сохраните программу на своем диске:<F2> A:\P9PR1

Упражнение 2. Даны две символьные строки, содержащие только строчные латинские буквы. Построить строку S3, в которую войдут только общие символы S1 и S2 в алфавитном порядке и без повторений.

End.

2. Запустите программу на выполнение и проверьте её работу:Ctrl-F9

3. Для просмотра результатов выполненной программы необходимо нажать:Alt-F5

4. Сохраните программу на своем диске:<F2> A:\P9PR2

3. Выполнить самостоятельно:

Задания уровня 2

1.Составьте программу, демонстрирующую операции над множествами: операции объединения, разности, пересечения. Множества чисел заполнить следующим образом: D1 – четными числами 2, 4, 6, 8; множество D2 – числами 0, 1, 2, 3, 5; множество D3 – нечетными числами 1, 3, 5, 7, 9. Сохранить программу под именем P9PR3

2. Введите строку. Подсчитайте количество гласных букв в ней. Записать программу под именем P9PR4

Задания уровня 3

3. Задано некоторое множество M и множество T того же типа. Подсчитать, сколько же элементов из множеств T и M совпадает. Сохранить программу под именем P9PR5

4. Требуется сформировать последовательность натуральных чисел от 1 до n, расположенных в случайном порядке без повторения значений. Сохранить программу под именем P9PR6

4. Окончание работы:

1. Сохранить созданные программы.

2. Подготовить ответы на контрольные вопросы.

3. Показать работу преподавателю.

4. Завершить работу TURBO PASCAL.

Контрольные вопросы:

1. Что такое множество?

2. Назовите основные особенности множеств.

3. Что называют конструктором множеств?

4. Как описываются множества в Паскале?

5. Какие операции можно осуществлять с множествами?

ПРАКТИЧЕСКАЯ РАБОТА №10

Не нашли, что искали? Воспользуйтесь поиском по сайту: