Слайды и текст доклада
Pic.1
Основы программирования Эффективные алгоритмы сортировки
Pic.2
Задача сортировки элементов массива Дан массив значений . Необходимо найти такую перестановку индексов , что для последовательности выполняется . - это некоторая перестановка чисел , поэтому общее …
Pic.3
Рекуррентное слияние (снизу вверх) Пусть – текущая длина серий в массиве (в исходном массиве серий и ). Проход в сортировке слиянием: массив A содержит текущих серий длины пары смежных серий …
Pic.4
Рекуррентное слияние (снизу вверх) В общем случае , поэтому на любом проходе возможны варианты: число текущих серий нечетно последняя серия имеет длину Поэтому при слиянии серий необходимо учесть, …
Pic.5
Рекуррентный алгоритм слияния void merge_sort(double *A, int n) { int s, b, c, e; double *D = new double[n]; for (s = 1; s < n; s *= 2) { for (b = 0; b < n; b += s*2) { c = min(b+s-1, n-1); e = …
Pic.6
Сортировка Шелла Основана на сортировке вставками (или обменной): элемент добавляется к уже отсортированной последовательности элементов . Для этого сравнивается и меняется с , пока . Общее число …
Pic.7
Сортировка Шелла: h-цепочки Зафиксируем и рассмотрим -цепочки – последовательности элементов с индексами: … Всего будет цепочек длиной .
Pic.8
Сортировка вставкам с шагом h Сортировка одной цепочки: , сортировка всех цепочек: . После упорядочения всех цепочек с шагом массив не будет отсортирован, но число инверсий в нем уменьшится. Если …
Pic.9
Сортировка Шелла: идея и требования Идея: сортировка всех -цепочек с последовательным уменьшением значений . С каждым проходом массив становится все ближе к упорядоченному, поэтому и трудоемкость …
Pic.10
Сортировка Шелла: выбор шага h Д. Кнут показал: Выбор шага - неудачный, т. к. при этом Цепочки хорошо перемешиваются при выборе взаимно простых . Хорошие последовательности для значений : . При …
Pic.11
Сортировка Шелла: алгоритм Используется последовательность , начальное значение вычисляется таким образом, чтобы начальные цепочки содержали элементов. void shell_sort(double *A, int n) { int i, j, …
Pic.12
Пирамидальная сортировка В алгоритме строится пирамида (бинарная куча), которую можно представить в виде бинарного дерева: каждой вершине соответствует элемент массива каждая вершина имеет 2 …
Pic.13
Свойства пирамиды (бинарной кучи) В корне пирамиды располагается максимальный элемент. Если пирамида имеет уровней и все уровни заполнены, то общее число вершин . Если , то -й уровень заполнен не до …
Pic.14
Идея сортировки Пусть на массиве длины построена пирамида и номер ее последнего элемента . Если поменять местами элементы с индексами 0 и , то максимальный элемент встанет на свое (последнее) место в …
Pic.15
Построение пирамиды При построении пирамиды также проводится просеивание элементов. Просеивать можно только в пирамиде, поэтому она будет строиться снизу вверх: элементы с номерами не имеют потомков …
Pic.16
Трудоемкость построения пирамиды Пусть пирамида имеет уровней, и все они заполнены. Тогда: на уровне находятся вершин, которые не надо просеивать на уровне находятся вершин, которые при просеивании …
Pic.17
Трудоемкость построения пирамиды Таким образом, максимальное число уровней, которые могут пройти все вершины, составляет (при ): Следовательно, трудоемкость построения пирамиды в наихудшем: .
Pic.18
Функция просеивания в пирамиде Параметры и переменные функции sift: i – начальный номер просеиваемого элемента, m – номер конечного элемента в текущей пирамиде, j – текущий номер просеиваемого …
Pic.19
Алгоритм пирамидальной сортировки void heap_sort(double *A, int n) { int i, m; // построение пирамиды for (i = n/2; i >= 0; i--) sift(A, i, n-1); // сортировка массива for (m = n-1; m >= 1; …
Pic.20
Быстрая сортировка (Хоар) В быстрой сортировке проводится рекурсивная обработка массива и его отдельных частей. При каждом рекурсивном вызове задаются границы текущей части. Обозначим индексы ее …
Pic.21
Быстрая сортировка После разделения элемент окажется на своем месте в упорядоченном массиве, а части и можно сортировать рекурсивно и независимо. Разделение массива длины необходимо проводить за …
Pic.22
Быстрая сортировка: трудоемкость в среднем и отличаются в порядках, поэтому нужно оценить трудоемкость в среднем: различные случаи соответствуют различным позициям вероятности для всех случаев равны …
Pic.23
Трудоемкость в среднем: доказательство Положим и . Покажем, что . Доказательство (мат. индукция): Базис Пусть выполняется , тогда
Pic.24
Трудоемкость в среднем: доказательство Оценка для суммы: Здесь интеграл взят по частям: , и в нашем случае .
Pic.25
Трудоемкость в среднем: доказательство Таким образом:
Pic.26
Разделение массива: 1-й способ Текущая разделяемая часть массива: . – текущий индекс опорного элемента (начальные значения ). – самый правый непроверенный элемент (начальное значение ). k = b; j = e; …
Pic.27
Разделение массива: 2-й способ Опорный элемент можно выбрать на любой позиции разделяемой части, его индекс не важен. и – левая и правая границы непроверенной части (начальные значения ). Пока : …
Pic.28
Быстрая сортировка с 2 рекурсивными вызовами void quick_sort_2(double *A, int b, int e) { double x; int i, j; x = A[(b+e)/2]; i = b; j = e; while (i < j) { while (A[i] < x) i++; while (A[j] …
Pic.29
Быстрая сортировка с 1 рекурсивным вызовом В наихудшем случае опорный элемент после разделения текущей части всегда оказывается либо в позиции , либо в позиции , т. е. нужно рекурсивно сортировать …
Pic.30
Быстрая сортировка с 1 рекурсивным вызовом Идея сортировки с 1 рекурсивным вызовом: устанавливаются текущие границы (нижняя) и (верхняя), текущая часть массива делится опорным элементом на 2 части, …
Pic.31
Быстрая сортировка с 1 рекурсивным вызовом void quick_sort(double *A, int b, int e) { double x; int i, j, c = b, d = e; while (c < d) { x = A[(c+d)/2]; i = c; j = d; while (i < j) { while (A[i] …
Pic.32
Свойства алгоритмов сортировки Сравнение алгоритмов сортировки по : быстрая < слияние < пирамидальная Выбор при различных : десятки – простые алгоритмы, сотни или несколько тысяч – алгоритм …
Pic.33
Поиск k-го минимального элемента Задача: в массиве найти -й по значению элемент (т. е. элемент, который стоял бы на позиции , если бы массив был упорядочен по возрастанию). Варианты решения: Для …
Pic.34
Поиск k-го минимального элемента Идея для общего случая: разделение массива опорным элементом, как в быстрой сортировке (пусть опорный элемент после разделения попадает на позицию ) рекурсивная или …
Pic.35
Алгоритм поиска k-го минимального элемента double med(double *A, int n, int k) { int b = 0, e = n-1; double x; while (b < e) { j = b; i = e; x = A[b]; while (j < i) if (A[i] >= x) i--; else …
Pic.36
Цифровая сортировка Пусть для целочисленного массива выполняется: , где и – целые и . Тогда для сортировки массива достаточно сформировать счетчик (целочисленный массив count[0…e-b]), подсчитать …
Pic.37
Простейший алгоритм цифровой сортировки void rad_sort(int *A, int n, int b, int e) { int i, j, k, *count; count = new int[e-b+1]; for (i = 0; i <= e-b; i++) count[i] = 0; for (i = 0; i < n; …
Pic.38
Косвенная цифровая сортировка Пусть при тех же условиях массив A нужно упорядочить косвенно, т. е. сформировать массив индексов в порядке возрастания элементов A. В этом случае нам понадобятся 3 …
Pic.39
Алгоритм косвенной цифровой сортировки int* ind_rad_sort(int *A, int n, int b, int e) { int i, *count, *pos, *Ind; count = new int[e-b+1]; pos = new int[e-b+1]; Ind = new int[n]; for (i = 0; i <= …
Pic.40
Косвенная цифровая сортировка со списками Если использовать списки целых (класс List из раздела «Линейные списки»), то можно записать более элегантный алгоритм косвенной сортировки массива A. В этом …
Pic.41
Косвенная цифровая сортировка со списками List lrad_sort(int *A,int n, int b, int e) { int i; List LRes, *LMas; LMas = new List[e-b+1]; for (i = 0; i < n; i++) LMas[A[i]-b]. push_back(i); for (i = …
Pic.42
Цифровая сортировка целых чисел Целые 4-байтовые числа можно делить на отдельные байты и сортировать по байтам (косвенно), начиная с младших (). При сортировке по байту необходимо: выбирать числа в …
Pic.43
Цифровая сортировка целых чисел Отметим, что положительные и отрицательные целые числа имеют разную внутреннюю кодировку, поэтому их нужно сортировать раздельно. Мы рассмотрим только неотрицательные …
Pic.44
Цифровая сортировка неотрицательных целых List radix_sort(unsigned *A, int n) { int i, k, j, m; List LRes, *LMas = new List[256]; for (i = 0; i < n; i++) LRes. push_back(i); for (k = 0; k < 4; …
Скачать презентацию
Если вам понравился сайт и размещенные на нем материалы, пожалуйста, не забывайте поделиться этой страничкой в социальных сетях и с друзьями! Спасибо!