Перетасовка Кнута. Быстрая сортировка (Quicksort) - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Перетасовка Кнута. Быстрая сортировка (Quicksort), слайд №1

Перетасовка Кнута. Быстрая сортировка (Quicksort), слайд №2

Перетасовка Кнута. Быстрая сортировка (Quicksort), слайд №3

Перетасовка Кнута. Быстрая сортировка (Quicksort), слайд №4

Перетасовка Кнута. Быстрая сортировка (Quicksort), слайд №5

Перетасовка Кнута. Быстрая сортировка (Quicksort), слайд №6

Перетасовка Кнута. Быстрая сортировка (Quicksort), слайд №7

Перетасовка Кнута. Быстрая сортировка (Quicksort), слайд №8

Перетасовка Кнута. Быстрая сортировка (Quicksort), слайд №9

Перетасовка Кнута. Быстрая сортировка (Quicksort), слайд №10

Перетасовка Кнута. Быстрая сортировка (Quicksort), слайд №11

Перетасовка Кнута. Быстрая сортировка (Quicksort), слайд №12

Перетасовка Кнута. Быстрая сортировка (Quicksort), слайд №13

Перетасовка Кнута. Быстрая сортировка (Quicksort), слайд №14

Перетасовка Кнута. Быстрая сортировка (Quicksort), слайд №15

Перетасовка Кнута. Быстрая сортировка (Quicksort), слайд №16

Перетасовка Кнута. Быстрая сортировка (Quicksort), слайд №17

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Перетасовка Кнута. Быстрая сортировка (Quicksort). Доклад-сообщение содержит 17 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Перетасовка Кнута На итерации i выбрать r между 0 и i при нормальном распределении Поменять a[i] и a[r]

Слайд 2

Описание слайда:

Слайд 3

Описание слайда:

Слайд 4

Описание слайда:

Слайд 5

Описание слайда:

Быстрая сортировка (Quicksort)

Слайд 6

Описание слайда:

Два классических алгоритма сортировки Критические компоненты в мировой вычислительной инфраструктуре Понимание научных основ этих алгоритмов даст нам возможность разрабатывать прикладные системы для решения реальных задач Быстрая сортировка входит в десятку самых полезных алгоритмов, разработанных в 20-м веке

Слайд 7

Описание слайда:

Слайд 8

Описание слайда:

Быстрая сортировка Основной план Перемешать элементы случайным образом Разбиение для элемента j a[j] оставить на месте Нет элементов меньше чем a[j] с правой стороны Нет элементов больше чем a[j] с левой стороны Отсортировать каждую часть рекурсивно

Слайд 9

Описание слайда:

Быстрая сортировка Повторять до тех пор, пока i и j не пересекутся Проверять i-ые элементы до тех пор пока a[i] < a[lo] Проверять j-ые элементы до тех пор пока a[j] > a[lo] Поменять местами a[i] и a[j] Видео 1

Слайд 10

Описание слайда:

Быстрая сортировка: реализация разбиения на Java

Слайд 11

Описание слайда:

Быстрая сортировка: реализация на Java

Слайд 12

Описание слайда:

Быстрая сортировка

Слайд 13

Описание слайда:

Быстрая сортировка

Слайд 14

Описание слайда:

Быстрая сортировка: реализация Не требует дополнительной памяти Выход из циклов. Обращайте особое внимание на условия выхода из циклов Ограничения. Проверка j == lo излишняя, но i == hi нет Рандомизация. Перетасовка нужна чтобы обеспечить гарантии производительности Равные ключи. Если присутствуют дубликаты, то можно использовать другой вариант алгоритма

Слайд 15

Описание слайда:

Быстрая сортировка: лучший случай Лучший случай. Количество сравнений ~ N log2N

Слайд 16

Описание слайда:

Быстрая сортировка: худший случай Худший случай. Количество сравнений ~ ½ N2

Слайд 17

Описание слайда:

Быстрая сортировка: свойства Худший случай. Квадратичное количество сравнений N + (N-1) + (N-2) + … + 1 ~ ½ N2 Средний случай. Количество сравнений ~ 1,39 Nlog2N На 39% сравнений больше, чем у сортировки слиянием Но, на практике, быстрее сортировки слиянием, потому что меньше перемещаются данные Перетасовка Гарантирует отсутствия худшего случая Предупреждение. Часть реализаций быстрой сортировки приводят к квадратичному времени выполнения если: Массив отсортирован или отсортирован в обратном порядке Имеется много дубликатов (даже если они перемешаны)