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

Сортировка данных © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 2 Сортировка – процесс перестановки элементов некоторого множества в определенном порядке. Цель сортировки – упрощение поиска данных в этом множестве. Задача сортировки данных часто возникает при разработке программного обеспечения. Алгоритмы сортировки можно разделить на: алгоритмы внутренней сортировки; алгоритмы внешней сортировки убываниевозрастание

3 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Размер последовательности: n элементов Оперативная память способна хранить k элементов Применение внутренней сортировки позволит сформировать серии размером не менее k элементов. Количество серий после внутренней сортировки: n/k Количество проходов: log 2 (n/k) Число проходов сокращается в log 2 n/log 2 (n/k)=log (n/k) n раз. Недостатки алгоритма естественной сортировки слиянием (2)

Файл подкачки 4 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Своппинг (swapping, paging, swap) – один из механизмов виртуальной памяти, при котором отдельные фрагменты памяти (обычно неактивные) перемещаются из ОП на жёсткий диск, освобождая ОП для загрузки других фрагментов памяти. Область в ОП Выгруженная область Данный механизм позволяет создать видимость того, что размер памяти (виртуальной) программы больше, чем объем доступной физической памяти

Внутренняя сортировка начальных серий 5 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Данная стратегия основана на использовании очереди с приоритетами для начального распределения серий: Буфер Quick Sort

Сравнение Quick Sort и Natural Merge + Quick sort (k элементов) 6 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» k = = 1,310 6 Quick Sort (swap) Quick Sort + Natural Merge

7 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» k = = 1,310 6 Quick Sort + Natural Merge Quick Sort (swap) Сравнение Quick Sort и Natural Merge + Quick sort (k элементов)

Выбор с замещением (replacement selection) 8 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Данная стратегия основана на использовании очереди с приоритетами для начального распределения серий: Буфер Н0Н0 Н0Н0 Н1Н1 Н1Н1 Н2Н2 Н2Н2 Н3Н3 Н3Н3 Н4Н4 Н4Н4 Н5Н5 Н5Н5 Н6Н6 Н6Н6... Heap Sort

Пирамида 9 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Пирамида – массив элементов, для каждого из которых выполняется следующее соотношение: i = 0, 1,..., n – 1i = 1, 2,..., n a i a 2i+1 a i a 2i+2 a i a 2i a i a 2i+1 ДЛЯ обеспечения соотношения (*) при формировании пирамиды, поддержания соотношения (*) при вставке/удалении элементов используется процедура просеивания. (*)(*)

Пример пирамиды 10 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» a i a 2i a i a 2i+1

Являются ли следующие массивы пирамидами? 11 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» a i a 2i a i a 2i+1 1) ) ) ) )

Являются ли следующие массивы пирамидами? 12 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 1) ) ) ) )

Процедура просеивания (sift) 13 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» sift(i, k): До тех пор, пока i > (k / 2), элемент в позиции i сравнивается с потомками 2i и (2i+1). Если a i > a 2i и a 2i < a 2i+1, то элементы i и 2i меняются местами, после чего просеивание продолжается для элемента 2i: sift(2i, k). Если a i > a 2i+1 и и a 2i+1 < a 2i, то элементы i и (2i+1) меняются местами, после чего просеивание продолжается для (2i+1): sift(2i+1, k).

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

