Алгоритмы сортировки (лекция 5)

1.

2.

Пузырьковая сортировка
Сортировка пузырьком
Сортировка пузырьком — один из самых известных
алгоритмов
сортировки.
Здесь
нужно
последовательно сравнивать значения соседних
элементов и менять числа местами, если
предыдущее оказывается больше последующего.
Таким образом элементы с большими значениями
оказываются в конце списка, а с меньшими
остаются в начале.
1

3.

Пузырьковая сортировка
1.
Запускаем
алгоритм
сортировки
с
неотсортированным списком.
2. Сравниваем первый элемент со вторым
элементом списка. Если первый элемент больше
второго, меняем их местами.
3. Переходим к следующей паре элементов и
повторяем процесс сравнения и, если необходимо,
обмена.
4. Проходим весь список сначала до конца, затем
снова, пока все элементы не будут отсортированы.
5. При каждом проходе самый большой элемент
"всплывает"
на
правильную
позицию
и
перемещается в конец списка.
6. Обновляем индекс конца списка, так как
сортировка уже правильно упорядочила самый
большой элемент на последней позиции, и его
можно исключить из дальнейших проходов.
7. Повторяем шаги 2-6, пока все элементы не будут
отсортированы.
2

4.

Шейкерная сортировка
Сортировка перемешиванием
Шейкерная
сортировка
отличается
от
пузырьковой тем, что
она
двунаправленная:
алгоритм
перемещается
не
строго
слева
направо, а сначала
слева направо, затем
справа налево.
3

5.

Шейкерная сортировка
1. Задаем неотсортированный список.
2. Устанавливаем начальные значения переменных "левая
граница" и "правая граница". "Левая граница" указывает на
первый элемент списка, а "правая граница" указывает на
последний элемент списка.
3. Проходим по списку слева направо, сравнивая пары
элементов. Если левый элемент больше правого, меняем их
местами.
4. Переходим к следующей паре элементов и повторяем процесс сравнения и, если
необходимо, обмена.
5. После прохода по всем элементам списка, уменьшаем "правую границу" на 1. Это
связано с тем, что самый большой элемент "всплывает" на правильную позицию после
первого прохода.
6. Теперь проходим по списку справа налево, сравнивая пары элементов. Если правый
элемент меньше левого, меняем их местами.
7. Переходим к следующей паре элементов и повторяем процесс сравнения и, если
необходимо, обмена.
8. После прохода по всем элементам списка, увеличиваем "левую границу" на 1. Это
связано с тем, что самый маленький элемент "всплывает" на правильную позицию после
второго прохода.
9. Повторяем шаги 3-8 до тех пор, пока "левая граница" не станет больше "правой границы".
10. Когда "левая граница" становится больше "правой границы", сортировка считается
завершенной.
4

6.

Сортировка расческой
Сортировка расчёской
Сортировка
расчёской
—
улучшение
сортировки
пузырьком. Её идея состоит в
том,
чтобы
«устранить»
элементы
с
небольшими
значения в конце массива,
которые
замедляют
работу
алгоритма.
Если
при
пузырьковой
и
шейкерной
сортировках
при
переборе
массива сравниваются соседние
элементы,
то
при
«расчёсывании»
сначала
берётся достаточно большое
расстояние
между
сравниваемыми значениями, а
потом оно сужается вплоть до
минимального.
5

7.

Сортировка расческой
1. Задаем неотсортированный список.
2. Устанавливаем начальное значение переменной "шаг" равным длине списка.
3. Создаем переменную-флаг "замена" со значением true, которая указывает на
то, что еще есть возможность обмена элементов в списке.
4. Пока "шаг" больше 1 или "замена" равна true, выполняем следующие
действия:
- Устанавливаем "шаг" равным результату деления его на фактор уменьшения
(например, 1.3).
- Если "шаг" становится меньше 1, устанавливаем его равным 1.
- Итерируемся по списку с индексом от 0 до "длина списка минус шаг":
* Сравниваем элемент с индексом i с элементом, находящимся на i плюс "шаг".
- Если элемент с индексом i больше элемента с индексом i плюс "шаг", меняем
их местами и устанавливаем "замена" равной true.
- Если элемент с индексом i не меньше элемента с индексом i плюс "шаг",
оставляем их на своих местах и переходим к следующей паре элементов.
5. После прохода по списку с шагом 1, проверяем, было ли произведено обмены
элементов ("замена" равна true). Если не было, то сортировка считается
завершенной.
6. Повторяем шаги 2-5 до тех пор, пока список не будет полностью отсортирован.
5

