Презентация «Основы программирования. Эффективные алгоритмы сортировки»

Смотреть слайды в полном размере
Презентация «Основы программирования. Эффективные алгоритмы сортировки»

Вы можете ознакомиться с презентацией онлайн, просмотреть текст и слайды к ней, а также, в случае, если она вам подходит - скачать файл для редактирования или печати. Документ содержит 44 слайда и доступен в формате ppt. Размер файла: 2.98 MB

Просмотреть и скачать

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 do
Рекуррентный алгоритм слияния 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-цепочки Зафиксируем и рассмотрим -цепочки – последовательности элементов с индек
Сортировка Шелла: h-цепочки Зафиксируем и рассмотрим -цепочки – последовательности элементов с индексами: … Всего будет цепочек длиной .
Pic.8
Сортировка вставкам с шагом h Сортировка одной цепочки: , сортировка всех цепочек: . После упорядоче
Сортировка вставкам с шагом h Сортировка одной цепочки: , сортировка всех цепочек: . После упорядочения всех цепочек с шагом массив не будет отсортирован, но число инверсий в нем уменьшится. Если …
Pic.9
Сортировка Шелла: идея и требования Идея: сортировка всех -цепочек с последовательным уменьшением зн
Сортировка Шелла: идея и требования Идея: сортировка всех -цепочек с последовательным уменьшением значений . С каждым проходом массив становится все ближе к упорядоченному, поэтому и трудоемкость …
Pic.10
Сортировка Шелла: выбор шага h Д. Кнут показал: Выбор шага - неудачный, т. к. при этом Цепочки хорош
Сортировка Шелла: выбор шага 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 – начальный номер просеиваемог
Функция просеивания в пирамиде Параметры и переменные функции sift: i – начальный номер просеиваемого элемента, m – номер конечного элемента в текущей пирамиде, j – текущий номер просеиваемого …
Pic.19
Алгоритм пирамидальной сортировки void heap_sort(double *A, int n) { int i, m; // построение пирамид
Алгоритм пирамидальной сортировки 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-й способ Текущая разделяемая часть массива: . – текущий индекс опорного элемен
Разделение массива: 1-й способ Текущая разделяемая часть массива: . – текущий индекс опорного элемента (начальные значения ). – самый правый непроверенный элемент (начальное значение ). k = b; j = e; …
Pic.27
Разделение массива: 2-й способ Опорный элемент можно выбрать на любой позиции разделяемой части, его
Разделение массива: 2-й способ Опорный элемент можно выбрать на любой позиции разделяемой части, его индекс не важен. и – левая и правая границы непроверенной части (начальные значения ). Пока : …
Pic.28
Быстрая сортировка с 2 рекурсивными вызовами void quick_sort_2(double *A, int b, int e) { double x;
Быстрая сортировка с 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 рекурсивным вызовом В наихудшем случае опорный элемент после разделения текущ
Быстрая сортировка с 1 рекурсивным вызовом В наихудшем случае опорный элемент после разделения текущей части всегда оказывается либо в позиции , либо в позиции , т. е. нужно рекурсивно сортировать …
Pic.30
Быстрая сортировка с 1 рекурсивным вызовом Идея сортировки с 1 рекурсивным вызовом: устанавливаются
Быстрая сортировка с 1 рекурсивным вызовом Идея сортировки с 1 рекурсивным вызовом: устанавливаются текущие границы (нижняя) и (верхняя), текущая часть массива делится опорным элементом на 2 части, …
Pic.31
Быстрая сортировка с 1 рекурсивным вызовом void quick_sort(double *A, int b, int e) { double x; int
Быстрая сортировка с 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-го минимального элемента Задача: в массиве найти -й по значению элемент (т. е. элемент, кото
Поиск k-го минимального элемента Задача: в массиве найти -й по значению элемент (т. е. элемент, который стоял бы на позиции , если бы массив был упорядочен по возрастанию). Варианты решения: Для …
Pic.34
Поиск k-го минимального элемента Идея для общего случая: разделение массива опорным элементом, как в
Поиск k-го минимального элемента Идея для общего случая: разделение массива опорным элементом, как в быстрой сортировке (пусть опорный элемент после разделения попадает на позицию ) рекурсивная или …
Pic.35
Алгоритм поиска k-го минимального элемента double med(double *A, int n, int k) { int b = 0, e = n-1;
Алгоритм поиска 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, *c
Простейший алгоритм цифровой сортировки 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 нужно упорядочить косвенно, т. е. сформировать массив индексов в порядке возрастания элементов A. В этом случае нам понадобятся 3 …
Pic.39
Алгоритм косвенной цифровой сортировки int* ind_rad_sort(int *A, int n, int b, int e) { int i, *coun
Алгоритм косвенной цифровой сортировки 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 из раздела «Лин
Косвенная цифровая сортировка со списками Если использовать списки целых (класс List из раздела «Линейные списки»), то можно записать более элегантный алгоритм косвенной сортировки массива A. В этом …
Pic.41
Косвенная цифровая сортировка со списками List lrad_sort(int *A,int n, int b, int e) { int i; List L
Косвенная цифровая сортировка со списками 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-байтовые числа можно делить на отдельные байты и сортировать
Цифровая сортировка целых чисел Целые 4-байтовые числа можно делить на отдельные байты и сортировать по байтам (косвенно), начиная с младших (). При сортировке по байту необходимо: выбирать числа в …
Pic.43
Цифровая сортировка целых чисел Отметим, что положительные и отрицательные целые числа имеют разную
Цифровая сортировка целых чисел Отметим, что положительные и отрицательные целые числа имеют разную внутреннюю кодировку, поэтому их нужно сортировать раздельно. Мы рассмотрим только неотрицательные …
Pic.44
Цифровая сортировка неотрицательных целых List radix_sort(unsigned *A, int n) { int i, k, j, m; List
Цифровая сортировка неотрицательных целых 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; …


Скачать презентацию

Если вам понравился сайт и размещенные на нем материалы, пожалуйста, не забывайте поделиться этой страничкой в социальных сетях и с друзьями! Спасибо!