Программирование и основы алгоритмизации. Тема 7. Алгоритмы и структуры данных. Сортировка

1.

Программирование и основы алгоритмизации
Тема 7. Алгоритмы и структуры
данных. Сортировка.
Шевченко А. В.
Тема 07. Алгоритмы и структуры данных. Сортировка.
1

2.

Программирование и основы алгоритмизации
Роль алгоритмов и структур данных
Предметная область
Модель процессов
Модель объектов
Алгоритмы
Структуры
данных
Программы
Шевченко А. В.
Тема 07. Алгоритмы и структуры данных. Сортировка.
2

3.

Программирование и основы алгоритмизации
Понятие алгоритма
Алгоритм — это конечный набор правил, который
определяет последовательность операций для решения
конкретного множества задач и обладает пятью
важными чертами: конечность, определённость, ввод,
вывод, эффективность.
Дональд Эрвин Кнут
Шевченко А. В.
Тема 07. Алгоритмы и структуры данных. Сортировка.
3

4.

Программирование и основы алгоритмизации
Свойства алгоритма
Дискретность — алгоритм должен представлять процесс решения задачи как
последовательное выполнение некоторых простых шагов. При этом для выполнения
каждого шага алгоритма требуется конечный отрезок времени.
Детерминированность — определённость. В каждый момент времени следующий
шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм
должен выдавать один и тот же результат для одних и тех же исходных данных.
Конечность — при корректно заданных исходных данных алгоритм должен
завершать работу и выдавать результат за конечное число шагов.
Масштабируемость — алгоритм должен быть применим к разным наборам
исходных данных.
Результативность — завершение алгоритма определенными результатами.
Эффективность — завершение алгоритма определенными результатами за
определенное число шагов (время).
Шевченко А. В.
Тема 07. Алгоритмы и структуры данных. Сортировка.
4

5.

Программирование и основы алгоритмизации
Пример алгоритма - задача о Ханойских башнях
Легенда. В одном из буддийских монастырей монахи уже тысячу лет
занимаются перекладыванием колец. Они располагают тремя пирамидами,
на которых надеты кольца разных размеров. В начальном состоянии 64
кольца были надеты на первую пирамиду и упорядочены по размеру. Монахи
должны переложить все кольца с первой пирамиды на вторую, выполняя
единственное условие — кольцо нельзя положить на кольцо меньшего
размера. При перекладывании можно использовать все три пирамиды.
Монахи перекладывают одно кольцо за одну секунду. Как только они
закончат свою работу, наступит конец света...
Шевченко А. В.
Тема 07. Алгоритмы и структуры данных. Сортировка.
5

6.

Программирование и основы алгоритмизации
Решение задачи о Ханойских башнях
Шаг 4
Шаг 1
Шаг 5
Шаг 2
Шаг 6
Шаг 3
Шаг 7
Число шагов алгоритма вычисляется по формуле 2N
− 1, где N − число колец .
Для перекладывания 64-х колец потребуется 18 446 744 073 709 551 615 шагов.
При скорости в одно перекладывание в секунду, потребуется около 584 542 046 091 лет.
Шевченко А. В.
Тема 07. Алгоритмы и структуры данных. Сортировка.
6

7.

Программирование и основы алгоритмизации
Эффективность алгоритмов
Временные функции
сложности
Полиномиальные
(P-задачи)
f(n)
10 20
10 18
10 16
10 14
10 12
10 10
10 8
10 6
10 4
10 2
1
1
Шевченко А. В.
Экспоненциальные
(NP-задачи)
22
n
nn n! 10 n
2n
n 10
n5
n2
n
10
Тема 07. Алгоритмы и структуры данных. Сортировка.
100 n
7

8.

