Улучшение эффективности внешней сортировки за счет использования основной памяти

<32 33 343536 37 38 >

Чем более длинные серии содержит файл перед началом применения внешней сортировки, тем меньше потребуется слияний и тем быстрее закончится сортировка. Поэтому до начала применения любого из методов внешней сортировки, основанных на применении серий, начальный файл частями считывается в основную память, к каждой части применяется один из наиболее эффективных алгоритмов внутренней сортировки (обычно Quicksort или Heapsort) и отсортированные части (образующие серии) записываются в новый файл. Кроме того, при выполнении распределений и слияний используется буферизация блоков файла(ов) в основной памяти. Возможный выигрыш в производительности зависит от наличия достаточного числа буферов достаточного размера.

ЛЕКЦИЯ 7. СРАВНЕНИЕ МЕТОДОВ СОРТИРОВКИ. ПОДГОТОВКА К КОНТРОЛЬНОЙ РАБОТЕ ПО ТЕМЕ «МЕТОДЫ СОРТИРОВКИ ДАННЫХ»

Цель лекции: дать обзор и сравнительный анализ методов сортировки.

Рассматриваемые вопросы: сравнительный анализ методов сортировки.

Приведем экспериментальные данные отличия одного метода от другого.

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

Три столбца содержат времена сортировки уже упорядоченного массива, случайной перестановки и массива, расположенного в обратном порядке.

В начале (таб.1) приводятся цифры для 256 элементов, а ниже(таб.2) - для 2048.

таблица 1

N=256	упорядоченный	случайный	в обратном порядке
Простое включение	0.02	0.82	1.64
Бинарное включение	0.12	0.70	1.30
Прямой выбор	0.94	0.96	1.18
Пузырек	1.26	2.04	2.80
Шейкер	0.02	1.66	2.92
Шелл	0.10	0.24	0.28
Heap Sort (пирам древ)	0.20	0.20	0.20
QuickSort	0.08	0.12	0.08
Бинарное слияние	0.18	0.18	0.18

Таблица 2

N=2048	упорядоченный	случайный	в обратном порядке
Простое включение	0.22	50.74	103.64
Бинарное включение	1.16	37.66	76.06
Прямой выбор	58.18	58.34	73.46
Пузырек	80.18	128.84	178.66
Шейкер	8.16	104.44	187.36
Шелл	0.80	7.08	12.34
Heap Sort (пирам древ)	2.32	2.22	2.12
QuickSort	0.72	1.22	0.76
Бинарное слияние	1.98	2.06	1.98

Некоторые выводы.

1. Улучшение двоичного включения по сравнению с прямым включением почти ничего не дает, а в случае упорядоченного массива даже получается отрицательный эффект.

2. Пузырьковая сортировка определенно наихудшая из всех сравниваемых.

3. Ее усовершенствованная версия, шейкерная сортировка, продолжает оставаться плохой по сравнению с прямым включением и прямым выбором (за исключением случая уже упорядоченного массива).

4. Quicksort лучше в 2-3 раза, чем Heapsort. Она сортирует массив, расположенный в обратном порядке, практически с той же скоростью, что и уже упорядоченный.

<32 33 343536 37 38 >

Дата добавления: 2018-05-10; просмотров: 1031;