Методы сортировки
Исследование сложности различных алгоритмов сортировки целочисленных массивов в зависимости от их исходных параметров в среде операционной системы Windows 3.11 или выше. Оценка быстрых и медленных их модификаций, графическое представление результатов.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | лабораторная работа |
| Язык | русский |
| Дата добавления | 10.08.2013 |
| Размер файла | 182,2 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Лабораторная работа №1
Методы сортировки
Данная лабораторная работа выполняется под управлением операционной системы Windows 3.11 или выше. Цель работы: исследование сложности различных алгоритмов сортировки целочисленных массивов в зависимости от исходных параметров этих массивов.
В результате измерения скорости сортировки массива из 3000 элементов и с диапазоном значений 3000 были установлены следующие результаты:
|
Название метода |
Время, с |
|
|
Быстрая Хоара |
0,05 |
|
|
Естественная двухпутевым сливанием |
0,06 |
|
|
Шелла |
0,07 |
|
|
Бинарной вставкой |
0,88 |
|
|
Интерполяционной вставкой |
0,90 |
|
|
Простым выбором |
1,64 |
|
|
Простой вставкой |
2,36 |
|
|
Пузырьком |
3,46 |
К быстрым методам были отнесены: Быстрая Хоара, Естественная двухпутевым сливанием, Шелла, Бинарной вставкой.
К медленным: Бинарной вставкой, Интерполяционной вставкой, Простым выбором, Простой вставкой, Пузырьком.
2. Исследование всех методов сортировки на их сложность
|
Метод |
500 |
1000 |
1500 |
2000 |
2500 |
1000 |
2000 |
4000 |
8000 |
16000 |
|
|
Быстрая Хоара |
0 |
0 |
0,5 |
0,06 |
0,22 |
||||||
|
Естественная двухпутевым сливанием |
0 |
0,5 |
0,11 |
0,22 |
0,50 |
||||||
|
Шелла |
0 |
0,6 |
0,12 |
0,24 |
0,58 |
||||||
|
Бинарной вставкой |
0,11 |
0,38 |
1,59 |
6,10 |
24,12 |
||||||
|
Интерполяционной вставкой |
0,06 |
0,11 |
0,22 |
0,44 |
0,66 |
||||||
|
Простым выбором |
0,06 |
0,22 |
0,44 |
0,83 |
1,26 |
||||||
|
Простой вставкой |
0,06 |
0,22 |
0,64 |
1,10 |
1,71 |
||||||
|
Пузырьком |
0,06 |
0,33 |
0,82 |
1,48 |
2,31 |
алгоритм сортировка массив
Или, если представлять в графическом виде:
Быстрая сортировка Хоара.
Естественная двухпутевым слиянием.
Шелла.
Бинарная вставка.
Простым выбором.
Простой вставкой.
Пузырьком.
4.Более подробное исследование метода Шелла
|
1000 |
2000 |
5000 |
10000 |
20000 |
||
|
прямая |
0 |
0,06 |
0,17 |
0,35 |
0,77 |
|
|
обратная |
0 |
0,06 |
0,17 |
0,36 |
0,77 |
|
|
Разброс 1000 |
0 |
0,06 |
0,17 |
0,35 |
0,74 |
|
|
Разброс 20000 |
0 |
0,06 |
0,17 |
0,35 |
0,74 |
|
|
Уже упорядоч. |
0 |
0 |
0 |
0 |
0 |
Как видно из приведенной таблицы методом Шелла можно сортировать массивы в обоих направлениях с одинаковой скоростью. Также не влияет на скорость сортировки разброс значений элементов массива. При обработке уже упорядоченного списка методом Шелла, были получены нулевые задержки, т.е. обработка происходила мгновенно. Из всего вышесказанного можно сделать вывод о высокой эффективности метода Шелла.
Все измерения проводились на компьютере оснащенном процессором intel P!!!-533B, со 128 Мб оперативной памяти. Использовалась операционная система Microsoft Windows98.
Размещено на Allbest.ru
...Подобные документы
Изучение алгоритмов внутренней сортировки массивов данных, сравнение сложности их реализации и производительности. Отличительные черты сортировки включением, выбором, разделением, сортировки Шелла, обменной сортировки. Сравнение методов: плюсы и минусы.
курсовая работа [203,8 K], добавлен 03.12.2010Обработка массивов элементов любого типа как главное назначение алгоритмов сортировки. Анализ наиболее используемых алгоритмов сортировки: пузырьком, выбором, вставками, методом Шелла и быстрой сортировкой. Основные требования к алгоритмам сортировки.
реферат [189,8 K], добавлен 06.12.2014Анализ основных алгоритмов внутренней сортировки массивов данных, сравнение сложности их реализации и производительности. Сортировка пузырьком, методами вставок, выбора, методом Шелла, быстрая сортировка. Операция разделения массива внутренней сортировки.
курсовая работа [161,7 K], добавлен 17.12.2015Исследование основных особенностей алгоритмов быстрой и поразрядной сортировки данных. Построение графиков зависимости времени сортировки от количества элементов в файле и от степени перемешенности элементов. Описания сортировки чисел и строковых данных.
лабораторная работа [1,2 M], добавлен 23.07.2012Реализация различных методов сортировки. Алгоритмические языки программирования. Обработка большого числа единообразно организованных данных. Алгоритмы сортировки массивов. Анализ проблем реализации и использования различных видов сортировок массивов.
курсовая работа [640,3 K], добавлен 07.07.2011Анализ структуры топологической сортировки в программной среде. Метод топологической сортировки с помощью обхода в глубину. Программа, реализующая топологическую сортировку методом Демукрона. Создание карты сайта и древовидная система разделов.
курсовая работа [1,3 M], добавлен 22.06.2011Методы реализации алгоритмов сортировки и алгоритмов поиска на языках программирования высокого уровня. Программирование алгоритмов сортировки и поиска в рамках создаваемого программного средства на языке Delphi. Создание руководства пользователя.
курсовая работа [1,7 M], добавлен 16.04.2012Понятие алгоритма и сортировки. Способы и алгоритмы сортировки массивов. Быстрая сортировка Хоара. Описание алгоритма "быстрой сортировки". Реализация на языке программирования. Анализ наихудшего разбиения. Вероятностные алгоритмы быстрой сортировки.
курсовая работа [291,5 K], добавлен 22.03.2012Сущность и порядок реализации простых методов сортировки при составлении программного алгоритма, их классификация и разновидности, отличительные признаки, характерные свойства. Особенности алгоритмов для сортировки файлов записей, содержащих ключи.
реферат [20,7 K], добавлен 20.05.2010Разработка программы для осуществления сортировки данных методами "Выбора" с использованием языка C# и Visual Studio 2012. Плавный метод сортировки. Основные фазы сортировки во внутреннем представлении пирамиды. Программа сортировки методами выбора.
курсовая работа [637,6 K], добавлен 29.11.2014Краткое описание языка программирования С++. Алгоритм линейного выбора элемента, методов минимального (максимального) элемента и челночной сортировки. Анализ и разработка приложения, организующего сортировку массива данных пятью методами сортировки.
реферат [614,8 K], добавлен 12.04.2014Понятие и основной принцип действия алгоритмов сортировки информации. Сравнительное исследование и анализ эффективности методов сортировки Шелла и Флойда в виде графиков зависимостей количества сравнений и числа перестановок элементов от объёма данных.
контрольная работа [573,6 K], добавлен 09.11.2010Характеристика используемой операционной системы, языка программирования. Структура программы на языке Turbo Pascal 7.1. Операторы языка Turbo Pascal. Проведение сортировки записей. Алгоритмы программы и подпрограмм. Причины возникновения ошибок.
курсовая работа [454,1 K], добавлен 13.06.2014Определение понятия, видов и задач сортировки. Рассмотрение основ построения простых и улучшенных алгоритмов сортировки, анализ числа операций. Линейная и пирамидальная организация данных. Основные правила нижней оценки числа операций в алгоритмах.
презентация [274,5 K], добавлен 19.10.2014Алгоритмы сортировки методами простых вставок и пузырька. Зависимость среднего времени сортировки от числа сортируемых элементов. Функции, осуществляющие сортировку любого количества элементов методом простых вставок, на основе сортировки таблицы адресов.
курсовая работа [557,1 K], добавлен 26.05.2010Постановка задачи сортировки. Анализ основных понятий сортировок слияниями. Алгоритм сортировки простым и естественным слиянием. Оценка сложности алгоритма. Программная реализация простого слияния. Тестирование меню на корректность входных данных.
курсовая работа [283,6 K], добавлен 22.06.2015Знакомство с операционной системой Windows. Исследование её устройства, истории, возможностей, особенностей работы с ней для получения новых знаний. Описание наиболее использующихся и важных функций этой операционной системы, их практическое освоение.
контрольная работа [2,9 M], добавлен 14.12.2009Широкое использование компьютерных и информационных технологий. Концепции типов данных. Алгоритмы сортировки одномерных массивов. Описание двумерного массива Паскаля. Методы доступа к элементам массивов. Индексные, динамические и гетерогенные массивы.
курсовая работа [66,3 K], добавлен 07.12.2010Знакомство с техническими характеристиками персонального компьютера. Установка операционной системы и драйверов Windows 7. Способы чистки Windows XP Professional SP3. Методы восстановления операционной системы. Выполнение установки Microsoft Office 2010.
отчет по практике [5,6 M], добавлен 22.09.2014Составление и программная реализация в среде Borland Delphi 7.0 алгоритмов итерационного и рекурсивного вариантов решения задачи поиска с возвращением. Исследование асимптотической временной сложности решения в зависимости от количества ячеек на плате.
курсовая работа [57,5 K], добавлен 25.06.2013