Алгоритм процедуры просеивания 15 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» H – массив, содержащий пирамиду i – номер просеиваемого элемента (нумерация с 1) n – количество элементов в пирамиде SIFT(H, i, n) j 2i x H[i] if (j H[j+1] then j j + 1 while (j n) И x > H[ j] do H[i] H[ j] i j j 2i if (j H[j+1] then j j + 1 H[i] x

Алгоритм процедуры просеивания 16 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» SIFT(H, i, n) j 2i x H[i] if (j H[j+1] then j j + 1 while (j n) И x > H[ j] do H[i] H[ j] i j j 2i if (j H[j+1] then j j + 1 H[i] x

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

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

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

Построение пирамиды (I) 20 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» k = 6 (количество доступных ячеек ОП) X X X X k/2 Правило пирамиды: i = 1, 2,..., n a i a 2i a i a 2i+1 Правило пирамиды: i = 1, 2,..., n a i a 2i a i a 2i+1 Правило пирамиды: i = 0, 1,..., n – 1 a i a 2i+1 a i a 2i+2 Правило пирамиды: i = 0, 1,..., n – 1 a i a 2i+1 a i a 2i

Построение пирамиды (II) 21 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» k = 6 (количество доступных ячеек ОП) X X k/ X X

Построение пирамиды (III) 22 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» k = 6 (количество доступных ячеек ОП) X X X X k/ X X X X

Построение пирамиды (IV) 23 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» k = 6 (количество доступных ячеек ОП) X X X X ><

Алгоритм формирования пирамиды 24 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» H – массив, в котором строится пирамида (номера с 1) n – количество элементов в пирамиде a – последовательность, содержащая элементы BUILDHEAP(H, n, a) // Заполнить элементы листы (n/2+1),..., n nh n/2, i n while i > nh do H[i] first(a), a rest(a), i i – 1 // Заполнить элементы n/2, n/2 – 1, n/2 – 2, …, 2, 1 с прим. sift while i > 0 И a do H[i] first(a), a rest(a), SIFT(H, i, n) i i – 1 return (a )

Алгоритм формирования пирамиды (пример, шаг 1) 25 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» BUILDHEAP(H, n, a) // 1. Заполнить элементы листы (n/2+1),..., n nh n/2, i n while i > nh do H[i] first(a), a rest(a), i i – 1 // 2. Заполнить элементы n/2, n/2 – 1, n/2 – 2, …, 2, 1 с прим. sift while i > 0 do H[i] first(a), a rest(a), SIFT(H, i, n) i i – a a

a a Алгоритм формирования пирамиды (пример, шаг 2) 26 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» BUILDHEAP(H, n, a) // 1. Заполнить элементы листы (n/2+1),..., n nh n/2, i n while i > nh do H[i] first(a), a rest(a), i i – 1 // 2. Заполнить элементы n/2, n/2 – 1, n/2 – 2, …, 2, 1 с прим. sift while i > 0 do H[i] first(a), a rest(a), SIFT(H, i, n) i i –

Алгоритм формирования пирамиды (пример, шаг 2) 27 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» BUILDHEAP(H, n, a) // 1. Заполнить элементы листы (n/2+1),..., n nh n/2, i n while i > nh do H[i] first(a), a rest(a), i i – 1 // 2. Заполнить элементы n/2, n/2 – 1, n/2 – 2, …, 2, 1 с прим. sift while i > 0 do H[i] first(a), a rest(a), SIFT(H, i, n) i i – a a

Алгоритм формирования пирамиды (пример, шаг 2) 28 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» BUILDHEAP(H, n, a) // 1. Заполнить элементы листы (n/2+1),..., n nh n/2, i n while i > nh do H[i] first(a), a rest(a), i i – 1 // 2. Заполнить элементы n/2, n/2 – 1, n/2 – 2, …, 2, 1 с прим. sift while i > 0 do H[i] first(a), a rest(a), SIFT(H, i, n) i i – a a

Алгоритм формирования пирамиды (пример, шаг 2) 29 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» BUILDHEAP(H, n, a) // 1. Заполнить элементы листы (n/2+1),..., n nh n/2, i n while i > nh do H[i] first(a), a rest(a), i i – 1 // 2. Заполнить элементы n/2, n/2 – 1, n/2 – 2, …, 2, 1 с прим. sift while i > 0 do H[i] first(a), a rest(a), SIFT(H, i, n) i i – a a

Алгоритм формирования пирамиды (пример, шаг 2) 30 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» BUILDHEAP(H, n, a) // 1. Заполнить элементы листы (n/2+1),..., n nh n/2, i n while i > nh do H[i] first(a), a rest(a), i i – 1 // 2. Заполнить элементы n/2, n/2 – 1, n/2 – 2, …, 2, 1 с прим. sift while i > 0 do H[i] first(a), a rest(a), SIFT(H, i, n) i i – a a

Алгоритм формирования пирамиды (пример, шаг 2) 31 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» BUILDHEAP(H, n, a) // 1. Заполнить элементы листы (n/2+1),..., n nh n/2, i n while i > nh do H[i] first(a), a rest(a), i i – 1 // 2. Заполнить элементы n/2, n/2 – 1, n/2 – 2, …, 2, 1 с прим. sift while i > 0 do H[i] first(a), a rest(a), SIFT(H, i, n) i i – a a Закончить самостоятельно!

Выбор с замещением (пример 1) 32 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» k = 6 (количество доступных ячеек ОП) X X I X X II X X III X X IV

Выбор с замещением (пример 1) 33 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» k = 6 (количество доступных ячеек ОП) X X V ?

Выбор с замещением (пример 1) 34 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» k = 6 (количество доступных ячеек ОП) X X V X X V X X V

Выбор с замещением (пример 1) 35 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» k = 6 (количество доступных ячеек ОП) X X V X X VI X X VII X X VIII

Выбор с замещением (пример 1) 36 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» k = 6 (количество доступных ячеек ОП) X X V X X VI X X VII X X VIII Закончить самостоятельно

Выбор с замещением (пример 2) 37 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» k = X X X X X X X X Если для некоторого элемента a i входной последовательности существует более k элементов, больших a i, то вставка a i в пирамиду приведет к немедленному формированию новой серии

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

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

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

Выбор с замещением (replacement selection) 41 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Данная стратегия основана на использовании очереди с приоритетами для начального распределения серий: Буфер Н0Н0 Н0Н0 Н1Н1 Н1Н1 Н2Н2 Н2Н2 Н3Н3 Н3Н3 Н4Н4 Н4Н4 Н5Н5 Н5Н5 Н6Н6 Н6Н6... Heap Sort

Основная часть алгоритма выбора с замещением (replacement selection base) 42 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» H – массив, в котором строится пирамида (номера с 1) n – количество элементов в пирамиде a – последовательность, содержащая элементы b – выходная последовательность REPSELECT_BASE(a, b, n) L n, b, nh n/2 while a do b b & H[1] if H[1] first(a) then // эта же серия! H[1] first(a), SIFT(H, 1, L), а rest(a) else H[1] H[L], SIFT(H, 1, L – 1) H[L] first(a), а rest(a) if L < nh then SIFT(H, L, n) L L – 1 return (H, L)

43 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» REPSELECT_BASE(a, b, n) L n, b, nh n/2 while a do b b & H[1] if H[1] first(a) then // эта же серия! H[1] first(a), SIFT(H, 1, L), а rest(a) else H[1] H[L], SIFT(H, 1, L – 1) H[L] first(a), а rest(a) if L < nh then SIFT(H, L, n) L L – 1 return (H, L) 10 Основная часть алгоритма выбора с замещением (replacement selection base) L L

44 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» REPSELECT_BASE(a, b, n) L n, b, nh n/2 while a do b b & H[1] if H[1] first(a) then // эта же серия! H[1] first(a), SIFT(H, 1, L), а rest(a) else H[1] H[L], SIFT(H, 1, L – 1) H[L] first(a), а rest(a) if L < nh then SIFT(H, L, n) L L – 1 return (H, L) 1 1 Основная часть алгоритма выбора с замещением (replacement selection base) L L

Завершающая часть алгоритма выбора с замещением (replacement selection base) 45 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» H – массив, в котором строится пирамида (номера с 1) n – количество элементов в пирамиде b – выходная последовательность REPSELECT_FIN(b, H, L, n) R n, nh n/2 while L > 0 do b b & H[1] H[1] H[L], SIFT(H, 1, L – 1), H[L] H[R] if L < nh then SIFT(H, L, R – 1) L L – 1, R R – 1 while L > 0 do b b & H[1], H[1] H[R] R R – 1, SIFT(H, 1, R)

Завершающая часть алгоритма выбора с замещением (replacement selection base) 46 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» REPSELECT_FIN(b, H, L, n) R n, nh n/2 while L > 0 do b b & H[1] H[1] H[L], SIFT(H, 1, L – 1), H[L] H[R] if L < nh then SIFT(H, L, R – 1) L L – 1, R R – 1 while L > 0 do b b & H[1], H[1] H[R] R R – 1, SIFT(H, 1, R) L X X L b RR b

Завершающая часть алгоритма выбора с замещением (replacement selection base) 47 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» REPSELECT_FIN(b, H, L, n) R n, nh n/2 while L > 0 do b b & H[1] H[1] H[L], SIFT(H, 1, L – 1), H[L] H[R] if L < nh then SIFT(H, L, R – 1) L L – 1, R R – 1 while L > 0 do b b & H[1], H[1] H[R] R R – 1, SIFT(H, 1, R) X X X X LR b X X X X X X LR Закончить самостоятельно

Алгоритм выбора с замещением 48 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» n – количество элементов в пирамиде a – последовательность, содержащая элементы b – выходная последовательность REPSELECT(a, b, n) if BUILDHEAP(H, n, a) = false then return false (H, L) REPSELECT_BASE(a, b, n) REPSELECT_FIN(b, H, L, n)

Литература 49 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 1.Вирт Н. Алгоритмы и структуры данных. Новая версия для Оберона / Пер. с англ. Ткачев Ф.В. – М.: ДМК Пресс, 2012 г. – 272 с., 2.Кнут, Д.Э. Искусство программирования: в 3 т. Т. 3. Сортировка и поиск [Текст] : [учеб. пособие]; пер. с англ. / под общ. ред. Ю.В. Казаченко. - 3-е изд. – М.: Издат.дом "Вильямс", – 822с. 3.Седжвик Р. Алгоритмы на C++ (Algorithms in C++): Пер. с англ. – М.: Издательский дом "Вильямс", 2011 г. – 1056 c. – ISBN , ;