Студопедия Главная Случайная страница Обратная связь

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

Сортировка слиянием





Ожидаемая трудоемкость: O(n log n)

Рис 7. График зависимости времени сортировки от количества сортируемых элементов для сортировки слиянием

Рис 8. График отношения времени сортировки к функции n log n в зависимости от количества сортируемых элементов

Сравнение сортировок

Рис 9. Сравнение времени сортировок на одном массиве


Заключение

В ходе выполнения лабораторной работы были реализованы две программы: Exp.exe, осуществляющая сортировку массива, и Tests.exe, проводящая серийный запуск Exp.exe. Обе программы удовлетворяют всем требованиям, представленным в разделе «Постановка задачи».

По результатам экспериментов было построено 7 графиков. Рисунки 3, 5, 7 демонстрируют зависимость времени сортировки от числа элементов в сортируемом массиве для соответствующих методов.

Рисунки 4, 6, 8 показывают, что ожидаемая трудоемкость для каждой из сортировок совпадает с реальной, так как функция отношения времени сортировки к ее ожидаемой трудоемкости ведет себя аналогично константе.

Рисунок 9 позволяет сравнить скорость сортировки разными алгоритмами на одном массиве данных. По результатам этого сравнения наиболее быстрым алгоритмом стала сортировка слиянием.

 


Литература

1. Сортировка слиянием — Википедия. — [http://ru.wikipedia.org/wiki/Сортировка_слиянием]

2. Microsoft Developer Network. — [http://msdn.microsoft.com/]








Дата добавления: 2015-06-15; просмотров: 540. Нарушение авторских прав; Мы поможем в написании вашей работы!




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


Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...


Кардиналистский и ординалистский подходы Кардиналистский (количественный подход) к анализу полезности основан на представлении о возможности измерения различных благ в условных единицах полезности...


Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...

Этапы трансляции и их характеристика Трансляция (от лат. translatio — перевод) — процесс синтеза белка из аминокислот на матрице информационной (матричной) РНК (иРНК...

Условия, необходимые для появления жизни История жизни и история Земли неотделимы друг от друга, так как именно в процессах развития нашей планеты как космического тела закладывались определенные физические и химические условия, необходимые для появления и развития жизни...

Метод архитекторов Этот метод является наиболее часто используемым и может применяться в трех модификациях: способ с двумя точками схода, способ с одной точкой схода, способ вертикальной плоскости и опущенного плана...

Типовые примеры и методы их решения. Пример 2.5.1. На вклад начисляются сложные проценты: а) ежегодно; б) ежеквартально; в) ежемесячно Пример 2.5.1. На вклад начисляются сложные проценты: а) ежегодно; б) ежеквартально; в) ежемесячно. Какова должна быть годовая номинальная процентная ставка...

Выработка навыка зеркального письма (динамический стереотип) Цель работы: Проследить особенности образования любого навыка (динамического стереотипа) на примере выработки навыка зеркального письма...

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

Studopedia.info - Студопедия - 2014-2025 год . (0.011 сек.) русская версия | украинская версия