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

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

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

А. В.
Понятие алгоритма
Алгоритм — это конечный набор правил, который определяет

последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность.
Дональд Эрвин Кнут

выполнение некоторых простых шагов. При этом для выполнения каждого шага

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

Программирование и основы алгоритмизации

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

4

Шевченко А. В.

Свойства алгоритма

занимаются перекладыванием колец. Они располагают тремя пирамидами, на которых надеты

кольца разных размеров. В начальном состоянии 64 кольца были надеты на первую пирамиду и упорядочены по размеру. Монахи должны переложить все кольца с первой пирамиды на вторую, выполняя единственное условие — кольцо нельзя положить на кольцо меньшего размера. При перекладывании можно использовать все три пирамиды. Монахи перекладывают одно кольцо за одну секунду. Как только они закончат свою работу, наступит конец света...

Программирование и основы алгоритмизации

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

5

Шевченко А. В.

Пример алгоритма - задача о Ханойских башнях

А. В.
Решение задачи о Ханойских башнях
Число шагов алгоритма вычисляется по

формуле 2N − 1, где N − число колец .
Для перекладывания 64-х колец потребуется 18 446 744 073 709 551 615 шагов.
При скорости в одно перекладывание в секунду, потребуется около 584 542 046 091 лет.

А. В.
Эффективность алгоритмов
Временные фукции сложности
Полиномиальные
(P-задачи)
Экспоненциальные
(NP-задачи)

А. В.
Трансвычислительные задачи
Не существует системы обработки данных, искусственной или естественной,

которая могла бы обрабатывать более 2*1047 бит в секунду на грамм своей массы.
Ханс Бреммерман

1093 бит

Предел Бреммермана

Трансвычислительные задачи

А. В.
Представления алгоритмов
Блок-схема
Псевдокод


Ввод N
I = 1
F = 1
ЦИКЛ ПОКА I

<= N
F = F * I
ВСЁ-ЦИКЛ
Вывод F

Начало

Ввод N

I = 1
F = 1

I <= N

F = F * I

Вывод F

Конец

Да

Нет

А. В.
Блок-схемы алгоритмов
ГОСТ 19.701-90 (ИСО 5807-85). Схемы алгоритмов, программ, данных

и систем. Условные обозначения и правила выполнения.

Наименование

Терминатор

Процесс

Решение

Предопределенный процесс

Данные

Соединитель

Комментарий

Обозначение

Функция

Элемент отображает вход из внешней среды или выход из нее (наиболее частое применение − начало и конец программы).
Выполнение одной или нескольких операций, обработка данных любого вида
Отображает решение с одним входом и двумя или более альтернатив-ными выходами, из которых только один может быть выбран.
Символ отображает выполнение процесса, который определен в другом месте программы
Преобразование данных в форму, пригодную для обработки (ввод) или отображения результатов обработки (вывод).
Символ отображает выход в часть схемы и вход из другой части этой схемы.
Используется для более подробного описания шага, процесса или группы процессов.

А. В.
Классы алгоритмов
Сортировка
Алгоритмы
Поиск
Оптимизация
Обходы графов

А. В.
Сортировка массивов
Код
Наименование

Цена

44
Яблоки
35.50

55
Апельсины
29.90

12
Бананы
22.00

...
...
...

typedef struct
{
short code;
char name[10];

float price;
} PROD;

PROD prod[8];

Ключ

Уникальный

Неуникальный

Сортировка - упорядочение массива в соответствии со значениями ключа

А. В.
Алгоритмы сортировки массивов
Сортировка
Сортировка с помощью включения
Сортировка с помощью выделения
Сортировка

с помощью обмена

Прямое включение

Двоичное включение

Прямой выбор

Пузырьковая

Шейкерная

Включение с уменьшающимися расстояниями (Шелла)

Разделение
(быстрая)

С помощью дерева

n2

n*log(n)

А. В.
Сортировка прямым включением (StraightInsertion)
44
55
12
42
94
18
06
67
12
44
55
42
94
18
06
67
12
42
44
55
94
18
06
67
12
42
44
55
94
18
06
67
12
18
42
44
55
94
06
67
06
12
18
42
44
55
94
67
06
12
18
42
44
55
67
94
44
55
12
42
94
18
06
67
Шаг 1
Шаг 2
Шаг 3
Шаг 4
Шаг 5
Шаг

6

Шаг 7

Эффективность (n2-n)/2

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

Шевченко А. В.

Пример сортировки прямым включением

А. В.
Сортировка прямым выбором (StraightSelection)
44
55
12
42
94
18
06
67
06
12
55
42
94
18
44
67
06
12
18
42
94
55
44
67
06
12
18
42
94
55
44
67
06
12
18
42
44
55
94
67
06
12
18
42
44
55
94
67
06
12
18
42
44
55
67
94
06
55
12
42
94
18
44
67
Шаг 1
Шаг 2
Шаг 3
Шаг 4
Шаг 5
Шаг

6

Шаг 7

Эффективность (n2-n)/2

А. В.
Пример сортировки прямым выбором
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;
}
}

А. В.
Сортировка прямым обменом (BubbleSort)
44
55
12
42
94
18
06
67
06
12
44
55
18
42
94
67
06
12
18
44
55
42
67
94
06
12
18
42
44
55
67
94
06
12
18
42
44
55
67
94
06
12
18
42
44
55
67
94
06
12
18
42
44
55
67
94
06
44
55
12
42
94
18
67
Шаг 1
Шаг 2
Шаг 3
Шаг 4
Шаг 5
Шаг

6

Шаг 7

Эффективность (n2-n)/2

А. В.
Пример сортировки прямым обменом
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;
}
}

А. В.
Шейкерная сортировка (ShakerSort)
44
55
12
42
94
18
06
67
06
44
12
42
55
18
67
94
06
12
44
18
42
55
67
94
06
12
18
42
44
55
67
94
06
44
55
12
42
94
18
67
Шаг 1
Шаг 2
Шаг 3
Шаг 4
Эффективность (n2-n(k+ln(n)))/2

А. В.
Шейкерная сортировка (ShakerSort)
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)
}

А. В.
Улучшенный метод сортировки Шелла (ShellSort)
44
55
12
42
94
18
06
67
06
18
12
42
44
55
94
67
06
12
18
42
44
55
67
94
44
18
06
42
94
55
12
67
Шаг 1
Шаг 2
Шаг 3
Эффективность n1.2
(сортировка

включением с уменьшающимися расстояниями)

h = 4

h = 2

h = 1

Последовательность расстояний 1, 3, 7, 15, 31... t = log2n-1, ht = 1, hk-1 = 2hk+1

А. В.
Метод быстрой сортировки Хоара (QuickSort)
44
55
12
42
94
18
06
67
06
12
18
42
44
55
94
67
06
12
18
42
44
55
67
94
06
18
12
42
94
55
44
67
Шаг 1
Шаг 2
Шаг 3
Эффективность n*log(n)
(сортировка

разделением)

А. В.
Пример быстрой сортировки
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);
if(L < j) sort(prod, L, j);
if(i < R) sort(prod, i, R);
}

void QuickSort(PROD* prod, int n)
{
sort(prod, 0, n);
}