02 Поиск и сортировка

1. Алгоритмы и структуры данных

Простые алгоритмы поиска и
сортировки
1

2. Задача и результаты поиска в массиве

Задача поиска:
Задан массив A из n элементов и некоторое значение p
(поисковое). Требуется найти такой номер i, что A[i]=p.
Возможные результаты поиска:
существует единственный элемент с номером i, для
которого A[i]=p
A[i]≠p при любых i=0,1,...,n-1 (безуспешный поиск)
существует несколько элементов с номерами i1,i2,...
таких, что A[i1]=p,A[i2]=p,...
2

3. Исчерпывающий поиск в массиве

На следующем слайде приводятся 2 функции, реализующие
исчерпывающий поиск в неупорядоченном массиве.
Функция find_int последовательно ищет в целочисленном
массиве A длины n первый элемент, совпадающий с
поисковым значением p. Если такой элемент найден, то
функция возвращает его индекс, в противном случае -1.
Функция find_double
проводит аналогичный поиск в
массиве элементов double. Параметр eps – это точность
задания значений элементов. Если элементы A или
поисковое значение p получены в результате вычислений, то
из-за округления значений проверка на точное равенство
может не сработать.
3

4. Исчерпывающий поиск

int find_int(int *A, int n, int p)
{
for (int i = 0; i < n; i++)
if (A[i] == p) return i;
return -1;
}
int find_double(double *A, int n, double p,
double eps)
{
for (int i = 0; i < n; i++)
if (abs(A[i]–p) < eps) return i;
return -1;
}
Минимальное число сравнений: 1
Максимальное число сравнений: n
4

5. Дихотомический (бинарный) поиск в упорядоченном массиве

На каждом шаге алгоритма выделяется область поиска:
A[b],A[b+1], ...,A[e]
(начальные границы области: b = 0, e = n-1).
Поисковое значение p сравнивается с элементом A[c],
где c = (b+e)/2. Возможны два исхода:
• A[c] < p, искомый элемент среди A[c+1],...,A[e],
новая нижняя граница области поиска b = c+1
• A[c] ≥ p, искомый элемент среди A[b],...,A[c] ,
новая верхняя граница области поиска e = c
Поиск продолжается, пока e > b.
5

6. 1-й алгоритм дихотомического поиска (поиск первого вхождения p)

int bin_search_first(int *A, int n, int p)
{
int b = 0, e = n-1, c;
while (b < e)
{
c = (b + e) / 2;
if (A[c] < p) b = c+1;
else e = c;
}
if (A[b] == p) return b; // элемент найден
return -1;
// безуспешный поиск
}
6

7. Варианты дихотомического поиска

Если упорядоченный массив содержит несколько
элементов,
равных
p,
то
они
располагаются
последовательно, а функция bin_search_first найдет
начальный элемент этой последовательности.
На
следующем
слайде
приводится
функция
bin_search_last, которая найдет конечный элемент в
последовательности элементов, равных p, или вернет -1.
В тексте функции выделены
bin_search_first.
отличия
от
функции
7

8. 2-й алгоритм дихотомического поиска (поиск последнего вхождения p)

int bin_search_last(int *A, int n, int p)
{
int b = 0, e = n-1, c;
while (b < e)
{
c = (b + e + 1) / 2;
if (A[c] <= p) b = c;
else e = c-1;
}
if (A[b] == p) return b;
return -1;
}
8

9. Рекурсивный алгоритм бинарного поиска

Бинарный поиск можно проводить рекурсивно. На
следующем слайде приводится соответствующая
рекурсивная функция bin_search_rec.
При каждом вызове этой функции необходимо
передавать в числе аргументов индексы начального и
конечного элемента текущей области поиска (при
первом вызове b = 0, e = n-1).
Длину массива при этом задавать не нужно.
9

10. Рекурсивный алгоритм бинарного поиска

int bin_search_rec(int *A, int p,int b, int e)
{ int c;
if (b == e)
// базисный вариант
if (A[b] == p) return b; else return -1;
else
{
c = (b + e) / 2;
if (A[c] < p)
return bin_search_rec(A,p,c+1,e);
else
return bin_search_rec(A,p,b,c);
}
}
Глубина рекурсии при
составляет log n.
поиске
в
массиве
длины
n
10

11. Варианты применения

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

12. Задача сортировки элементов массива

Задача
сортировки
возрастанию:
(упорядочения)
массива
по
Задан произвольный массив A из n элементов.
Требуется переставить его элементы таким образом,
чтобы условие A[i]<=A[i+1] выполнялось для всех
i=0,…,n-2.
При сортировке по убыванию меняется условие:
A[i]>=A[i+1] для всех i=0,…,n-2.
Очевидно, что набор значений в массиве A должен
оставаться неизменным.
12

13. Алгоритм обменной сортировки

Пусть начальные i элементов массива A[0]…A[i-1] уже
упорядочены.
Будем сравнивать A[i] и, если нужно, менять его местами
с A[i-1], A[i-2],…, пока он не займет свое место в
упорядоченной последовательности из i+1 элемента.
Повторив эти действия для всех i=1…n-1, получим
упорядоченный массив.
13

14. Алгоритм обменной сортировки

void exchange_sort(double *A, int n)
{
int i, j; double z;
for (i = 1; i < n; i++)
for (j=i-1; j>=0 && A[j]>A[j+1]; j--)
{
z=A[j]; A[j]=A[j+1]; A[j+1]=z;
// или swap(A[j], A[j+1]);
}
}
14

15. Пример для сортировки обменом

Массив A :
перед обработкой элемента 5:
1 3 4 8 11 12 5 2 7 7 3
после первого обмена 5 и 12:
1 3 4 8 11 5 12 2 7 7 3
после завершения обработки элемента 5:
1 3 4 5 8 11 12 2 7 7 3
15

16. Алгоритм сортировки вставками

Данный алгоритм очень похож на предыдущий. Разница
заключается в замене обмена элементов сдвигом:
• значение z=A[i] запоминается
• A[j]>z, j<i, сдвигаются на одну позицию вправо
• z ставится на свое место в последовательности
void insert_sort(double *A, int n)
{ int i, j; double z;
for (i = 1; i < n; i++)
{ z = A[i];
for (j=i-1; j>=0 && A[j]>z; j--)
A[j+1] = A[j];
A[j+1] = z;
}
}
16

17. Число сравнений элементов массива

В обеих сортировках общее количество сравнений и,
соответственно, выполнений внутреннего цикла в
наихудшем случае (исходный массив отсортирован по
убыванию):
1 + 2 + . . . + (n – 1) = n·(n – 1)/2
Если исходный массив уже упорядочен по возрастанию,
то внутренний цикл не будет исполняться ни разу, т.е.
общее число сравнений элементов составит n-1.
17

18. Алгоритм сортировки выбором

Среди m начальных элементов массива ищем
максимальный и меняем его местами с последним (m-1).
Выполняем эти действия для всех m=n…2.
При m=n после обмена максимального и последнего
элемента самый большой элемент встанет на свое
(последнее) место в упорядоченном массиве. Затем то
же самое повторится для n-1, n-2,…,2 начальных
элементов, и в результате массив будет отсортирован.
18

19. Алгоритм сортировки выбором

void select_sort(double *A, int n)
{
int i, m, imax; double z;
for (m = n; m > 1; m--)
{
for (imax = 0, i = 1; i < m; i++)
if (A[imax] < A[i]) imax = i;
z=A[imax]; A[imax]=A[m-1]; A[m-1]=z;
}
}
В переменной imax вычисляется индекс максимального
элемента.
19

20. Число сравнений элементов массива

Внутренний цикл в сортировке выбором всегда
выполняется m-1 раз, а m уменьшается во внешнем
цикле от n до 2.
Поэтому общее
составит
количество
сравнений
элементов
(n – 1)+(n – 2)+ . . . + 1 = n·(n – 1)/2 ≈ n2/2
для любого исходного массива длины n.
20

21. Простой алгоритм пузырьковой сортировки

