Алгоритмы упорядочения данных (сортировки)

1.

Алгоритмы упорядочения
данных (сортировки)

2.

ПрограСортировкой (упорядочиванием) называется процесс (операция)
перегруппировки объектов в некотором порядке. Сортировка облегчает
поиск, поэтому имеет важное значение в задачах обработки больших
объемов данныхммирование на языке C++
СОРТИРОВКА
Внутренняя сортировка –
упорядочение данных, хранимых в ОП
Внешняя сортировка – упорядочение
данных, хранимых во внешней
памяти
Рассматриваем алгоритмы
внутренней сортировки данных,
хранимых в статической таблице
2

3.

Сортировка таблиц
Если таблица представлена множеством элементов a1, a2, ... , an, тогда сортировка есть
перестановка элементов ak1, ak2, ... , akn, в которой над элементами установлено
отношение порядка:
f(ak1) ⩽ f(ak2) ⩽ ... ⩽ f(akn) или f(ak1) ⩾ f(ak2) ⩾ ... ⩾ f(akn)
( или какое-то другое отношение порядка, здесь f – упорядочивающая функция).
В простом случае f задается явно как компонент элемента таблицы, обычно этот
компонент – ключ элемента. В таком случае говорят об упорядочении по ключам.
Множество называется отсортированным, если оно не содержит ни одной инверсии.
Инверсия (при отношении порядка по возрастанию значений ключа) – это пара
индексов i и j такая, что i < j, а ключ (i-й элемент) > ключ (j-й элемент).

4.

Алгоритмизация и программирование, язык C++, 10 класс
4
Что такое сортировка?
Сортировка – это расстановка элементов массива в заданном
порядке.
…по возрастанию, убыванию, последней цифре, сумме
делителей, по алфавиту, …
Алгоритмы:
• простые и понятные, но неэффективные для больших
массивов
время
работы
▫ метод пузырька
▫ метод выбора
• сложные, но эффективные
▫ «быстрая сортировка» (QuickSort)
N
▫ сортировка слиянием (MergeSort)
▫ пирамидальная сортировка
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

5.

Алгоритмизация и программирование, язык C++, 10 класс
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

6.

