Преподаватель: Доцент Кафедры ВС, к.т.н. Поляков Артем Юрьевич © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» ФГОБУ ВПО "СибГУТИ" Кафедра вычислительных систем Дисциплины "ЯЗЫКИ ПРОГРАММИРОВАНИЯ" "ПРОГРАММИРОВАНИЕ" Примеры алгоритмов обработки массивов

План лекции © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 2 1. Задача сортировки и алгоритмы ее решения 1.1. Мера упорядоченности последовательности 1.2. Задача сортировки 1.3. Алгоритм сортировки выбором 1.4. Алгоритм сортировки вставками 1.5. Алгоритм сортировки методом пузырька 2. Задача поиска простых чисел в заданном диапазоне 2.1. Линейный алгоритм 2.2. Алгоритм Эратосфена

Мера упорядоченности последовательности © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ»

Количественная мера упорядоченности © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 4 Инверсией элементов i и j последовательности a называется ситуация, когда a[i] > a[j] и i < j a[4] = 29, a[9] = 8: 4 8. Общее количество инверсией определяет степень упорядоченности последовательности. Для вычисления этого показателя элементы последовательности перебираются слева направо, для каждого элемента вычисляется количество его инверсий с элементами, расположенными правее.

Количественная мера упорядоченности (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» ) a[1] – a[3] : количество инверсий 0; 2) a[4] = 29: инверсии с элементами a[5] – a[9] = 5; 3) a[5] – a[8]: инверсия с элементом a[9], в сумме = 4; 4) a[9]: инверсий нет. 5) a[10]: инверсий нет. Итого: 9 инверсий.

Мера упорядоченности последовательности © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» абсолютное: 16 инверсий относит: 0,356 абсолютное: 0 инверсий относит: 0 абсолютное: 9 инверсий относит: 0,2 абсолютное: 24 инверсий относит: 0,533 абсолютное: 45 инверсий относит: 1

Задача сортировки (sorting problem) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 7 Дано: последовательность из n чисел a 1, a 2, a 3, …, a n Необходимо: переставить элементы последовательности так, чтобы для любых элементов новой последовательности a' 1, a' 2, a' 3, …, a' n выполнялось соотношение: a' 1 a' 2 a' 3 … a' n (сортировка по возрастанию) Алгоритм сортировки выбором

© Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Суть алгоритма заключается в последовательном формировании упорядоченной последовательности слева направо. На каждом шаге рассматривается фрагмент массива c i по n-й элементы. Среди них выбирается наименьший, который занимает первое место диапазона (на место i-го элемента). При этом i-й элемент перемещается на позицию, в которой найден минимум: После этого считается, что элементы массива с 1 по i отсортированы. Поэтому далее процедура повторяется для диапазона элементов с i+1 по n.

Алгоритм сортировки выбором (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» i = 1, min(a[k], k = i…n) = 2 inv = 22 i = 2, min(a[k], k = i…n) = 4 inv = i = 3, min(a[k], k = i…n) = 5 inv = i = 4, min(a[k], k = i…n) = 6 inv = i = 5, min(a[k], k = i…n) = 7 inv = i = 6, min(a[k], k = i…n) = 10 inv = 4

Алгоритм сортировки выбором (3) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» i = 7, min(a[k], k = i…n) = 15 inv = i = 8, min(a[k], k = i…n) = 17 inv = i = 9, min(a[k], k = i…n) = 19 inv = i = 6, min(a[k], k = i…n) = 10 inv = 4

Проход алгоритма сортировки выбором © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» i = 3, min(a[k], k = i…n) = 5 Основной подзадачей, возникающей в процессе сортировки, является поиск индекса минимального элемента в диапазоне с i по n (в примере на рис. диапазон – с 3 по 10). Для решения этой задачи можно воспользоваться уже известным алгоритмом поиска минимального элемента: m = i, k = i + 1 while k n do if a[k] < a[m] then m = k k = k + 1 t = a[i], a[i] = a[m], a[m] = t Приведенный фрагмент называется "проходом" данного алгоритма.

Алгоритм сортировки выбором (4) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 12 После каждого прохода алгоритма сортировки выбором размер отсортированной части увеличивается на 1 элемент: Поэтому, учитывая, что на последнем проходе рассматривается один элемент, количество проходов составляет n –

Алгоритм сортировки выбором (псевдокод) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 13 i = 1 while i < n do m = i, k = i + 1 while k < n do if a[k] a[m] then m = k k = k + 1 t = a[i], a[i] = a[m], a[m] = t Учитывая, что на последнем проходе рассматривается один элемент, количество проходов для получения полностью отсортированной последовательности составляет n – 1.

Алгоритм сортировки вставками © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 14 Суть данного алгоритма (аналогично предыдущему) заключается в последовательном формировании упорядоченной последовательности слева направо. Однако, в отличие от сортировки вставками, основная работа осуществляется в отсортированной части массива. На каждом шаге имеется отсортированная часть последовательности с 1 по (i – 1) и не отсортированная – с i по n элементы. Для первого не отсортированного элемента с номером i в отсортированной части ищется подходящая позиция, как показано на рисунке:

Алгоритм сортировки вставками (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» inv = 22 inv = 20 inv = 18 inv = 14 inv = 8 inv = 7 inv = 0 inv = 7

Проход алгоритма сортировки вставками © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» t 6 Основной подзадачей, возникающей в процессе сортировки, является поиск для очередного элемента правильного места в уже отсортированной части массива и вставка его на эту позицию. Решение этой задачи можно разбить на следующие шаги: 1. Поиск индекса подходящей позиции k для элемента a[i]. 2. Запоминание элемента a[i] во временной ячейке t: t = a[i]. 3. Сдвиг элементов a[k], a[k+1], …, a[i–1] на один элемент вправо, т.е. в ячейки a[k+1], a[k+2], …, a[i] соответственно. 4. Поместить значение из ячейки t в a[k]: a[k] = t

Проход алгоритма сортировки вставками (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Поиск индекса подходящей позиции k для элемента a[i]. 2. Запоминание элемента a[i] во временной ячейке t: t = a[i]. 3. Сдвиг элементов a[k], a[k+1], …, a[i–1] на один элемент вправо, т.е. в ячейки a[k+1], a[k+2], …, a[i] соответственно. 4. Поместить значение из ячейки t в a[k]: a[k] = t. На практике поиск элемента часто объединяют со сдвигом элементов: a[5] > a[4] => сдвиг не нужен t = a[5] 1) t < a[4], сдвиг: a[5] = a[4]; 2) t < a[3], сдвиг: a[3] = a[4]; 3) t > a[2], стоп: a[3] = t; t 9