Для m начальных элементов массива проводим сравнение
всех пар соседних элементов A[i] и A[i+1], i=0…m-2, и
меняем их местами, если A[i]>A[i+1]. В результате
максимальный элемент встает на последнее место (m-1).
Повторяем эти действия для всех m=n…2.
21

22. Простой алгоритм пузырьковой сортировки

void bubble_sort(double *A, int n)
{
int i, m;
for (m = n; m > 1; m--)
for (i = 0; i < m-1; i++)
if (A[i] > A[i+1])
swap(A[i], A[i+1]);
}
22

23. Простой алгоритм пузырьковой сортировки

Алгоритм сортировки пузырьком похож на алгоритм
сортировки выбором. Отличие заключается в том, что в
сортировке пузырьком максимальный элемент не ищется
отдельно,
а
выталкивается
в
конец
массива
последовательными обменами пар элементов.
Соответственно, число сравнений элементов в обоих
алгоритмах будет одинаковым (≈ n2/2 для любого массива
длины n).
23

24. Улучшенный алгоритм пузырька

Алгоритм сортировки пузырьком можно улучшить. Если во
внутреннем цикле не производится ни одного обмена, то
массив уже отсортирован. Для отметки этого используем
флаг – переменную sorted.
Сортировка продолжается, пока sorted=false. В начале
работы каждого внутреннего цикла предполагается, что
массив уже отсортирован, и устанавливается значение
sorted=true, но оно заменяется на false, если
произошел хотя бы один обмен элементов.
24

25. Улучшенный алгоритм пузырька

void bubble_sort_2(double *A, int n)
{
int i, m;
bool sorted = false;
for (m = n; m > 1 && !sorted; m--)
for (sorted=true, i = 0; i < m-1; i++)
if (A[i] > A[i+1])
{ swap(A[i], A[i+1]); sorted=false; }
}
25

26. Число сравнений элементов массива

Если исходный массив отсортирован по убыванию, то и в
улучшенном алгоритме пузырька общее количество
сравнений и, соответственно, выполнений внутреннего
цикла в наихудшем случае :
(n – 1) + (n - 2) + . . . + 2 + 1= n·(n – 1)/2
Если исходный массив уже упорядочен по возрастанию,
то внутренний цикл будет выполняться только один
раз, т.е. число сравнений элементов составит n - 1.
26

27. Косвенная сортировка

Сортировка бывает прямой и косвенной.
Прямую можно провести, если сортируемые объекты
объединены в массив (назовем его A). В процессе
прямой сортировки изменяется сам массив A.
При
косвенной
сортировке
формируется
дополнительный массив, который определяет выбор
элементов A в порядке возрастания. Массив A (если
он существует) не изменяется.
27

28. Косвенная сортировка элементов массива (вариант с массивом индексов)

Если сортируемые объекты объединены в массив A,то в
косвенной сортировке в качестве дополнительного
можно использовать массив Ind из n индексов
элементов A.
Начальные значения его элементов – это индексы
элементов A: Ind[i]=i, i=0…n-1. В результате
сортировки Ind перестраивается таким образом, что
выполняется:
A[Ind[i]] ≤ A[Ind[i+1]], i=0…n-2
т.е. Ind[i] хранит номер элемента, который
упорядоченном массиве A стоял бы на i-м месте.
в
28

29. Пример работы алгоритма косвенной сортировки с массивом индексов

Массив A (при сортировке не изменяется)
3 8 11 1 12 5 2 7 4 7 3
Массив Ind перед сортировкой
0 1
2
3
4
5 6 7 8 9 10
Массив Ind в результате сортировки
3 6
0 10 8
5 7 9 1
2
4
Цветами выделены минимальное и максимальное
значения, их индексы в A.
29

30. Косвенная упорядоченность массива

Алгоритм косвенной сортировки можно получить на
основе простой модификации алгоритма прямой
сортировки:
1) перед началом сортировки присвоить начальные
значения элементам Ind:
Ind[i]=i,
i=0…n-1
2) везде, где элемент массива A[i] используется в
операции сравнения, заменить A[i] на A[Ind[i]]
3) везде, где элемент массива A[i] используется в
присваивании, заменить A[i] на Ind[i]
30