Алгоритмизация и программирование, язык C++, 10 класс
6
Метод пузырька (сортировка обменами)
Идея: пузырек воздуха в стакане воды поднимается со
дна вверх.
Для массивов – самый маленький («легкий» элемент
перемещается вверх («всплывает»).
1-й проход:
4
4
4
4
1
5
5
5
1
4
2
2
1
5
5
1
1
2
2
2
3
3
3
3
3
К.Ю. Поляков, Е.А. Ерёмин, 2014
• сравниваем два соседних
элемента; если они стоят
«неправильно», меняем
их местами
• за 1 проход по массиву
один элемент (самый
маленький) становится на
свое место
http://kpolyakov.spb.ru

7.

Алгоритмизация и программирование, язык C++, 10 класс
7
Метод пузырька
2-й проход:
3-й проход:
4-й проход:
1
1
1
1
1
1
1
1
1
4
4
4
2
2
2
2
2
2
5
5
2
4
4
4
3
3
3
2
2
5
5
5
3
4
4
4
3
3
3
3
3
5
5
5
5
сортировки массива из N элементов нужен
! Для
N-1 проход (достаточно поставить на свои места N-1
элементов).
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

8.

Алгоритмизация и программирование, язык C++, 10 класс
8
Метод пузырька
1-й проход:
сделать для j от N-2 до 0 шаг -1
если A[j+1]< A[j] то
// поменять местами A[j] и A[j+1]
единственное
отличие!
2-й проход:
сделать для j от N-2 до 1 шаг -1
если A[j+1]< A[j] то
// поменять местами A[j] и A[j+1]
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

9.

Алгоритмизация и программирование, язык C++, 10 класс
9
Метод пузырька
for ( i = 0; i < N-1; i++ )
for ( j = N-2; j >= i ; j-- )
if ( A[j] > A[j+1] )
{
// поменять местами A[j] и A[j+1]
}
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

10.

Алгоритмизация и программирование, язык C++, 10 класс
Сортировка методом прямого обмена (методом пузырька)
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

11.

Алгоритмизация и программирование, язык C++, 10 класс
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

12.

Алгоритмизация и программирование, язык C++, 10 класс
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

13.

Алгоритмизация и программирование, язык C++, 10 класс
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

14.

Алгоритмизация и программирование, язык C++, 10 класс
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

15.

Алгоритмизация и программирование, язык C++, 10 класс
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

16.

Алгоритмизация и программирование, язык C++, 10 класс
Шейкерная сортировка
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

17.

Алгоритмизация и программирование, язык C++, 10 класс
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

18.

Алгоритмизация и программирование, язык C++, 10 класс
18
Метод выбора (минимального элемента)
Идея: найти минимальный элемент и поставить его на
первое место.
сделать для i от 0 до N-2
// найти номер nMin минимального
// элемента из A[i]..A[N]
если i != nMin то
// поменять местами A[i] и A[nMin]
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

19.

Алгоритмизация и программирование, язык C++, 10 класс
19
Метод выбора (минимального элемента)
for ( i = 0; i < N-1; i++ )
{
nMin = i;
for ( j = i+1; j < N; j++ )
if ( A[j] < A[nMin] )
nMin = j;
if ( i != nMin )
{
// поменять местами A[i] и A[nMin]
}
}
? Как поменять местами два значения?
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

20.

Алгоритмизация и программирование, язык C++, 10 класс
Сортировка методом прямого выбора
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

21.

Алгоритмизация и программирование, язык C++, 10 класс
Сортировка методом вставки
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

22.

Алгоритмизация и программирование, язык C++, 10 класс
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

23.

Алгоритмизация и программирование, язык C++, 10 класс
Сортировка методом прямого включения
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

24.

Алгоритмизация и программирование, язык C++, 10 класс
Сортировка слиянием
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

25.

Алгоритмизация и программирование, язык C++, 10 класс
Сортировка слиянием
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

26.

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

27.

Второй пример
сортировки слиянием
на конкретном
массиве.

28.

Алгоритмизация и программирование, язык C++, 10 класс
Алгоритмы быстрой сортировки
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

29.

Алгоритмизация и программирование, язык C++, 10 класс
Быстрые методы сортировки. Метод Шелла.
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

30.

Алгоритмизация и программирование, язык C++, 10 класс
Метод Шелла
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

31.

Алгоритмизация и программирование, язык C++, 10 класс
Сортировка с помощью дерева (пирамиды)
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

32.

Алгоритмизация и программирование, язык C++, 10 класс
Сортировка с помощью дерева (пирамиды)
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

33.

Алгоритмизация и программирование, язык C++, 10 класс
Сортировка с помощью дерева (пирамиды)
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

34.

Алгоритмизация и программирование, язык C++, 10 класс
Сортировка с помощью дерева
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

35.

Алгоритмизация и программирование, язык C++, 10 класс
Сортировка с помощью дерева
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

36.

Алгоритмизация и программирование, язык C++, 10 класс
36
Быстрая сортировка (QuickSort)
Идея: выгоднее переставлять элементы,
который находятся дальше друг от друга.
Ч.Э.Хоар
6
5
4
3
2
1
1
5
4
3
2
6
1
2
4
3
5
6
1
2
3
4
5
6
массива из N элементов нужно всего
! Для
N/2 обменов!
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

37.

Алгоритмизация и программирование, язык C++, 10 класс
37
Быстрая сортировка
Шаг 1: выбрать некоторый элемент массива X
Шаг 2: переставить элементы так:
A[i] <= X
A[i] >= X
при сортировке элементы не покидают « свою область»!
Шаг 3: так же отсортировать две получившиеся области
Разделяй и властвуй (англ. divide and conquer)
78
6
82
67
?
55
44
34
Как лучше выбрать X?
Медиана – такое значение X, что слева и справа от него в
отсортированном массиве стоит одинаковое число
элементов (для этого надо отсортировать массив…).
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

38.

Алгоритмизация и программирование, язык C++, 10 класс
38
Быстрая сортировка
Разделение:
1) выбрать средний элемент массива (X=67)
78
6
82
67
55
44
34
2) установить L = 1, R = N
3) увеличивая L, найти первый элемент A[L],
который >= X (должен стоять справа)
4) уменьшая R, найти первый элемент A[R],
который <= X (должен стоять слева)
5) если L<=R то поменять местами A[L] и A[R]
и перейти к п. 3
иначе стоп.
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

39.

Алгоритмизация и программирование, язык C++, 10 класс
39
Быстрая сортировка
78
L
6
82
67
55
44
34
R
34
6
82
L
67
55
44
R
78
34
6
44
67
L
55
R
82
78
34
6
44
55
R
67
L
82
78
! L > R : разделение закончено!
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

40.

Алгоритмизация и программирование, язык C++, 10 класс
40
Быстрая сортировка
Основная программа:
глобальные
const int N = 7;
данные
int A[N];
...
main()
{
// заполнить массив
qSort( 0, N-1 ); // сортировка
// вывести результат
}
процедура
сортировки
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

41.

Алгоритмизация и программирование, язык C++, 10 класс
41
Быстрая сортировка
void qSort( int nStart, int nEnd )
{
int L, R, c, X;
if ( nStart >= nEnd ) return; // готово
L = nStart; R = nEnd;
X = A[(L+R)/2]; // или X = A[irand(L,R)];
while ( L <= R ) {
// разделение
while ( A[L] < X ) L ++;
while ( A[R] > X ) R --;
if ( L <= R ) {
c = A[L]; A[L] = A[R]; A[R] = c;
L ++; R --;
Что плохо?
}
}
qSort ( nStart, R );
// рекурсивные вызовы
qSort ( L, nEnd );
}
?
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

42.

Алгоритмизация и программирование, язык C++, 10 класс
42
Быстрая сортировка
Передача массива через параметр:
void qSort( int A[], int nStart,
int nEnd )
{
...
qSort ( A, nStart, R );
qSort ( A, L, nEnd );
}
main()
{ // заполнить массив
qSort( A, 0, N-1 ); // сортировка
// вывести результат
}
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

43.

Алгоритмизация и программирование, язык C++, 10 класс
43
Быстрая сортировка
Сортировка массива случайных значений:
N
метод
пузырька
метод
выбора
быстрая
сортировка
1000
0,24 с
0,12 с
0,004 с
5000
5,3 с
2,9 с
0,024 с
15000
45 с
34 с
0,068 с
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru