ieJiQnOs3sEtHwHZDOOXeYwK0Zs0EY2yD6P3KE35

1. 5-лекция: Алгоритмы сортировки данных

План:
1. Понятие сортировки
2. Классификация методов и алгоритмов
3. Строгие (прямые) методы сортировок
1.
2.
3.
метод прямого включения
метод прямого выбора
метод прямого обмена
© ТУИТ, кафедра СПП

2. Понятие сортировки

Сортировка (sorting) - это переупорядочивание данных
в памяти в регулярном виде по их ключам.
Регулярность значения ключа от начала к концу в
массиве рассматривают:
Как возрастание если r1 ≤ r2 ≤ … ≤ rn
Как убывание если r1 ≥ r2 ≥ … ≥ rn
Алгоритм сортировки не меняющий порядок следования
равных элементов называется устойчивым (stable).
Пример:
40 –> А, 20 –> B, 30 –> C, 40 –> D, 50 –> E
1) 20 –> B, 30 –> C, 40 –> D, 40 –> А, 50 –> E
2) 20 –> B, 30 –> C, 40 –> А, 40 –> D, 50 –> E
© ТУИТ, кафедра СПП

3. Понятие сортировки

Из всех задач программирования сортировка, возможно,
имеет самый богатый выбор алгоритмов решения. Вот
некоторые факторы, которые влияют на выбор алгоритма:
1) Порядок алгоритма
2) Сложность алгоритма
3) Временные характеристики операций
4) Ресурс памяти
5) Исходная упорядоченность входного множества
Эффективность сортировки можно рассматривать с
нескольких критериев:
• Количество сравнений (T);
• Количество перестановок (M);
• Нотация большого О. (≈T+M)
© ТУИТ, кафедра СПП

4. Классификация методов и алгоритмов

Разнообразие
алгоритмов
сортировки
требует
некоторой
их
классификации.
Выбран
один
из
применяемых
для
классификации
подходов,
ориентированный
прежде
всего
на
логические
характеристики применяемых алгоритмов. Согласно
этому подходу любой алгоритм сортировки использует
одну из следующих четырех стратегий (или их
комбинацию).
1). Стратегия выборки.
2). Стратегия включения.
3). Стратегия распределения.
4). Стратегия слияния.
По логически-циклическому просмотру данных:
1). Строгие (прямые) методы
2). Улучшенные методы
© ТУИТ, кафедра СПП

5. Сортировка методом прямого включения

Алгоритм :
Элементы
мысленно
делятся
на
уже
готовую
последовательность a1,...,ai-1 и исходную последовательность.
При каждом шаге, начиная с i = 2 и увеличивая i каждый раз на
единицу, из исходной последовательности извлекается i-й
элемент и перекладывается в готовую последовательность, при
этом он вставляется на нужное место.
Данные
Шаги
40
51
8
38
90
14
1
2
3
4
5
6
40
40
8
8
8
8
51
51
40
38
38
14
8
8
51
40
40
38
38
38
38
51
51
40
90
90
90
90
90
51
14
14
14
14
14
90
© ТУИТ, кафедра СПП
Т
М
12
8

6. Сортировка методом прямого включения

Программная реализация:
© ТУИТ, кафедра СПП

7. Сортировка методом прямого выбора

Алгоритм :
Выбирается элемент с наименьшим ключом. Он
меняется местами с первым элементом a 1. Затем этот
процесс повторяется с оставшимися n-1 элементами, n-2
элементами и т.д. до тех пор, пока не останется один,
самый "большой" элемент.
Данные
Шаги
40
51
8
38
90
14
1
2
3
4
5
6
40
8
8
8
8
8
51
51
14
14
14
14
8
40
40
38
38
38
38
38
38
40
40
40
90
90
90
90
90
51
14
14
51
51
51
90
© ТУИТ, кафедра СПП
Т
М
15
4

8. Сортировка методом прямого выбора

Программная реализация:
© ТУИТ, кафедра СПП

9. Сортировка с помощью прямого обмена (пузырьковая сортировка)

Алгоритм :
Алгоритм основывается на сравнении и смене мест для
пары соседних элементов и продолжении этого процесса
до тех пор, пока не будут упорядочены все элементы.
Данные
Шаги
40
51
8
38
90
14
1
2
3
4
5
6
40
8
8
8
51
40
14
14
8
51
40
38
38
14
51
40
90
38
38
51
14
90
90
90
© ТУИТ, кафедра СПП
Т
М
12
8

10. Сортировка с помощью прямого обмена

Программная реализация:
© ТУИТ, кафедра СПП

11.

© ТУИТ, кафедра СПП