31. Косвенная сортировка алгоритмом пузырька

Косвенно сортируем массив A (типа double). Динамический
индексный массив Ind создается и формируется в
функции, функция возвращает его адрес (указатель).
int* bubble_sort(double *A, int n)
{
int i, m, *Ind;
Ind = new int [n];
for (i = 0; i < n; i++) Ind[i] = i;
for (m = n; m > 1; m--)
for (i = 0; i < m-1; i++)
if (A[Ind[i]] > A[Ind[i+1]])
swap(Ind[i], Ind[i+1]);
return Ind;
}
31

32. Бинарный поиск в косвенно упорядоченном массиве

Функцию
bin_search_first
можно
легко
модифицировать для быстрого поиска в косвенно
упорядоченном массиве.
В качестве параметров необходимо передать не только
исходный массив A, его длину n и поисковое значение
p, но и сформированный в результате сортировки
индексный массив Ind.
При поиске значения элементов в массивах не
изменяются, производится только сравнение элементов
A с поисковым значением p. Элементы A выбираются
через индексный массив Ind.
32

33. Бинарный поиск в косвенно упорядоченном массиве

int bin_search_first(double *A, int *Ind,
int n, double p)
{
int b = 0, e = n-1, c;
while (b < e)
{
c = (b + e) / 2;
if (A[Ind[c]] < p) b = c+1;
else e = c;
}
if (A[Ind[b]] == p) return b;
return -1;
}
33

34. Косвенная сортировка с массивом указателей

В реальных задачах объекты для сортировки не
обязательно образуют массив - они могут
создаваться динамически и располагаться в разных
областях памяти. Очевидно, что ни прямая
сортировка, ни косвенная с массивом индексов в
таком случае не применимы.
Проблема решается путем использования массива
указателей на объекты вместо массива индексов.
34

35. Косвенная упорядоченность – общий случай

В общем случае не важно, образуют ли косвенно
сортируемые объекты один массив или нет. Необходим
только массив указателей Ptr, хранящих адреса этих
объектов. В результате сортировки массив указателей
изменится таким образом, что будет выполняться:
*Ptr[i] ≤ *Ptr[i+1], i=0…n-2
т.е. Ptr[i] будет хранить адрес объекта, который в
упорядоченной последовательности объектов стоял бы
на i-м месте.
В алгоритме косвенной сортировки должны выполняться
очевидные правила: сравниваются объекты, меняются
местами указатели.
35

36. Косвенная сортировка алгоритмом пузырька

Пусть надо упорядочить объекты некоторого типа TYPE.
Функция сортировки должна получать в качестве
параметра адрес массива указателей (т.е. двойной
указатель на TYPE).
void bubble_sort(TYPE **Ptr, int n)
{
int i, m;
for (m = n; m > 1; m--)
for (i = 0; i < m-1; i++)
if (*Ptr[i] > *Ptr[i+1])
swap(Ptr[i], Ptr[i+1]);
}
36

37. Дихотомический поиск в косвенно упорядоченном массиве

int bin_search_first(TYPE **Ptr, int n,
TYPE& p)
{
int b = 0, e = n-1, c;
while (b < e)
{
c = (b + e) / 2;
if (*Ptr[c] < p) b = c+1;
else e = c;
}
if (*Ptr[b] == p) return b;
return -1;
}
37

38. Преимущества косвенной сортировки

Цель любой сортировки – построение структуры данных,
которая обеспечит быстрый (бинарный) поиск нужных
объектов.
В реальных задачах объекты могут иметь достаточно
сложную структуру, а поиск нужно проводить по разным
атрибутам объектов.
Косвенная сортировка позволяет:
• не изменять и не перемещать объекты
• не зависеть от размещения объектов в памяти
• строить независимые структуры (массивы указателей
или индексов) для быстрого поиска по каждому
поисковому атрибуту
38