8.

Сортировка вставками
Сортировка вставками
При
сортировке
вставками
массив
постепенно
перебирается
слева
направо.
При
этом
каждый последующий
элемент размещается
так, чтобы он оказался
между
ближайшими
элементами
с
минимальным
и
максимальным
значением.
6

9.

Сортировка вставками
1. Задаем неотсортированный список.
2. Итерируемся по списку от индекса 1 до конца списка:
- За текущий элемент принимаем элемент с текущим индексом.
- Создаем переменную "позиция" и устанавливаем ее равной текущему
индексу.
3. Пока "позиция" больше 0 и элемент, находящийся перед текущим
элементом, больше текущего элемента, выполняем следующие действия:
- Сдвигаем элемент, находящийся перед текущим элементом, на одну позицию
вперед.
- Уменьшаем "позицию" на 1.
4. Вставляем текущий элемент на "позицию".
5. Повторяем шаги 2-4 для каждого элемента списка.
6. После прохода по всем элементам список будет полностью отсортирован.
7

10.

Сортировка выбором
Сортировка выбором
Сначала
нужно
рассмотреть
подмножество массива и
найти в нём максимум
(или
минимум).
Затем
выбранное
значение
меняют
местами
со
значением
первого
неотсортированного
элемента. Этот шаг нужно
повторять до тех пор, пока
в массиве не закончатся
неотсортированные
подмассивы.
7

11.

Сортировка выбором
1. Задаем неотсортированный список.
2. Итерируемся по списку от начала до конца:
-За текущий элемент принимаем элемент с
текущим индексом.
- За минимальный элемент принимаем текущий
элемент.
- За индекс минимального элемента принимаем
текущий индекс.
3. Итерируемся по списку от текущего индекса
плюс один до конца:
- Если текущий элемент меньше минимального
элемента, обновляем значение минимального
элемента и его индекса.
4. Если индекс минимального элемента не равен
текущему индексу:
- Меняем местами элемент, находящийся на
текущей позиции, с минимальным элементом.
5. Повторяем шаги 2-4 для каждого элемента
списка.
6. После прохода по всем элементам список будет
полностью отсортирован.
Перейти на
новый индекс
Найти наименьший
элемент
Владимир
Владимирович
8

12.

Быстрая сортировка
Быстрая сортировка
Этот алгоритм состоит из
трёх шагов. Сначала из
массива нужно выбрать
один элемент — его обычно
называют опорным. Затем
другие элементы в массиве
перераспределяют
так,
чтобы элементы меньше
опорного оказались до него,
а большие или равные —
после.
А
дальше
рекурсивно
применяют
первые
два
шага
к
подмассивам
справа
и
слева от опорного значения.
9

13.

Быстрая сортировка
1. Задаем неотсортированный список и
выбираем опорный элемент.
2. Разделяем список на две части: элементы,
меньшие опорного элемента, и элементы,
большие опорного элемента.
3. Создаем два пустых подсписка для хранения
этих двух частей.
4. Итерируемся по списку от начала до конца, и
для каждого элемента:
- Если элемент меньше опорного, помещаем его
в левый подсписок.
- Если элемент больше опорного, помещаем его
в правый подсписок.
5. Рекурсивно повторяем шаги 1-4 для левого
подсписка.
6. Рекурсивно повторяем шаги 1-4 для правого
подсписка.
7.
Объединяем
отсортированный
левый
подсписок, опорный элемент и отсортированный
правый подсписок для получения полностью
отсортированного списка.
10

14.

Быстрая слиянием
Сортировка слиянием
Сортировка
слиянием
пригодится для таких структур
данных, в которых доступ к
элементам
осуществляется
последовательно (например,
для потоков). Здесь массив
разбивается на две примерно
равные части и каждая из них
сортируется по отдельности.
Затем два отсортированных
подмассива сливаются в один.
11

15.

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

16.

Я: изучаю только полный перебор
На собеседовании: напишите
какой-нибудь алгоритм
сортировки, кроме пузырьковой
Я:
A. Aho, J. Hopkroft, J.Ullman
«Структуры
данных
и
алгоритмы» - Глава 8 (8.1,
8.2, 8.3)
13