Содержание
- 2. Пример: 2-Sum Подсчет количества инструкций, как функции от N.
- 3. Проблема сортировки Пример. Список студентов Сортировка. Переставить N записей в массиве в определенном порядке
- 4. Пример сортировки Цель. Отсортировать любые типы данных Пример. Отсортировать случайные вещественные числа в порядке возрастания
- 5. Пример сортировки Цель. Отсортировать любые типы данных Пример. Отсортировать строки из файла в алфавитном порядке
- 6. Пример сортировки Цель. Отсортировать любые типы данных Пример. Сортировка файлов в директории по имени
- 7. Сортировка выбором
- 8. Сортировка выбором На итерации i найти минимальный оставшийся элемент с индексом min Поменять местами a[i] и
- 9. Сортировка выбором Алгоритм. Сканирование идет слева направо Элементы слева от стрелки отсортированы и не меняются Нет
- 10. Сортировка выбором: внутренний цикл
- 11. Сортировка выбором: реализация на Java
- 12. Сортировка выбором: математический анализ Утверждение. Сортировка выбором использует (N-1) + (N-2) + … + 1 +
- 13. Видео 2
- 14. Сортировка вставками
- 15. Сортировка вставками На итерации i поменять a[i] с каждым большим элементом слева Видео 3
- 16. Сортировка вставками Алгоритм. Сканирование идет слева направо Элементы слева от стрелки отсортированы по возрастанию Элементы справа
- 17. Сортировка вставками: внутренний цикл
- 18. Сортировка вставками: реализация на Java
- 19. Сортировка вставками: математический анализ Утверждение. Сортировка вставками использует ~ N2/4 сравнений и ~ N2/4 перестановок при
- 20. Сортировка вставками: пример
- 21. Видео 4
- 22. Сортировка вставками: лучший и худший случай Лучший случай. Массив отсортирован; необходимо N-1 сравнений и 0 перестановок
- 23. Видео 5
- 24. Сортировка вставками: частично упорядоченный массив Инверсия — пара элементов, которая нарушает упорядоченность в массиве Частично упорядоченный
- 25. Видео 6
- 26. Сортировка Шелла
- 27. Сортировка Шелла: обзор Идея. Переупорядочить массив так, чтобы каждые h-е элементы (начиная с любого места в
- 28. h-sorting Сортировка вставками через шаг h Большой шаг => маленькие подмассивы Маленький шаг => массив почти
- 30. Сортировка Шелла Утверждение. g-отсортированный массив остается g-отсортированным даже после h-сортировки
- 32. Сортировка Шелла: реализация на Java
- 34. Видео 7
- 35. Сортировка Шелла: анализ Утверждение. В худшем случае количество сравнений при последовательности 3x + 1 равно O(N3/2)
- 36. Чем интересна Сортировка Шелла? Простая идея дает хорошую производительность На практике Работает быстро на небольших массивах
- 37. Перетасовка
- 38. Как перетасовать элементы в массиве? Цель. Переставить элементы в массиве так, чтобы они имели равномерное распределение
- 39. Сортировка Шелла Сгенерировать вещественные числа для каждого элемента Отсортировать массив
- 40. Перетасовка Кнута На итерации i выбрать r между 0 и i при нормальном распределении Поменять a[i]
- 41. Перетасовка Кнута На итерации i выбрать r между 0 и i при нормальном распределении Поменять a[i]
- 45. Скачать презентацию