Программирование и основы алгоритмизации
Трансвычислительные задачи
Не существует системы обработки данных, искусственной или
естественной, которая могла бы обрабатывать более 2*1047
бит в секунду на грамм своей массы.
Ханс Бреммерман
Предел Бреммермана
=
1093 бит
Трансвычислительные
задачи
Шевченко А. В.
Тема 07. Алгоритмы и структуры данных. Сортировка.
8

9.

Программирование и основы алгоритмизации
Представления алгоритмов
Блок-схема
Псевдокод
Начало
Ввод N
Ввод N
I=1
F=1
I=1
F=1
Да
F=F*I
I <= N
Нет
ЦИКЛ ПОКА I <= N
F=F*I
ВСЁ-ЦИКЛ
Вывод F
Вывод F
Конец
Шевченко А. В.
Тема 07. Алгоритмы и структуры данных. Сортировка.
9

10.

Программирование и основы алгоритмизации
Блок-схемы алгоритмов
ГОСТ 19.701-90 (ИСО 5807-85). Схемы алгоритмов, программ, данных и систем. Условные
обозначения и правила выполнения.
Наименование
Терминатор
Обозначение
Функция
Элемент отображает вход из внешней среды или выход из нее (наиболее
частое применение − начало и конец программы).
Процесс
Решение
Предопределенный
процесс
Выполнение одной или нескольких операций, обработка данных любого
вида
Отображает решение с одним входом и двумя или более альтернативными выходами, из которых только один может быть выбран.
Символ отображает выполнение процесса, который определен в другом
месте программы
Преобразование данных в форму, пригодную для обработки (ввод) или
Данные
отображения результатов обработки (вывод).
Символ отображает выход в часть схемы и вход из другой части этой
Соединитель
Комментарий
Шевченко А. В.
схемы.
Используется для более подробного описания шага, процесса или
группы процессов.
Тема 07. Алгоритмы и структуры данных. Сортировка.
10

11.

Программирование и основы алгоритмизации
Классы алгоритмов
Сортировка
Поиск
Алгоритмы
Обходы графов
Оптимизация
Шевченко А. В.
Тема 07. Алгоритмы и структуры данных. Сортировка.
11

12.

Программирование и основы алгоритмизации
Сортировка массивов
Код
ТОВАР
Наименование
Цена
Код
Наименование
Цена
44
Яблоки
35.50
55
Апельсины
29.90
12
Бананы
22.00
...
...
...
typedef struct
Ключ
{
short code;
char name[10];
float price;
Уникальный
Неуникальный
} PROD;
PROD prod[8];
Шевченко А. В.
Сортировка - упорядочение массива в
соответствии со значениями ключа
Тема 07. Алгоритмы и структуры данных. Сортировка.
12

13.

Программирование и основы алгоритмизации
Алгоритмы сортировки массивов
Сортировка
Сортировка с
помощью
включения
Сортировка с
помощью
выделения
Сортировка с
помощью обмена
Прямые
n2
Прямое
включение
Двоичное
включение
Прямой
выбор
Пузырьковая
Улучшенные
n*log(n)
Включение с
уменьшающимися
расстояниями (Шелла)
Шевченко А. В.
Шейкерная
С помощью дерева
Тема 07. Алгоритмы и структуры данных. Сортировка.
Разделение
(быстрая)
13

14.

Программирование и основы алгоритмизации
Сортировка прямым включением (StraightInsertion)
44
55
12
42
94
18
06
67
Шаг 1
44
55
12
42
94
18
06
67
Шаг 2
12
44
55
42
94
18
06
67
Шаг 3
12
42
44
55
94
18
06
67
Шаг 4
12
42
44
55
94
18
06
67
Шаг 5
12
18
42
44
55
94
06
67
Шаг 6
06
12
18
42
44
55
94
67
Шаг 7
06
12
18
42
44
55
67
94
Эффективность (n2-n)/2
Шевченко А. В.
Тема 07. Алгоритмы и структуры данных. Сортировка.
14

15.

