ТЕМА УРОКА: «АЛГОРИТМЫ СОРТИРОВКИ» - В чем состоит задача сортировки?
- Зачем нужно изучать сортировку?
- Сортировка пузырьком
- Сортировка выбором
- Сортировка вставками
- Сортировка слиянием
1. В ЧЕМ СОСТОИТ ЗАДАЧА СОРТИРОВКИ? - Сортировка – упорядочЕние заданного списка элементов.
- Вход: последовательность, состоящая из n чисел (a1, a2, …, an).
- Выход: перестановка (изменение порядка) (a1’, a2’,…, an’) входной последовательности таким образом, что a1’ ≤ a2’ ≤ … ≤ an’.
- Входная последовательность представляется в виде n-элементного массива.
1. В ЧЕМ СОСТОИТ ЗАДАЧА СОРТИРОВКИ? - Устойчивый алгоритм – не меняет относительное расположение одинаковых элементов в массиве.
- Если номера двух одинаковых элементов i < j, то в отсортированном списке i’ < j’
- Обменный (in-place) алгоритм – для его работы не требуется дополнительная память, которая зависит от размера массива.
1. В ЧЕМ СОСТОИТ ЗАДАЧА СОРТИРОВКИ? - Как правило, сортируются только ключи, которые существуют в записях (строчка в таблице, список, объект)
- Базовая операция – сравнение двух элементов: ai ≤ aj (кроме некоторых специальных алгоритмов)
- Время работы: Ω(n log n)
- Рассматривается сортировка по возрастанию
2. ЗАЧЕМ НУЖНО ИЗУЧАТЬ СОРТИРОВКУ? - Во многих приложениях нужно сортировать данные
- Выдача информации (отчеты, списки)
- Сортировка для бинарного поиска
- Геометрические алгоритмы (вывод графики, поиск выпуклой оболочки)
- Многие алгоритмы требуют предварительную сортировку данных
- Алгоритмы сортировки – прекрасный способ изучения алгоритмов (большое количество алгоритмов, много техник).
Download
Do'stlaringiz bilan baham: |
