Практическая работа №6 «Разработка алгоритмов для сортировки массивов»

Цель: Формирование умений и навыков разработке алгоритмов сортировки массивов.

 

Задачи:

1. научиться выполнять сортировку массивов методами простой сортировки

2. научиться разрабатывать алгоритмы сортировки массивов

3. научиться определять сложность алгоритма сортировки

 

Оснащение урока:

· Техническое: ПК, сканер, принтер, интерактивная доска

· Методическое: инструкционная карта, задание для самостоятельного выполнения

· Программное: Windows XP, Microsoft Office 2007.

Теоретические сведения: Сортировка –процесс перестановки объектов множества в определенном порядке. Цель сортировки – облегчить процесс поиска в уже отсортированном множестве.

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

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

Задания для самостоятельного выполнения

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

1. Методом сортировки простыми включениями, упорядочить последовательность по убыванию.

2. Методом простого выбора упорядочить последовательность по возрастанию.

3. Методом пузырьковой сортировки упорядочить последовательность по возрастанию.

4. Методом бинарного поиска найти в массиве число и указать его индекс в массиве.

Вариант	Массив к заданию 1-3	Массив к заданию 4
1.	15 2 48 53 14 3 25 14 51	1 8 9 11 12 15 16 20 найти 16
2.	5 2 40 51 12 30 2 14 55	2 4 6 8 10 12 14 16 найти 19
3.	3 21 48 13 14 2 25 1 51	1 3 5 7 9 11 13 15 17 найти 3
4.	5 2 45 5 14 30 21 11 43	1 2 3 4 5 6 7 8 9 10 11 найти 10
5.	2 48 53 65 3 2 14 51 66	5 6 7 8 9 10 12 15 16 найти 13
6.	14 3 25 14 51 14 51 66	15 16 48 85 94 96 97 99 найти 15
7.	2 22 4 53 14 30 25 21 51	23 25 26 44 56 58 59 60 найти 5
8.	15 4 53 14 25 14 51 12	3 6 9 12 13 15 16 18 66 67 найти 6
9.	5 2 48 5 14 3 25 14 5 21	7 14 21 26 29 30 32 33 36 3 найти 33
10.	53 14 3 25 14 51 54 2 3	36 56 85 95 96 100 120 125 136 найти 56

 

5. Даны декартовые координаты N точек на плоскости.

Составить алгоритмы нахождения:

· самых близких друг к другу точек

· самых удаленных друг от друга точек

· трех точек, лежащих в вершинах треугольника с наибольшим периметром.

Приложение 1

Базовые элементы блок-схем

Наименование	Обозначение	Функция
Блок начало-конец (пуск-остановка)		Элемент отображает выход во внешнюю среду и вход из внешней среды (наиболее частое применение − начало и конец программы). Внутри фигуры записывается соответствующее действие.
Блок действия		Выполнение одной или нескольких операций, обработка данных любого вида (изменение значения данных, формы представления, расположения). Внутри фигуры записывают непосредственно сами операции, например, операцию присваивания: a = 10*b + c.
Логический блок (блок условия)		Отображает решение или функцию переключательного типа с одним входом и двумя или более альтернативными выходами, из которых только один может быть выбран после вычисления условий, определенных внутри этого элемента. Вход в элемент обозначается линией, входящей обычно в верхнюю вершину элемента. Если выходов два или три, то обычно каждый выход обозначается линией, выходящей из оставшихся вершин (боковых и нижней). Если выходов больше трех, то их следует показывать одной линией, выходящей из вершины (чаще нижней) элемента, которая затем разветвляется. Соответствующие результаты вычислений могут записываться рядом с линиями, отображающими эти пути. Примеры решения: в общем случае − сравнение (три выхода: >, <, =); в программировании − условные операторы if (два выхода: true, false) и case (множество выходов).
Предопределённый процесс		Символ отображает выполнение процесса, состоящего из одной или нескольких операций, который определен в другом месте программы (в подпрограмме, модуле). Внутри символа записывается название процесса и передаваемые в него данные. Например, в программировании − вызов процедуры или функции.
Данные (ввод-вывод)		Преобразование данных в форму, пригодную для обработки (ввод) или отображения результатов обработки (вывод). Данный символ не определяет носителя данных (для указания типа носителя данных используются специфические символы).
Соединитель		Символ отображает вход в часть схемы и выход из другой части этой схемы. Используется для обрыва линии и продолжения её в другом месте (для избежания излишних пересечений или слишком длинных линий, а также, если схема состоит из нескольких страниц). Соответствующие соединительные символы должны иметь одинаковое (при том уникальное) обозначение.
Комментарий		Используется для более подробного описания шага, процесса или группы процессов. Описание помещается со стороны квадратной скобки и охватывается ей по всей высоте. Пунктирная линия идет к описываемому элементу, либо группе элементов (при этом группа выделяется замкнутой пунктирной линией). Также символ комментария следует использовать в тех случаях, когда объём текста, помещаемого внутри некоего символа (например, символ процесса, символ данных и др.), превышает размер самого этого символа.