Введение. «Сортировка и поиск в массивах»

ОБЪЕКТНО-ОРИЕНТИРОВАННОЕ ПРОГРАММИРОВАНИЕ

Курсовой проект

«Сортировка и поиск в массивах»

Выполнил: студент 3-го курса

Воробьев К.И.

Специальность: 230202

Шифр: 9405020001

Проверил: __________________

Дата: «_____» _________ 2012 г.

Санкт-Петербург

Оглавление

Введение. 3

1. Алгоритмы сортировки. 4

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

1.2. Сортировка методом Выбора (метод локального минимума) 6

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

1.4. Сортировка Быстрым методом.. 10

2. Алгоритмы поиска. 12

2.1. Прямой поиск. 12

2.2. Бинарный поиск. 13

2.3. Интерполяционный поиск. 14

3. Реализация оценки эффективности алгоритмов в программе. 16

3.1. Исходные данные. 16

3.2. Способы оценки эффективности. 16

3.3. Реализация подсчета кол-ва сравнений, присваиваний и эффективности в программе. 17

3.4. Реализация замера времени выполнения алгоритмов сортировки в программе. 17

3.5. Реализация представления результата в программе. 18

4. Результат определения эффективности алгоритмов. 18

5. Структура прграммы.. 20

5.1. Интерфейс программы.. 20

5.2. Описание структуры программы.. 22

5.2.1. Глобальная структура для хранения статистики. 22

5.2.2. Основной модуль Unit1.cpp (для Формы Form1) 23

5.2.3. Модуль Unit2.cpp (для Формы GrafForm) 24

6. Листинг программы.. 25

6.1. Файл Unit1.h. 25

6.2. Файл Unit2.h. 25

6.3. Файл Unit1.cpp. 25

6.4. Файл Unit2.cpp. 44

Заключение. 47

Список используемой литературы.. 48

Введение

Целью данного курсового проекта является приобретение навыков создания Windows-приложений с помощью среды разработки Borland Builder 2005, которая является мощным инструментом создания приложений с неограниченными возможностями использования ресурсов Windows и языка программирования C++. Целевой основой курсового проекта является приобретение навыков разработки алгоритмов для сортировки массивов на основе их словесных описаний, а также поиска в них.

В первой главе представлены словесные описания алгоритмов сортировки, которые использовались при создании программы в Borland Builder, их реализация и анализ.

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

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

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

В пятой главе представлены основные механизмы для реализации программы.

В шестой главе приведен листинг программы.

Основные возможности программы:

1. Выполнение четырех видов сортировок по четырем разным размерностям исходных массивов (5, 7, 9, 25 элементов).

2. Два типа заполнения исходных массивов – в случайном порядке, в убывающем порядке.

3. Возможность выбрать новые случайные значения.

4. Возможность выбрать новое значение кол-ва повторений сортировок для замера времени выполнения.

5. Возможность пройтись по всем сортировкам для всех размерностей в автоматическом режиме с помощью одной кнопки.

6. Вывод информации текущей операции.

7. Прогресс-бар для текущей операции.

8. Отдельный вывод информации о результате последней сортировки.

9. Вывод статистики результатов по всем методам сортировки для всех размерностей.

10. Вывод графика (диаграммы) для каждого из двух способов заполнения исходных массивов (убывающий и случайны порядки) по всем методам и размерностям.

11. Выполнение поиска тремя методами (прямым, бинарным и интерполяционным) с показом результата поиска и эффективности и фильтром вводимых данных.