Содержание
- 2. Сортировка включениями с убывающим шагом. Метод Шелла Хоар, Флойд, Шелл: для алгоритмов сортировки, перемещающих в последовательности
- 3. Пример работы сортировки Шелла На первом проходе выделим в подпоследовательности элементы, отстоящие друг от друга на
- 4. Пример работы сортировки Шелла, продолжение В результате 4-сортировки получим последовательность: _________________________________ | | | | 40
- 5. Выбор шага в сортировке Шелла В сортировке методом Шелла можно использовать любую убывающую последовательность шагов ht,
- 6. Анализ эффективности метода Утверждение Если k-отсортированная последовательность i-сортируется (k > i), то она остается k-отсортированной. →
- 7. Алгоритм процедура Вставка(b, h) // b — номер первого элемента последовательности // h – величина шага
- 8. Алгоритм, продолжение Основная программа: // Выбор начального шага: h := 1; пока h h := 3*h
- 9. Пример работы сортировки Шелла для массива: 5 12 4 21 7 2 13 16 1 10
- 10. Пирамидальная сортировка При сортировке методом простого выбора на каждом шаге выполняется линейный поиск минимального элемента. Линейная
- 12. Свойство пирамиды Пусть дана последовательность h1, ..., hn. Элемент hi образует пирамиду в этой последовательности, если
- 13. Полная пирамида при n=15 Полная пирамида может быть изображена в виде корневого бинарного дерева, в котором
- 14. Пример полной пирамиды при n=12 Если число элементов в полной пирамиде не равно 2k – 1,
- 15. Идея метода пирамидальной сортировки Подготовка к сортировке: входная неупорядоченная последовательность перестраивается в пирамиду. Сортировка: входная и
- 16. Построение пирамиды a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 Шаг 1, i=5: 52
- 17. Сортировка На каждом шаге сортировки первый элемент массива, т. е. максимальный элемент пирамиды, переносится в начало
- 18. Сортировка, продолжение Таким образом, для новой входной последовательности a1, ..., ai-1 условия пирамиды выполнены для всех
- 20. Алгоритм процедура Просеивание (i, n) // i – номер элемента, который нужно просеять // n –
- 21. Алгоритм, продолжение Основная программа: Шаг 1. Построение пирамиды: i := N / 2; пока i ≥
- 22. Анализ Число итераций цикла в процедуре просеивания не превосходит высоты пирамиды. Высота полного бинарного дерева из
- 23. Построение пирамиды 5 4 12 21 7 2 13 16 1 10 3 Исходный массив: Шаг
- 24. Сортировка на пирамиде (продолжение примера) Шаг 1: обмен 21 13 16 12 10 2 4 5
- 25. Сортировка на пирамиде (продолжение примера) Шаг 4: обмен 12 7 10 5 1 2 4 3
- 26. Сортировка на пирамиде (продолжение примера) Шаг 7: обмен 5 4 3 2 1 7 10 12
- 27. родился 11 января 1934, Коломбо, Цейлон, Британская империя, ныне Шри Ланка) — английский учёный, специализирующийся в
- 28. Другие известные результаты его работы: Язык Z спецификаций и параллельная модель взаимодействия последовательных процессов (CSP, Communicating
- 29. Биография Родился в Коломбо в Шри-Ланке. Получил степень бакалавра по классическим языкам в Оксфордском университете в
- 30. Биография, продолжение В 1977 году вернулся в Оксфорд, как профессор вычислительной техники, чтобы возглавить исследовательскую группу
- 31. Хоар в Академгородке (PSI 2003)
- 32. Среди участников конференции
- 33. Сортировка с разделением. Быстрая сортировка Ч. Э. Р. Хоар Это метод сортировки, при котором обмениваются местами
- 34. Сортировка разделением, идея алгоритма Отсортируем любым методом обмена отдельно левую часть, не затрагивая элементов правой части,
- 35. Получается, что в процессе дробления исходной задачи на подзадачи мы приходим к тривиальным подзадачам: сортировке последовательностей
- 36. В процессе разделения мы соберем в левой части последовательности все элементы аi ≤ х, а в
- 37. Процесс разделения i = l; j = r; цикл пока ai i := i + 1;
- 38. Комментарии Циклы по встречным индексам переносят из средней части в левую или правую элементы, строго меньшие
- 39. Проверка того, что бегущие индексы не выходят за границы l...r, строго говоря, необходима, но фактически не
- 40. Цикл оканчивается при i ≥ j. Однако нам еще надо определить медиану. Определенные границы левой части
- 41. Процесс разделения, пример Разделение: 40 51 8 38 89 1 15 63 Начало: i x j
- 42. Разделение
- 43. Анализ Процессу разбиения подвергается весь массив, следовательно выполняется N сравнений. Число обменов? Пусть после разделения х
- 44. Анализ, продолжение Просуммируем всевозможные варианты выбора медианы и разделим эту сумму на N, в результате получим
- 45. Анализ, продолжение Однако в худшем случае сортировка становится «медленной». Например, когда в качестве пилотируемого элемента всегда
- 46. Быстрая сортировка (пример) 5 4 12 21 7 2 13 16 1 10 3 Исходный массив:
- 47. Быстрая сортировка (продолжение примера) 1 4 2 3 5 12 10 7 13 16 21 Четвертое
- 49. Скачать презентацию