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

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

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

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

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

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

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

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

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

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

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

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

Задание 13 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Выполнить слияние следующих последовательностей: ' ' ' ' 8

ПРОСТАЯ СОРТИРОВКА СЛИЯНИЕМ (STRAIGHT MERGE) 14 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ»

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

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

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

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

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

Простая сортировка слиянием (двухфазная) (straight merge) 20 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Ф1 Проход 1 Ф2 Ф1 Проход

Простая сортировка слиянием (двухфазная) (straight merge) 21 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Ф1 Проход 1 Ф2 Ф1 Проход Ф2

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

Алгоритм простой сортировки слиянием 23 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» ввод n, a k 1 while k < n do (b, c) DISTR(a, n, k) a MERGE(b, c, k) k k 2 done DISTRIBUTE(a, n, k) i 1, b, c while i < n do k min(n – i, k) b b & b c i i + k return (b, c) MERGE(b, c, k) while b ИЛИ с do f 1 first(b), b rest(b), n 1 1 f 2 first(c), c rest(c), n 2 1 while b И с И n 1 k И n 2 k do if f 1 < f 2 then a a & f 1, n 1 n f 1 first(b), b rest(b) else a a & f 2, n 2 n f 2 first(c), c rest(c) while b И n 1 k do n 1 n 1 + 1, a a & first (b), b rest(b) while с И n 2 k do n 2 n 2 + 1, a a & first (с), c rest(c)

Реализация алгоритма распределения 24 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» DISTRIBUTE(a, n, k) i 1, b, c while i < n do k min(n – i, k) b b & b c i i + k return (b, c) void distr(int s[], int n, int d1[], int *d1n, int d2[], int *d2n, int k) { int *wptr = d1, *bptr = d2, *tp; int *wn = d1n, *bn = d2n, i = 0, j, *tn; *wn = 0; *bn = 0; while( i < n ){ k = (k < (n - i)) ? k : n - i; // min(k,n-i) for(j=0; j

Алгоритм простой сортировки слиянием 25 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Выполнить сортировку последовательности: ввод n, a k 1 while k < n do (b, c) DISTR(a) a MERGE(b, c) k k 2 done

Анализ алгоритма простой сортировки слиянием 26 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Количество R пересылок данных на одном этапе: этап состоит из двух фаз, на каждой из которых выполняется копирование всех элементов из a; Количество R элементов, обраб. на одном этапе: R = 2n ввод n, a k 1 while k < n do (b, c) DISTR(a) a MERGE(b, c) k k 2 done

Анализ алгоритма простой сортировки слиянием 27 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Количество i этапов: зависит от параметра k (длина серии), который на каждом этапе удваивается; общее число i этапов: i = [log 2 n] + 1 ввод n, a k 1 while k < n do (b, c) DISTR(a) a MERGE(b, c) k k 2 done ) k = 1 (2 0 ) 2) k = 2 (2 1 ) 3) k = 4 (2 2 ) i) k = 2 i – 1 < n i+1) k = 2 i n

Анализ алгоритма простой сортировки слиянием 28 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Количество M пересылок: M = i R = 2n[log 2 n] = O(nlog 2 n) ввод n, a k 1 while k < n do (b, c) DISTR(a) a MERGE(b, c) k k 2 done Число C сравнений по ключу: сопоставимо с M; время сравнения значительно ниже времени пересылки. Алгоритм требует n = O(n) дополнительной памяти

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

МЕТОД СБАЛАНСИРОВАННЫХ СЛИЯНИЙ (BALANCED MERGE) 30 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ»

Метод сбалансированных слияний (balanced merge) 31 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» a b c d a b

Алгоритм сбалансированных слияний 32 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» ввод n, a k 1 (a, b) DISTR (a, n, k) while k < n do (c, d) MERGE2(a, b, k) (a, b) (c, d) k k 2 done (a, b) (c, d) a MERGE(b, c, k) Предложите алгоритм процедуры MERGE a b c d a b

Объединенная процедура слияния и распределения 33 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» MERGE2(s 1, s 2, k) d 1, d 2, f 1 first(s 1 ), f 2 first(s 2 ), s 1 rest(s 1 ), s 2 rest(s 2 ) while s 1 ИЛИ s 2 do n 1 1, n 2 1 while (s 1 И n 1 k) И (s 2 И n 2 k) do if f 1 < f 2 then d 1 d 1 & f 1, n 1 n 1 + 1, f 1 first(s 1 ), s 1 rest(s 1 ) else d 1 d 1 & f 2, n 2 n 2 + 1, f 2 first(s 2 ), s 2 rest(s 2 ) while s 1 И n 1 k do d 1 d 1 & first (s 1 ) while s 2 И n 2 k do d 1 d 1 & first (s 2 ) d 2 d a b c d

Анализ алгоритма сбалансированной сортировки слиянием 34 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» ввод n, a k 1 (a, b) DISTR(a, n, k) while k < n do (c, d) MERGE2(a, b, k) (a, b) (c, d) k k 2 done (a, b) (c, d) a MERGE(b, c, k) Оцените количество пересылок данных, которое производится при применении алгоритма сбалансированной сортировки слиянием

Анализ алгоритма сбалансированной сортировки слиянием 35 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Количество R пересылок данных на одном этапе: этап состоит из одной фазы, в рамках которой выполняется копирование каждого элемента a; Количество M пересылок на одном этапе: R = n ввод n, a k 1 (a, b) DISTR(a, n, k) while k < n do (c, d) MERGE2(a, b, k) (a, b) (c, d) k k 2 done (a, b) (c, d) a MERGE(b, c, k) a b c d

Анализ алгоритма сбалансированной сортировки слиянием 36 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Количество i этапов: зависит от параметра k (длина серии), который на каждом этапе удваивается; общее число i этапов: i = [log 2 n] + 1 1) k = 1 (2 0 ) 2) k = 2 (2 1 ) 3) k = 4 (2 2 ) i) k = 2 i – 1 < n i+1) k = 2 i n ввод n, a k 1 (a, b) DISTR(a, n, k) while k < n do (c, d) MERGE2(a, b, k) (a, b) (c, d) k k 2 done (a, b) (c, d) a MERGE(b, c, k) I II III

Анализ алгоритма сбалансированной сортировки слиянием 37 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Количество M пересылок: M = i R = n[log 2 n] = O(nlog 2 n) Число C сравнений по ключу: сопоставимо с M; время сравнения значительно ниже времени пересылки. Алгоритм требует 2n = O(n) дополнительной памяти ввод n, a k 1 (a, b) DISTR(a, n, k) while k < n do (c, d) MERGE2(a, b, k) (a, b) (c, d) k k 2 done (a, b) (c, d) a MERGE(b, c, k)

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

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