Программирование и основы алгоритмизации
Пример сортировки прямым включением
void StraightInsertion(PROD* prod, int n)
{
for(int i = 1; i < n; i++)
{
PROD tmp = prod[i];
int j;
for(j = i; j > 0 && tmp.code < prod[j-1].code; j--)
prod[j] = prod[j-1];
prod[j] = tmp;
}
}
Шевченко А. В.
Тема 07. Алгоритмы и структуры данных. Сортировка.
15

16.

Программирование и основы алгоритмизации
Сортировка прямым выбором (StraightSelection)
44
55
12
42
94
18
06
67
Шаг 1
06
55
12
42
94
18
44
67
Шаг 2
06
12
55
42
94
18
44
67
Шаг 3
06
12
18
42
94
55
44
67
Шаг 4
06
12
18
42
94
55
44
67
Шаг 5
06
12
18
42
44
55
94
67
Шаг 6
06
12
18
42
44
55
94
67
Шаг 7
06
12
18
42
44
55
67
94
Эффективность (n2-n)/2
Шевченко А. В.
Тема 07. Алгоритмы и структуры данных. Сортировка.
16

17.

Программирование и основы алгоритмизации
Пример сортировки прямым выбором
void StraightSelection(PROD* prod, int n)
{
for(int i = 0; i < n-1; i++)
{
PROD tmp = prod[i];
int k = i;
for(int j = i+1; j < n; j++)
if(prod[j].code < tmp.code)
{
tmp = prod[j];
k = j;
}
prod[k] = prod[i];
prod[i] = tmp;
}
}
Шевченко А. В.
Тема 07. Алгоритмы и структуры данных. Сортировка.
17

18.

Программирование и основы алгоритмизации
Сортировка прямым обменом (BubbleSort)
44
55
12
42
94
18
06
67
Шаг 1
06
44
55
12
42
94
18
67
Шаг 2
06
12
44
55
18
42
94
67
Шаг 3
06
12
18
44
55
42
67
94
Шаг 4
06
12
18
42
44
55
67
94
Шаг 5
06
12
18
42
44
55
67
94
Шаг 6
06
12
18
42
44
55
67
94
Шаг 7
06
12
18
42
44
55
67
94
Эффективность (n2-n)/2
Шевченко А. В.
Тема 07. Алгоритмы и структуры данных. Сортировка.
16

19.

Программирование и основы алгоритмизации
Пример сортировки прямым обменом
void BubbleSort(PROD* prod, int n)
{
for(int i = 1; i < n; i++)
for(int j = n-1; j >= i; j--)
if(prod[j-1].code > prod[j].code)
{
PROD tmp = prod[j-1];
prod[j-1] = prod[j];
prod[j] = tmp;
}
}
Шевченко А. В.
Тема 07. Алгоритмы и структуры данных. Сортировка.
19

20.

Программирование и основы алгоритмизации
Шейкерная сортировка (ShakerSort)
44
55
12
42
94
18
06
67
Шаг 1
06
44
55
12
42
94
18
67
Шаг 2
06
44
12
42
55
18
67
94
Шаг 3
06
12
44
18
42
55
67
94
Шаг 4
06
12
18
42
44
55
67
94
Эффективность (n2-n(k+ln(n)))/2
Шевченко А. В.
Тема 07. Алгоритмы и структуры данных. Сортировка.
20

21.

Программирование и основы алгоритмизации
Пример шейкерной сортировки
void ShakerSort(PROD* prod, int n)
{
int L = 1, R = n-1, k = n-1;
do
{
for(int j = R; j >= L; j--)
if(prod[j-1].code > prod[j].code)
{
PROD tmp = prod[j-1]; prod[j-1] = prod[j]; prod[j] = tmp;
k = j;
}
L = k+1;
for(int j = L; j <= R; j++)
if(prod[j-1].code > prod[j].code)
{
PROD tmp = prod[j-1]; prod[j-1] = prod[j]; prod[j] = tmp;
k = j;
}
}
R = k-1;
} while(L < R)
Шевченко А. В.
Тема 07. Алгоритмы и структуры данных. Сортировка.
21

