Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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






    " Быстрая сортировка", хоть и была разработана более 40 лет назад, является наиболее широко применяемым и одним их самых эффективных алгоритмов. Метод основан на подходе " разделяй-и-властвуй". Общая схема такова: 1 из массива выбирается некоторый опорный элемент a[i], 2 запускается процедура разделения массива, которая перемещает все ключи, меньшие, либо равные a[i], влево от него, а все ключи, большие, либо равные a[i] - вправо, 3 теперь массив состоит из двух подмножеств, причем левое меньше, либо равно правого, 4 5 для обоих подмассивов: если в подмассиве более двух элементов, рекурсивно запускаем для него ту же процедуру. В конце получится полностью отсортированная последовательность.

 

 

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

Написать пролграммы сортировки массивов длинной 5000, 15000 и 30000 элементов одного типа, указанными методами сортировки.

Произвести расчет мектрик Холстеда для каждого метода.

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

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

Оглавление

1.Теоретические сведенья

1.1. Методы сортировки в Pascal....................................................

1.2. Метрики Холстеда....................................................................

1.3. Функция Get Time

2. Расчетная часть................................................................................

2.1. Вычисление времени срабатывания программы....................

Таблица 1- сравнительный анализ программ, отсортированных различными методами, и расчет метрик........................................

2.2. Расчёт метриков Холстеда........................................................

2.2.1. Метод Пузырьковой сортировки......................................

2.2.2. Метод Простых вставок.....................................................

2.2.3. Метод Шелла......................................................................

2.2.4. Метод Быстрой сортировки..............................................

3.Анализ полученных данных............................................................

Приложение.






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.