Поиск компоненты с заданным значением это одна из основных операций, применяемых к структурированным данным

Вид материала

Документы

Содержание Таблица 6.2 Время выполнения программ сортировки. Простые методы Улучшенные методы

Подобный материал:

• Лекция Перегрузка операций. Преобразование типов, 75.44kb.
• Лабораторная работа, 20.66kb.
• Морфология, 3050.25kb.
• Ием в характере выпускаемой продукции, используемых основных производственных фондов, 769.16kb.
• Методические указания и тематика контрольных работ По дисциплине «Математические методы, 294.85kb.
• 1 учебно-научный текст как лингвистическая основа формирования интеллектуально-речевой, 445.3kb.
• План. Введение. Аудит учета основных средств. Проверка операций по реализации и выбытию, 304.48kb.
• Ке современных строительных материалов, уместно сказать: оно уникально, универсально, 920.91kb.
• Учебные задания на развитие мыслительных операций, 84.79kb.
• История становления и развития промышленных предприятий в поселке, 53.58kb.

Таблица 6.2 Время выполнения программ сортировки.

Метод	Упорядоченный массив		Случайный массив		Обратно упорядоченный
	5000 эл.	20000эл.	5000 эл.	20000эл.	5000 эл.	20000эл
ПРОСТЫЕ МЕТОДЫ
Прямой обмен	<0.01	<0.01	14.77	235.41	17.91	286.94
Шейкерная сортировка	<0.01	<0.01	6.75	108.97	11.86	191.03
Прямой выбор	4.34	71.35	4.34	71.35	4.51	71.95
Прямое включение	<0.01	<0.01	3.02	48.61	6.04	98.26
Бинарное включение	<0.01	0.11	2.36	38.44	4.78	77.39
УЛУЧШЕННЫЕ МЕТОДЫ
Метод Шелла	<0.01	0.05	0.39	6.53	0.77	13.35
Сортировка слиянием	0.01	0.09	0.19	0.4	0.12	0.1
Пирамидальная сортировка	0.05	0.12	0.05	0.08	0.04	0.07
QuickSort	<0.01	0.11	0.05	0.17	0.06	0.15

Таким образом, на основании таблиц, можно утверждать, что:

• среди простых методов сортировки предпочтительным является метод прямого включения, а при наличии сопутствующей информации – прямого выбора;
  
• сортировка методом простого обмена является наихудшей среди всех сравниваемых методов; ее улучшенная версия – шейкер-сортировка все-таки хуже сортировки простыми включениями и простым выбором (кроме “непонятного” случая сортировки ранее рассортированного массива);
  
• быстрая сортировка по эффективности превосходит все остальные методы сортировки;
  
• сортировка слиянием занимает промежуточное место между пирамидальной и быстрой сортировками, т. е. является вполне приемлемой для массивов;
  
• наличие сопутствующей ключам информации существенно не искажает предыдущие утверждения.
  

Рис.6.14 20000 элементов типа Word, 486DX2-66.

Рис.6.15 3000 элементов типа Word, 486DX2-66

Рис.6.16 4000 элементов типа Word, 486DX2-66




Рис.6.17 2000 элементов типа Word, 486DX2-66

Упражнения


В качестве упражнения по этому этому разделу можно рекомендовать разработку упомянутого комплекса программ для экспериментальной сравнительной оценки качуства алгоритмов сортировки. Для этого целесообразно сначала “спланировать” сам эксперимент, например в таком виде:

1. Сформировать массив с задаными свойствами.
   
2. Выбрать метод сортировки.
   
3. Упорядочить массив и табулировать результаты оценки.
   
4. Заменить метод и выполнить предидущий пункт.
   
5. Если все оцениваемые методы применены к выбранному массиву, то перейти к пункту 1.
   
6. Если выборка массивов достаточна, то прекратить эксперимент и обработать результаты оценок.
   

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