Содержание
- 2. Изучаемые вопросы 3.1. Описание алгоритмов сортировки (продолжение) 3.2. Оценка методов сортировки Крючков А.В.
- 3. Цель курса – ознакомление обучающихся с различными методами сортировки и поиска и формирование навыка их практического
- 4. На предыдущем лекционном мероприятии мы рассмотрели 6 методов сортировки. В данной лекции нам предстоит узнать ещё
- 5. Крючков А.В. Вопрос 1.1. Гномья сортировка Гномья сортировка получила своё название в связи с тем, что
- 6. Крючков А.В. Вопрос 1.1. Гномья сортировка. Реализация При реализации программисты часто применяют не три, как я
- 7. Крючков А.В. Вопрос 1.1. Гномья сортировка. Улучшение Улучшение алгоритма связано с запоминаем места в наборе данных
- 8. Крючков А.В. Вопрос 1.1. Гномья сортировка. Оценка В лучшем и в худшем случае число сравнений будет
- 9. Крючков А.В. Вопрос 1.2. Сортировка выбором В классическом смысле применения данного алгоритма существует два варианта его
- 10. Крючков А.В. Вопрос 1.2. Сортировка выбором. 1-й вариант Перебор, начинающийся с первого элемента, направлен на то,
- 11. Крючков А.В. Вопрос 1.2. Сортировка выбором. 2-й вариант Перебор начинается с первого элемента. Он направлен на
- 12. Крючков А.В. Вопрос 1.2. Сортировка выбором. Оценка В лучшем и в худшем случае число сравнений будет
- 13. Крючков А.В. Вопрос 1.3. Пирамидальная сортировка Данный метод получил своё название по причине аналогии структуры данных,
- 14. Крючков А.В. Вопрос 1.3. Пирамидальная сортировка На первом шаге алгоритма сортировки строится двоичное дерево. Массив при
- 15. Крючков А.В. Вопрос 1.3. Пирамидальная сортировка На втором шаге сортировки выполняется обмен элементов массива между собой
- 16. Крючков А.В. Вопрос 1.3. Пирамидальная сортировка 1. Последовательно выбираются ветви дерева. Для массива с рис.3 это
- 17. Крючков А.В. Вопрос 1.3. Пирамидальная сортировка 3. Дерево на основе изменённого массива перестраивается 4. Процесс повторяется
- 18. Крючков А.В. Вопрос 1.3. Пирамидальная сортировка 1. Полученный в результате просеивания максимальный элемент, стоящий первым в
- 19. Крючков А.В. Вопрос 1.3. Пирамидальная сортировка. Оценка В лучшем и в худшем случае число сравнений будет
- 20. Крючков А.В. Вопрос 1.4. Быстрая сортировка В основу алгоритма данного метода сортировки положен принцип разбиения массива
- 21. Крючков А.В. Вопрос 1.4. Быстрая сортировка В случае если пивот выбирается произвольно, алгоритм называют рандомизированным. Выбор
- 22. В лучшем случае число сравнений равно n*log2(n) . В худшем случае число сравнений будет равно n2.
- 23. Метод основан на разбиении массива на множество частей, содержащих только 1 элемент. Такие массивы считаются отсортированными.
- 24. 1. Если исходный массив (подаваемый на вход программы) состоит из одного значимого элемента – следует завершить
- 25. 1. Формируется массив размером, равным сумме размеров подмассивов, участвующих в слиянии. 2. Попарно сравниваются элементы массивов.
- 26. Всего используется три магнитные ленты — основная, на которой записаны неотсортированные данные и две вспомогательные. Данные
- 27. Крючков А.В. Вопрос 1.5. Сортировка слиянием. Оценка Во всех случаях в методе будет выполнено n* log2(n)
- 28. В данном алгоритме сортировки используется некий диапазон чисел сортируемого массива для определения количества совпадающих элементов в
- 29. Массив из n элементов (n целых чисел в диапазоне от 0 до k-1, где k ∈
- 30. Шаг четвёртый. Проходим по исходному массиву сначала до конца. Число, которое встречается в исходном массиве, является
- 31. Крючков А.В. Вопрос 1.6. Сортировка подсчетом. Оценка Во всех случаях в методе будет выполнено (n +
- 32. Необходимо разбить массив на ряд блоков (или карманов), размер которых определяется характером значений в массиве. В
- 33. На первом шаге (первый проход исходного массива) выявляются наименьший и наибольший по значению элементы массива. На
- 34. На последующих шагах алгоритма внутри блоков происходят те же действия, которые были описаны в первых его
- 35. Крючков А.В. Вопрос 1.7. Блочная сортировка. Оценка Во всех случаях в методе будет выполнено n2 сравнений.
- 36. Аналогична методу сортировки подсчётом. Но в отличие от него в данном методе мы не сразу заводим
- 37. Крючков А.В. Вопрос 1.8. Голубиная сортировка. Оценка Во всех случаях в методе будет выполнено n +
- 38. LSD – это least significant digit, или наименьшая значащая цифра. Метод лучше использовать для сортировки чисел,
- 39. Шаг первый. Создадим вспомогательный двумерный массив длины 10 (от 0 до 9) и ширины, равной размерности
- 40. Шаг третий. Выполняем второй проход по исходному массиву. Определяем цифру последнего разряда элемента исходного массива и
- 41. Шаг пятый. Выполняем третий проход по исходному массиву. Определяем цифру второго с конца разряда элемента исходного
- 42. Шаг седьмой. Выполняем четвёртый проход по исходному массиву. Определяем цифру третьего с конца разряда элемента исходного
- 43. Крючков А.В. Вопрос 1.9. Сортировка LSD. Оценка Во всех случаях в методе будет выполнено n сравнений.
- 44. MSD – это most significant digit иои наибольшая значащая цифра. Аналогичен методу сортировки LSD. Но действует
- 45. Шаги алгоритма метода MSD такие же, как для метода LSD. На рисунках дано их отражение в
- 46. Крючков А.В. Вопрос 1.10. Сортировка MSD. Оценка Во всех случаях в методе будет выполнено n сравнений.
- 47. Этот метод сортировки выстроен на основе битонных последовательностей и операций над ними. Это параллельный алгоритм сортировки
- 48. Последовательности, которые полностью включены в битонную, как и последовательности, состоящие из одного или двух элементов, является
- 49. Шаг первый. Перед тем, как сделать первый проход исходного массива определяем число элементов в нём. Если
- 50. Шаг третий. Выбираем точку «отсечения»: Nотс = (Nmax - Nmin) / 2. Выполняем второй проход исходного
- 51. В завершении алгоритма значения элементов вспомогательных массивов, полученных на последней итерации перед остановкой, последовательно переписываются в
- 52. Крючков А.В. Вопрос 1.11. Битонная сортировка. Оценка Во всех случаях в методе будет выполнено n +
- 53. Метод сортировки Timsort поддерживает гибридный алгоритм, соединяющий сортировку вставками и слиянием. Изобретен был в 2002 году
- 54. Принципы работы алгоритма: - исходный массив делится на подмассивы; - подмассивы сортируются вставками; - сортировкой слиянием
- 55. - отсортированные элементы последних двух подмассивов записываются в исходный массив, используя сортировку слиянием. Если общее число
- 56. Крючков А.В. Вопрос 1.12. Сортировка Timsort. Оценка В лучшем случае будет выполнено n сравнений. В среднем
- 57. Крючков А.В. Вопрос 2. Оценка методов сортировки Частично оценки методам сортировки уже были даны в виде
- 58. Крючков А.В. Вопрос 2. Оценка методов сортировки. Тесты Все тесты поделены на четыре группы. Первая группа
- 59. Крючков А.В. Вопрос 2. Оценка методов сортировки. Тесты Четвёртая группа состоит из нескольких тестов с полностью
- 60. 1. С чем связано улучшение алгоритма гномьей сортировки? 2. Опишите правила построения двоичного дерева в алгоритме
- 61. 10. Назовите основное отличие голубиной сортировки от сортировки подсчётом. 11. Что такое LSD? 12. Что такое
- 63. Скачать презентацию