Порядок выполнения работы

ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

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

Дональд Кнут в книге «Сортировка и поиск» утверждает, что алгоритмы сортировки занимают половину времени исполнения всех процессов обработки данных вычислительной машиной!

Сортировка массива -расположение его элементов по возрастанию (или убыванию). Если не все элементы различны, то надо говорить о неубывающем (или невозрастающем) порядке.

Существует множество методов сортировки. Их можно разделить на:

- простые;

- улучшенные;

- усовершенствованные.

Улучшенные и усовершенствованные базируются на простых методах.

Рассмотренные далее методы сортировки относятся к группе простых.

Пузырьковая сортировка (или сортировка перестановкой, обменом)

Это один из самых простых, но наименее эффективных способов сортировки.

Основная идея: менять местами каждых два соседних элемента (т.е. 1-й и 2-й, затем 2-й и 3-й, …), если их расположение не удовлетворяет условию сортировки. Таким образом, за первый проход самый большой элемент будет в конце (или в начале) сортируемого множества.

Сортировка отбором (или линейная)

Основная идея: на каждом проходе найти наименьший (или наибольший) элемент и поменять его с первым или последним не отсортированным элементом в зависимости от условия сортировки.

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

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

- сортируем первые два элемента

- смотрим на 3-й элемент и вставляем его в нужную позицию по отношению к первым двум.

Продолжаем процесс до конца сортируемого множества.

ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

1. Повторить правила ТБ при работе с ПК.

2. Включить ПК и запустить ИСП PascalABC.NET.

3. Реализовать в ИСП PascalABC.NET программe, листинг которой приведен ниже:

4. Запустить программы на выполнение, проанализировать полученные результаты.

5. САМОСТОЯТЕЛЬНО внести в программу изменения, чтобы происходила сортировка по убыванию.

6. САМОСТОЯТЕЛЬНО дополнить программу строкой так, чтобы велся подсчет числа итераций (количества перестановок и обменов элементов).

7. Установить зависимость количества итераций от длины массива. Для этого изменять количество элементов массива и фиксировать число итераций.

8. Результаты работы программы внести в таблицу.

9. Построить график зависимости f = K(n).

10. Сделать выводы на основе анализа данных в таблице и графика.

КОНТРОЛЬНЫЕ ВОПРОСЫ И ЗАДАНИЯ

1. Где и в каких программах используется сортировка? Привести примеры.

2. По каким показателям можно оценить быстродействие алгоритма сортировки?