Lecture_3_1. Алгоритмы сортировки

1. Основы цифровых технологий

Алгоритмы сортировки

2. Алгоритмы сортировки

Алгоритм сортировки – алгоритм упорядочивания
элементов в некоторой структуре данных
(массиве, списке, векторе, дереве и т.д.) по
заданному критерию.
В рассматриваемых алгоритмах предполагается,
что сортировка осуществляется в оперативной
памяти и время выполнения элементарных
инструкций одинаково.
2

3. Алгоритмы сортировки

Основные алгоритмы сортировки:
• Пузырьком
• Вставкой
• Выбором
• С помощью двоичного дерева
• Блочная
• Слиянием
• Быстрая
3

4. Алгоритмы сортировки

Алгоритмы сортировки рассмотрены на примере
сортировки массива из N элементов в порядке
возрастания.
Примеры приведены для массива:
int arr[5] = {7, 1, 9, 5, 3};
4

5. Оценка сложности алгоритмов

Сложность алгоритма в наихудшем случае – это
функция, определяемая максимальным количеством
шагов, требуемых для обработки любого входного
набора данных размером n.
При этом для оценки сложности используется
асимптотическое обозначение O-большое.
5

6. Оценка сложности алгоритмов