БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

Кафедра программного обеспечения информационных технологий

Факультет ЗВиДО

Специальность ПОИТ

Курсовая работа

по дисциплине «Основы алгоритмизации и программирования»

тема: «Исследование эффективности трех методов сортировок»

Выполнил студент:

Группа

Зачетная книжка

Минск 2009

Оглавление

Оглавление 2

Постановка задачи 2

Входные и выходные данные. 3

Способ решения. 3

Укрупненная структура программы 4

Сортировка прямым выбором 5

Блок схема Сортировки прямым выбором 7

Сортировка пузырьком 8

Блок схема: сортировки пузырьком 12

Быстрая сортировка 13

Блок схема: быстрая сортировка. 15

Тестирование программы. 16

Анализ полученных результатов 16

Литература 18

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

Постановка задачи

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

Поставленная цель определяет задачи исследования:

• Разработать программу для анализа сортировок

• Провести сравнительный анализ этих сортировок между собой по различным параметром: подсчитать количество перестановок и сравнений элементов заданных массивов,а так же исследовать время работы каждой сортировки при заданных параметрах

• Провести сравнительный анализ этих сортировок в зависимости от размера массива.

• Провести анализ в зависимости от вида массива: отсортированный в прямом порядке, отсортированный в обратном порядке, отсортированный наполовину, массив случайных чисел.

Входные и выходные данные.

Входные данные, в данную программу вводятся пользователем не изменяя самого кода программы, а используя именно интерфейс программ, что несомненно является достоинством программы. В результате «диалога» с программой можно выбирать следующие входные данные: размер массива (100, 500, 1000 элементов), а также вид исходного массива (уже отсортированный массив, отсортированный в обратном порядке, отсортированный наполовину, и массив случайных чисел).

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

Способ решения.

pquick, pselect, pbuble, srselect, srquick, srbuble данные переменные в общем случае не укладываю в диапазон (-32768 ÷ 32767) поэтому целеособразно определить их типом longint,.

a,a1,a2:array [0..1000] of integer; массивов берется три, чтобы когда мы вводим массив случайным образом сразу первый массив скопировать в два остальных и отсортировать их три одинаковых массива тремя различными способами, иначе при рандомном ввод и для второй сортировки получается другой результат. До 1000 потому, что массив максимального размера равен 1000 элементам. 1001 элемент 0 нам нужен в качестве барьерного элемента при одном из типов сортировок(сортировка прямым выбором).

hour,hund,min,sec:word; Типf Word встроенная функция gettime(вычисляет текущее системное время с точностью до 1/100 секунды) из unit Dos, записывает выходные данные именно в этот тип.

key:char; flag:boolean; cik:integer;t1,t2,tq,ts,tb:integer;i,j,c,x,k,max,im,n:integer; Выбраны данного типа т.к. именно данный тип дает возможность использовать минимальный объем памяти на их хранение сохраняя при этом функциональность программы.

И наконец y:real; для того, чтоб взяв корень квадратный из дробного числа и записав его в y мы искусственно пропорционально замедлили выполнение каждого типа сортировки иначе совреммеными процессороми задачи сортировки данных массивов решаются за время меньшее, чем 1/100 секунды и его уже не так просто определить.

Выбранный способ решения задачи исходил из цели этой работы. Количество сравнений и перестановок считали в циклах, а время выполнения с помощью встроенной функцияи gettime(вычисляет текущее системное время с точностью до 1/100 секунды) из unit Dos до начала цикла и после начала цикла. Вывод информации на выходе осуществляется с помощью процедур из библиотеки Unita graph.

Системные требования.

IBM совместимый компьютер

32 мб ОЗУ

Выполнение времени сортировок рассчитана на 64 разрядный AMD 5600+ процессор, но убрав искусственно замедляющую время выполнения часть кода программы может использоваться процессор 32 разрядный от 200 МГц и выше.