Разбор алгоритмов быстрой и пирамидальной сортировки

1.

Разбор алгоритмов быстрой и пирамидальной сортировки
Деловая презентация
2024

2.

Оглавление
• 1. Введение в сортировки
• 2. Быстрая сортировка (Quick Sort)
• 3. Пример работы быстрой сортировки
• 4. Пирамидальная сортировка (Heap Sort)
• 5. Пример работы пирамидальной
сортировки
• 6. Сравнение алгоритмов

3.

Введение в сортировки
• • Алгоритмы сортировки используются для
упорядочивания массивов данных.
• • Два популярных алгоритма: быстрая
сортировка и пирамидальная сортировка.

4.

Быстрая сортировка (Quick Sort)
• • Быстрая сортировка — это алгоритм
"разделяй и властвуй".
• • Основная идея — выбрать опорный
элемент и разделить массив на две части:
элементы меньше опорного и больше
опорного.

5.

Пример кода быстрой сортировки
• void Qsort(int *arr, int low, int hight) {
if (low < hight) {
int opEl = low;
int i = low;
int j = hight + 1;
while (j > i) {
while ((j > i) && (arr[--j] > arr[opEl])) {
}
while ((j > i) && (arr[++i] < arr[opEl])) {

6.

Пример работы быстрой сортировки
• • Исходный массив: [3, 6, 8, 10, 1, 2, 1]
• • Шаг 1: Опорный элемент — 3
• • Разделение на две части: [1, 2, 1] и [6, 8,
10]
• • Повторение процесса для каждой части.

7.

Пирамидальная сортировка (Heap Sort)
• • Пирамидальная сортировка основывается
на структуре данных "куча".
• • Массив преобразуется в двоичную кучу,
затем на каждом шаге самый большой
элемент перемещается в конец.

8.

Пример кода пирамидальной сортировки
• void Psort(int *arr, int size) {
for (int i = (size - 2) / 2; i >= 0; i--) {
down(arr, size, i);
}
for (int j = size - 1; j >= 0; j--) {
swap(arr, 0, j);
down(arr, j, 0);
}
}
void down(int *arr, int size, int root) {

9.

Пример работы пирамидальной сортировки
• • Исходный массив: [3, 6, 8, 10, 1, 2, 1]
• • Преобразование в кучу: [10, 6, 8, 3, 1, 2, 1]
• • Сортировка: на каждом шаге самый
большой элемент перемещается в конец.

10.

Сравнение алгоритмов
• | Алгоритм
| Время (среднее) |
Время (худшее) | Пространство |
|-----------------------|-----------------|---------------|--------------|
| Быстрая сортировка | O(n log n) |
O(n^2)
| O(log n) |
| Пирамидальная сортировка| O(n log n)
| O(n log n) | O(1)
|

11.

Заключение
• • Оба алгоритма имеют свои плюсы и
минусы.
• • Быстрая сортировка чаще используется
из-за простоты реализации и хорошей
производительности в среднем.
• • Пирамидальная сортировка полезна для
случаев, когда требуется стабильная
производительность в худшем случае.