22.

Программирование и основы алгоритмизации
Пример шейкерной сортировки, вариант 2
void ShakerSort2(PROD* prod, int n)
{
int LkR[3] = {0, n-1, n};
// L, k, R
for(int* B = &LkR[1], d = -1; B[-1] < B[1]; d = -d)
{
for(int j = B[-d]+d; j != B[d]; j += d)
if(prod[j-1].code > prod[j].code)
{
PROD tmp = prod[j-1];
prod[j-1] = prod[j];
prod[j] = tmp;
B[0] = j;
}
B[d] = B[0];
}
}
Шевченко А. В.
Тема 07. Алгоритмы и структуры данных. Сортировка.
21

23.

Программирование и основы алгоритмизации
Улучшенный метод сортировки Шелла (ShellSort)
(сортировка включением с уменьшающимися расстояниями)
44
55
12
42
94
18
06
67
h=4
Шаг 1
44
18
06
42
94
55
12
67
h=2
Шаг 2
06
18
12
42
44
55
94
67
h=1
Шаг 3
06
12
18
42
44
55
67
94
Последовательность расстояний 1, 3, 7, 15, 31... t = log2n-1, ht = 1, hk-1 = 2hk+1
Эффективность n1.2
Шевченко А. В.
Тема 07. Алгоритмы и структуры данных. Сортировка.
22

24.

Программирование и основы алгоритмизации
Пример сортировки методом Шелла
void ShellSort(PROD* prod, int n)
{
for(int t = 24; t > 1; t--)
{
if(!(n >> t)) continue;
int d = (1 << (t-1))-1;
for(int ofs = 0; ofs < d; ofs++)
for(int i = d+ofs; i < n; i += d)
{
PROD tmp = prod[i];
int j;
for(j = i; j >= d && tmp.code < prod[j-d].code; j -= d)
prod[j] = prod[j-d];
prod[j] = tmp;
}
}
}
Шевченко А. В.
Тема 07. Алгоритмы и структуры данных. Сортировка.
22

25.

Программирование и основы алгоритмизации
Улучшенный метод сортировки Шелла (ShellSort)
5
8
Шевченко А. В.
2
4
5
3
6
2
7
5
1
Тема 07. Алгоритмы и структуры данных. Сортировка.
4
9
3
5
2
22

26.

Программирование и основы алгоритмизации
Метод быстрой сортировки Хоара (QuickSort)
(сортировка разделением)
44
55
12
42
94
18
06
67
Шаг 1
06
18
12
42
94
55
44
67
Шаг 2
06
12
18
42
44
55
94
67
Шаг 3
06
12
18
42
44
55
67
94
Эффективность n*log(n)
Шевченко А. В.
Тема 07. Алгоритмы и структуры данных. Сортировка.
23

27.

Программирование и основы алгоритмизации
Пример быстрой сортировки
void sort(PROD* prod, int L, int R)
{
int i = L, j = R;
PROD x = prod[(L+R)/2];
do
{
while(prod[i].code < x.code) i++;
while(x.code < prod[j].code) j--;
if(i <= j)
{
PROD tmp = prod[i]; prod[i] = prod[j]; prod[j] = tmp;
i++; j--;
}
} while(i < j);
void QuickSort(PROD* prod, int n)
if(L < j) sort(prod, L, j); {
sort(prod, 0, n-1);
if(i < R) sort(prod, i, R); }
}
Шевченко А. В.
Тема 07. Алгоритмы и структуры данных. Сортировка.
24

28.

Программирование и основы алгоритмизации
Пример быстрой сортировки
5
8
Шевченко А. В.
2
4
5
3
6
2
7
5
1
Тема 07. Алгоритмы и структуры данных. Сортировка.
4
9
3
5
2
24