Проход алгоритма сортировки вставками (3) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 18 Псевдокод одного прохода алгоритма сортировки вставками выглядит следующим образом: t = a[i], k = i – 1 while k 1 и a[k] > t do a[k+1] = a[k] k = k – 1 a[k+1] = t Приведенный фрагмент называется "проходом" данного алгоритма k = 5 a[6] = a[5] k = 4 a[5] = a[4] k = 3 a[4] = a[3] k = 2 a[3] = t

Алгоритм сортировки вставками (3) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 19 Таким образом для сортировки всей последовательности требуется n – 1 проход. После каждого прохода алгоритма сортировки выбором размер отсортированной части увеличивается на 1 элемент:

Алгоритм сортировки вставками (псевдокод) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 20 i = 2 while i < n do t = a[i], k = i – 1 while k 1 и a[k] > t do a[k+1] = a[k] k = k – 1 a[k+1] = t Таким образом для сортировки всей последовательности требуется n – 1 проход. t = a[i], k = i – 1 while k 1 и a[k] > t do a[k+1] = a[k] k = k – 1 a[k+1] = t

Алгоритм сортировки методом пузырька © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 21 Суть данного заключается в том, что на каждом проходе определяется наибольший элемент, который выводится на последнее место рассматриваемой подпоследовательности и исключается из дальнейшего рассмотрения. Важным отличием данного алгоритма от ранее рассмотренных является то, что в процессе выведения наибольшего элемента участвуют все элементы и количество инверсий сокращается более, чем на вклад наибольшего элемента. Проход алгоритма заключается в попарном сравнении соседних элементов и устранении "локальных" инверсий. В результате такого прохода наибольший элемент (пузырек наибольшего размера) выдвигается в крайнюю правую позицию

Проход алгоритма сортировки методом пузырька © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» inv = 22 inv = 17

Алгоритм сортировки методом пузырька (3) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» inv = 22 inv = 17 inv = inv = inv = inv = inv = 1

Алгоритм сортировки методом пузырька (4) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» inv = inv = inv = inv = 0 Особенностью алгоритма сортировки методом пузырька является то, что существует возможность досрочного прекращения сортировки при условии, что на очередном проходе не было выполнено ни одного обмена.

Проход алгоритма сортировки методом пузырька (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 25 j 1 while j (n – i) do if a[k+1] < a[k] then t a[k+1] a[k+1] a[k] a[k] t j = j

Алгоритм сортировки методом пузырька (5) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 26 Таким образом для сортировки всей последовательности требуется n – 1 проход. После каждого прохода алгоритма сортировки методом пузырька наибольший размер отсортированной правой части увеличивается на 1 элемент: inv = 22 inv = inv = 0

Алгоритм сортировки методом пузырька (псевдокод) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 27 i = 1 while i < n – 1 do j 1 while j (n – i) do if a[k+1] < a[k] then t a[k+1] a[k+1] a[k] a[k] t j = j + 1 Таким образом для сортировки всей последовательности требуется n – 1 проход. j 1 while j (n – i) do if a[k+1] < a[k] then t a[k+1] a[k+1] a[k] a[k] t j = j + 1

Алгоритм сортировки методом пузырька c досрочным выходом (псевдокод) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 28 i = 1, f 1 while i 0 do j 1, f 0 while j (n – i) do if a[k+1] < a[k] then t a[k+1] a[k+1] a[k] a[k] t f 1 j = j + 1 Таким образом для сортировки всей последовательности требуется n – 1 проход.