Структуры и алгоритмы компьютерной обработки данных

Федеральное государственное автономное образовательное учреждение высшего образования «САНКТ-ПЕТЕРБУРГСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ПЕТРА ВЕЛИКОГО» Институт компьютерных наук и технологий Высшая школа интеллектуальных систем и суперкомпьютерных технологий В.Г. Пак Структуры и алгоритмы компьютерной обработки данных Слайды видеолекций для студентов заочного бакалавриата направления подготовки высшего образования «Прикладная информатика» Санкт-Петербургский политехнический университет Петра Великого 2020 Санкт-Петербургский политехнический университет Петра Великого, 2020 © Федеральное государственное автономное образовательное учреждение высшего образования «САНКТ-ПЕТЕРБУРГСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ПЕТРА ВЕЛИКОГО» Институт компьютерных наук и технологий Высшая школа интеллектуальных систем и суперкомпьютерных технологий ЛЕКЦИЯ №4 Алгоритмы сортировки Санкт-Петербургский политехнический университет Петра Великого 2020 Санкт-Петербургский политехнический университет Петра Великого, 2020 © Содержание IV. Алгоритмы сортировки §1. Задача сортировки §2. Алгоритмы внутренней сортировки 2.1. Модель внутренней сортировки 2.2. Простая сортировка 2.2.1. Простые алгоритмы сортировки 2.2.2. Вычислительная сложность простых алгоритмов сортировки 2.3. Быстрая сортировка Хоара 2.3.1. Алгоритм сортировки Хоара 2.3.2. Вычислительная сложность сортировки Хоара 2.3.2.1. Худший случай 2.2.2.2. Сложность в среднем Структуры и алгоритмы компьютерной обработки данных Лекция 4. Алгоритмы сортировки 3 Содержание 2.4. Пирамидальная сортировка на сбалансированных деревьях 2.4.1. Основные операторы АТД множеств 2.4.2. Реализация АТД множеств с помощью сбалансированных деревьев 2.4.3. Операторы АТД множеств на сбалансированных деревьях 2.4.4. Алгоритм пирамидальной сортировки на сбалансированных деревьях Структуры и алгоритмы компьютерной обработки данных Лекция 4. Алгоритмы сортировки 4 Содержание (окончание) 2.5. Пирамидальная сортировка на частично упорядоченных деревьях 2.5.1. Реализация АТД очередей с приоритетами с помощью частично упорядоченных деревьев 2.5.2. Алгоритм пирамидальной сортировки на частично упорядоченных деревьях Структуры и алгоритмы компьютерной обработки данных Лекция 4. Алгоритмы сортировки 5 Содержание §3. Алгоритмы внешней сортировки 3.1. Модель внешней обработки данных 3.2. Внешняя сортировка слиянием 3.3. Многоканальное слияние 3.4. Многофазная сортировка Структуры и алгоритмы компьютерной обработки данных Лекция 4. Алгоритмы сортировки 6 §1. Задача сортировки IV. Алгоритмы сортировки §1. Задача сортировки Сортировка (упорядочение кортежа или множества объектов) – расположение этих объектов по возрастанию или убыванию согласно определѐнному на них линейному порядку ≤. Сортировка Внутренняя: все сортируемые объекты помещаются в ОП. Используется модель памяти с произвольным доступом. Внешняя: объѐм данных очень велик для помещения в ОП, поэтому организуется обмен данными между ОП и внешней памятью. Структуры и алгоритмы компьютерной обработки данных Лекция 4. Алгоритмы сортировки 7 2.1. Модель внутренней сортировки §2. Алгоритмы внутренней сортировки 2.1. Модель внутренней сортировки Модель (структура) данных. Сортируемые объекты – записи, одно из полей которых содержит ключ, имеющий тип данных, на котором определено отношение линейного порядка ≤. Если записи 𝑟1 , … , 𝑟𝑛 имеют ключевые поля 𝑘1 , … , 𝑘𝑛 , то упорядочение состоит в нахождении такого их расположения 𝑟𝑖1 , … , 𝑟𝑖𝑛 , что 𝑘𝑖1 ≤ 𝑘𝑖2 ≤ ⋯ ≤ ≤ 𝑘𝑖 𝑛 . Критерии оценки алгоритмов: 1) время упорядочения 𝑛 записей; 2) количество сравнений значений ключей при упорядочении 𝑛 записей (значимый критерий, т.к. сравнение – наиболее трудоѐмкий процесс); Структуры и алгоритмы компьютерной обработки данных Лекция 4. Алгоритмы сортировки 8 2.1. Модель внутренней сортировки 3) время перемещения записей (может быть критичным при большой длине записи). Далее будем говорить об упорядочении ключей 𝑘1 , … , 𝑘𝑛 . Устойчивая (стабильная) сортировка — сортировка, которая не меняет относительный порядок сортируемых элементов, имеющих одинаковые ключи. Структуры и алгоритмы компьютерной обработки данных Лекция 4. Алгоритмы сортировки 9 2.2.1. Простые алгоритмы сортировки 2.2. Простая сортировка 2.2.1. Простые алгоритмы сортировки a) Сортировка «пузырьком». Словесное описание алгоритма. На i-м проходе вектора 1-й элемент сравнивается со 2м, если он больше, то они меняются местами; далее 2-й сравнивается с 3-м, опять меняются местами, если 2-й больше 3-го и т.д. до (n-i)-го и (n-i+1)-го. Таким образом, наибольший из 1-го, 2-го, … , (n-i)-го элементов оказывается на (n-i+1)-м месте. Проходы вектора повторяются при i=1, … , n-1. Структуры и алгоритмы компьютерной обработки данных Лекция 4. Алгоритмы сортировки 10 2.2.1. Простые алгоритмы сортировки Псевдокод: For i:=1 to n-1 for j:=1 to n-I if A[j]>A[j+1] then A[j]↔A[j+1] End b) Сортировка вставками. Рассмотрен в примере (лекция 1, слайд 19). c) Сортировка бинарными вставками. Модификация сортировки вставками, заключающаяся в том, что определение места вставки элемента производится методом бинарного поиска. Структуры и алгоритмы компьютерной обработки данных Лекция 4. Алгоритмы сортировки 11 2.2.1. Простые алгоритмы сортировки Псевдокод: For i:=2 to n if A[i-1]>A[i] then begin x:=A[i] left:=1 right:=i-1 repeat mid:=(left+right) div 2 if A[mid]right for j:=i-1 downto left A[j+1]:=A[j] A[left]:=x End Структуры и алгоритмы компьютерной обработки данных Лекция 4. Алгоритмы сортировки 12 2.2.1. Простые алгоритмы сортировки d) Сортировка выбором минимального элемента. Словесное описание алгоритма. На i-м проходе вектора считается, что подвектор от 1-го до (i-1)-го элемента отсортирован, хвост (от i-го до n-го) не отсортирован. Находим индекс минимального элемента в неотсортированной части, меняем местами этот элемент с первым в неотсортированной части (обмен не нужен, если минимальный элемент уже находится на данной позиции). Отсортированная часть увеличивается на один элемент. Проходы вектора повторяются при i=1, … , n-1. Структуры и алгоритмы компьютерной обработки данных Лекция 4. Алгоритмы сортировки 13 2.2.2. Вычислительная сложность простых алгоритмов сортировки 2.2.2. Вычислительная сложность простых алгоритмов сортировки Сортировка «пузырьком»: 1 For i:=1 to n-1 2 for j:=1 to n-I 3 if A[j]>A[j+1] then 4 A[j]↔A[j+1] End Алгоритм имеет порядок роста Ο 𝑛2 в худшем случае и в среднем и Ω 𝑛2 в лучшем случае. Алгоритм имеет высокую вычислительную сложность, но является устойчивым и использует мало памяти. Сортировки вставками, бинарными вставками и выбором имеют такую же вычислительную сложность. Структуры и алгоритмы компьютерной обработки данных Лекция 4. Алгоритмы сортировки 14 2.2.2. Вычислительная сложность простых алгоритмов сортировки Из-за высокой вычислительной сложности простые алгоритмы проигрывают при больших n быстрым алгоритмам с Ο 𝑛 log 𝑛 . Значение n, при котором быстрая сортировка лучше, определяется размером записей, качеством кода и т.д. Практический опыт показывает, что при 𝑛 ≤ 100 на время работы влияют многие не поддающиеся анализу факторы, а при 𝑛 > 100 действует решающий фактор – качество алгоритма. Вывод. При небольших n лучше применять сравнительно простые алгоритмы 3 2 (компромисс – алгоритм Шелла с Ο 𝑛 ), при больших – быстрые. Структуры и алгоритмы компьютерной обработки данных Лекция 4. Алгоритмы сортировки 15 2.3.1. Алгоритм сортировки Хоара 2.3. Быстрая сортировка Хоара 2.3.1. Алгоритм сортировки Хоара Словесное описание алгоритма. Из элементов вектора выбирается значение 𝑣 – опорный элемент, относительно которого упорядочиваются элементы 𝑣. Обычно в качестве 𝑣 выбирается медиана вектора. Затем элементы переставляются так, чтобы для некоторого 𝑗 все 𝑘𝑖1 , … , 𝑘𝑖𝑗 были меньше 𝑣, все 𝑘𝑖𝑗+1 , … , 𝑘𝑖𝑛 были не меньше 𝑣. Процедура рекурсивно применяется к подвекторам 𝑘𝑖1 , … , 𝑘𝑖𝑗 и 𝑘𝑖𝑗+1 , … , 𝑘𝑖𝑛 и т.д. Структуры и алгоритмы компьютерной обработки данных Лекция 4. Алгоритмы сортировки 16 2.3.1. Алгоритм сортировки Хоара Псевдокод процедуры сортировки подмассива A[i..j]: Procedure QuickSort (A[i..j]) If A[i..j] имеет не менее 2 различных элементов then begin v:=наибольший из двух первых (слева) различных элементов перестановка A[i..j]: при некотором k (i+1≤k≤j) все элементы A[i..k-1] меньше v, все элементы A[k..j] больше или равны v, QuickSort (A[i..k-1]) QuickSort (A[k..j]) End Структуры и алгоритмы компьютерной обработки данных Лекция 4. Алгоритмы сортировки 17 2.3.1. Алгоритм сортировки Хоара Процедура Findv(A[i..j]) проверяет, все ли элементы A[i..j] одинаковы; если да, то возвращает 0, если нет – индекс наибольшего из первых двух найденных неравных элементов. Псевдокод: Function Findv(A[i..j]) k:=A[i] For s:=i+1 to j do if A[s]>k then begin Findv:=s exit end elseif A[s]r (на самом деле возможно только l=r+1), если выполнено, то перемещение заканчивается. 3. Если lr Sort:=l точка разделения массива на левую и правую части End Структуры и алгоритмы компьютерной обработки данных Лекция 4. Алгоритмы сортировки 20 2.3.1. Алгоритм сортировки Хоара Теперь собираем фрагменты в общий алгоритм: Procedure QuickSort (A[i..j]) Indexv:=Findv(A[i..j]) If Indexv<>0 then do v:=A[indexv] k:=Sort(A[i..j], v) QuickSort (A[i..k-1]) QuickSort (A[k..j]) End End QuickSort Вызов: QuickSort (A[1..n]). Структуры и алгоритмы компьютерной обработки данных Лекция 4. Алгоритмы сортировки 21 2.3.2.1. Вычислительная сложность в худшем 2.3.2. Вычислительная сложность сортировки Хоара 2.3.2.1. Худший случай Покажем, что время выполнения процедуры Sort(A[i..j], v) имеет порядок роста Ο 𝑗 − 𝑖 + 1 . Найдѐм время обработки элементов A[i], … , A[j]. Оно равно времени, необходимому для достижения в процедуре Sort курсорами l и r элемента A[k] (𝑖 ≤ 𝑘 ≤ 𝑗), начиная от исходного положения курсоров. Процедура возвращает значение курсора l, разбивающего массив A[i..j] на два подмассива, содержащих по крайней мере по одному элементу. Следовательно, каждый элемент массива A[i..j] просматривается хотя бы один раз. Поэтому время обработки каждого из элементов A[i], … , A[j], а значит, и общее время работы процедуры Sort пропорционально длине массива, т.е. j-i+1. Найдѐм характер этой пропорциональности. Для этого проанализируем псевдокод. Структуры и алгоритмы компьютерной обработки данных Лекция 4. Алгоритмы сортировки 22 2.3.2.1. Вычислительная сложность в худшем Function Sort(A[i..j], v) 1 l:=i 2 r:=j Repeat 3 перестановка A[l], A[r] 4 while A[l]r 9 Sort:=l End Подсчитаем количество шагов алгоритма между двумя выполнениями оператора l:=l+1 или r:=r-1 в худшем случае. Сначала происходит инициализация курсоров (строки 1, 2), затем перестановка элементов (строка 3) (выполняется всегда – цикл repeat!), Структуры и алгоритмы компьютерной обработки данных Лекция 4. Алгоритмы сортировки 23 2.3.2.1. Вычислительная сложность в худшем затем выполняются строки 4, 6 без изменения значений l и r (худший случай!). На втором и последующих проходах цикла repeat перестановка в строке 3 гарантирует, что хотя бы один из циклов 4 или 6 будет выполнен не менее одного раза. Следовательно, между операторами l:=l+1 или r:=r-1 в худшем случае выполняются строки 1, 2, 3 дважды, проверки условий 4, 6, 8 и снова 4. Эти операции требуют фиксированного времени, не зависящего ни от i, ни от j. В конце процедуры выполняются проверки 4, 6, 8, не связанные ни с какими элементами и занимающие фиксированное время. Следовательно, время обработки любого элемента не превышает некоторой константы, а это значит (см. слайд 124), что время работы процедуры Sort имеет порядок роста Ο 𝑗 − 𝑖 + 1 . Теперь проанализируем псевдокод процедуры QuickSort (A[i..j]). Структуры и алгоритмы компьютерной обработки данных Лекция 4. Алгоритмы сортировки 24 2.3.2.1. Вычислительная сложность в худшем Procedure QuickSort (A[i..j]) 1 Indexv:=Findv(A[i..j]) 2 If Indexv<>0 then do 3 v:=A[indexv] 4 k:=Sort(A[i..j], v) 5 QuickSort (A[i..k-1]) 6 QuickSort (A[k..j]) End End QuickSort Время работы Findv(A[i..j]) в строке 1 имеет порядок Ο 𝑗 − 𝑖 + 1 (легко доказывается рассмотрением псевдокода). Строки 2, 3 выполняются за фиксированное время. Вызов Sort(A[i..j], v) в 4, как было доказано, требует время порядка Ο 𝑗 − 𝑖 + 1 . Следовательно, каждый отдельный вызов QuickSort (A[i..j]) без учѐта рекурсии требует времени, пропорционального количеству упорядочиваемых им элементов. Структуры и алгоритмы компьютерной обработки данных Лекция 4. Алгоритмы сортировки 25 2.3.2.1. Вычислительная сложность в худшем С другой стороны, общее время выполнения QuickSort (A[i..j]) равно сумме по всем элементам времѐн нахождения данного элемента в части массива A[i..j], обрабатываемом этим вызовом процедуры. Это время для каждого элемента можно выразить как максимальную глубину рекурсии, на котором заканчивается обработка этого элемента. В самом худшем случае опорный элемент на каждом шаге равен максимальному из сортируемых. Тогда массив разбивается на подмассивы, один из которых («правый») состоит из одного опорного элемента. Такая последовательность разбиений (рекурсий) изображается структурой дерева (см. рис.). Элемент 𝑟𝑖 имеет глубину 𝑛 − 𝑖 + 1 (2 ≤ 𝑖 ≤ 𝑛), 𝑟1 (𝑛 − 1). 𝑟𝑛 𝑟𝑛−1 𝑣 𝑟1 Структуры и алгоритмы компьютерной обработки данных Лекция 4. Алгоритмы сортировки 𝑟2 26 2.3.2.1. Вычислительная сложность в худшем Суммарная глубина всех элементов равна 𝑛 𝑛2 + 𝑛 − 2 𝑛−1+ 𝑛−𝑖+1 = . 2 𝑖=2 Отсюда следует, что процедура QuickSort (A[1..n]) имеет вычислительную сложность Ο 𝑛2 в худшем случае. Структуры и алгоритмы компьютерной обработки данных Лекция 4. Алгоритмы сортировки 27 2.3.2.2. Вычислительная сложность в среднем 2.3.2.2. Вычислительная сложность в среднем Алгоритм имеет вычислительную сложность Ο 𝑛 log 𝑛 в среднем. Структуры и алгоритмы компьютерной обработки данных Лекция 4. Алгоритмы сортировки 28 2.4.1. Основные операторы АТД множеств Следующий быстрый алгоритм, который будет изучен, - пирамидальная сортировка. Он имеет вычислительную сложность Ο 𝑛 log 𝑛 и худшем, и в среднем. Его можно записать в абстрактной форме, используя операторы АТД множеств. 2.4. Пирамидальная сортировка на сбалансированных деревьях 2.4.1. Основные операторы АТД множеств Здесь будут рассмотрены используемые в алгоритме операторы АТД множеств и некоторые реализации множеств. 1. Процедура INSERT(x, A), где элемент 𝑥 имеет тот же тип данных, что и элементы 𝐴. Процедура делает 𝑥 элементом 𝐴, т.е. INSERT(x, A)=𝐴 ∪ 𝑥 . Структуры и алгоритмы компьютерной обработки данных Лекция 4. Алгоритмы сортировки 29 2.4.1. Основные операторы АТД множеств 2. Процедура DELETE(x, A), где элемент 𝑥 имеет тот же тип данных, что и элементы 𝐴. Процедура удаляет 𝑥 из 𝐴, т.е. DELETE(x, A)=𝐴\ 𝑥 . 3. Функция MIN(A) возвращает минимальный элемент 𝐴. Для применения необходимо, чтобы на элементах 𝐴 был определѐн линейный порядок. 4. Функция MAX(A) возвращает максимальный элемент 𝐴. 5. Функция EMPTY(A) возвращает true, если 𝐴 = ∅, false в противном случае. 6. Процедура DELETEMIN(A) находит минимальный элемент 𝐴 и удаляет его из 𝐴, т.е. DELETEMIN(A)=𝐴\ min 𝐴 . 7. Процедура DELETEMAX(A) находит максимальный элемент 𝐴 и удаляет его из 𝐴, т.е. DELETEMAX(A)=𝐴\ max 𝐴 . Структуры и алгоритмы компьютерной обработки данных Лекция 4. Алгоритмы сортировки 30 2.4.2. Реализация АТД множеств с помощью сбалансированных деревьев 2.4.2. Реализация АТД множеств с помощью сбалансированных деревьев Пример реализации АТД структурой данных, позволяющей выполнять операторы за время порядка Ο log 𝑛 . Сбалансированное дерево – дерево, в котором высота поддеревьев любого узла различается не более чем на заданную величину k. Виды сбалансированных деревьев: • АВЛ-деревья (Адельсон-Вельский, Ландис); • красно-чѐрные деревья; • B-деревья; • … АВЛ-дерево – сбалансированное двоичное дерево, в котором у любого внутреннего узла высота левого и правого поддеревьев отличаются не более чем на единицу. Известно, что алгоритмы поиска, вставки и удаления на АВЛ-деревьях имеют вычислительную сложность Ο log 𝑛 в среднем и в худшем. Структуры и алгоритмы компьютерной обработки данных Лекция 4. Алгоритмы сортировки 31 2.4.2. Реализация АТД множеств с помощью сбалансированных деревьев Построим реализацию АТД множеств, в которой операторы имеют время выполнения в худшем случае Ο log 𝑛 . Сбалансированное дерево является 2-3-деревом, если в нѐм: 1. Каждый внутренний узел имеет либо 2, либо 3 сыновей. 2. Все пути от корня до любого листа имеют одинаковую длину. Пустое дерево Λ и дерево из одного корня также являются 2-3деревьями. Реализуем множества, упорядоченные отношением линейного порядка < (не ≤, т.к. нет одинаковых элементов), 2-3-деревьями следующим образом. Элементы множества располагаются в листах дерева, причѐм, если 𝑎 < 𝑏, то 𝑎 находится левее 𝑏 и наоборот. Внутренний узел Наименьший элемент, являющийся потомком второго сына 𝑦 𝑧 Наименьший элемент, являющийся потомком третьего сына Структуры и алгоритмы компьютерной обработки данных Лекция 4. Алгоритмы сортировки 32 2.4.2. Реализация АТД множеств с помощью сбалансированных деревьев Любое 2-3-дерево с 𝑘 уровнями имеет от 2𝑘−1 до 3𝑘−1 листьев, значит, дерево, реализующее (𝑛)-множество, будет иметь от 1 + log 2 𝑛 до 1 + log 3 𝑛 уровней. Следовательно, длины всех путей имеют порядок Ο log 𝑛 . Элемент 𝑥 находится в представляющем множество 𝐴 2-3дереве за время порядка Ο log 𝑛 следующим перемещением по дереву: 1. Во внутреннем узле 𝑥 сравнивается с 𝑦. Структуры и алгоритмы компьютерной обработки данных Лекция 4. Алгоритмы сортировки 33 2.4.2. Реализация АТД множеств с помощью сбалансированных деревьев Внутренний узел Да 𝑥<𝑦 перемещаемся к 1-му сыну узла Да Да перемещаемся ко 2-му сыну узла Нет узел имеет 3 сыновей Нет перемещаемся ко 2-му сыну узла 𝑥 𝑝. Структуры и алгоритмы компьютерной обработки данных Лекция 4. Алгоритмы сортировки 61 3.4. Многофазная сортировка • Поскольку число записей в исходном файле может не обеспечить такого распределения, применяется метод добавления пустых записей (серий), которые в дальнейшем как можно более равномерно распределяются между промежуточными файлами. Понятно, что чем меньше таких пустых серий, т.е. чем ближе число сортируемых записей к суммам чисел Фибоначчи, тем более эффективно работает алгоритм. Структуры и алгоритмы компьютерной обработки данных Лекция 4. Алгоритмы сортировки 62