Презентация Основы программирования. Эффективные алгоритмы сортировки онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Основы программирования. Эффективные алгоритмы сортировки абсолютно бесплатно. Урок-презентация на эту тему содержит всего 44 слайда. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:44 слайда
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:2.98 MB
- Просмотров:92
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Основы программирования
Эффективные алгоритмы сортировки
№2 слайд
Содержание слайда: Задача сортировки элементов массива
Дан массив значений .
Необходимо найти такую перестановку индексов , что для последовательности выполняется .
- это некоторая перестановка чисел , поэтому общее количество потенциальных решений задачи равно числу перестановок из элементов, т.е.
Минимальная гарантированная трудоемкость в наихудшем для сортировки, основанной на сравнениях:
Алгоритмы с такой трудоемкостью мы будем считать эффективными.
№3 слайд
Содержание слайда: Рекуррентное слияние (снизу вверх)
Пусть – текущая длина серий в массиве (в исходном массиве серий и ).
Проход в сортировке слиянием:
массив A содержит текущих серий длины
пары смежных серий сливаются в серий длины в рабочий массив D
новые серии копируются из D в A.
Проходы повторяются при , пока (т.е. ).
Общее число проходов составляет .
На каждом проходе в слиянии участвуют все элементов, поэтому
№4 слайд
Содержание слайда: Рекуррентное слияние (снизу вверх)
В общем случае , поэтому на любом проходе возможны варианты:
число текущих серий нечетно
последняя серия имеет длину
Поэтому при слиянии серий необходимо учесть, что 2-я серия может быть короче 1-й или вообще пустой.
В приведенном ниже алгоритме вычисляются индексы b,c и e, которые задают границы сливаемых серий: A[b…c] и A[c+1…e].
№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 = min(c+s, n-1);
merge_series(A, b, c, e, D);
}
for (b = 0; b < n; b++) A[b] = D[b];
}
delete [] D;
}
№6 слайд
Содержание слайда: Сортировка Шелла
Основана на сортировке вставками (или обменной):
элемент добавляется к уже отсортированной последовательности элементов . Для этого сравнивается и меняется с , пока .
Общее число сравнений для всех :
Чем меньше в массиве инверсий, тем быстрее он сортируется.
№7 слайд
Содержание слайда: Сортировка Шелла: h-цепочки
Зафиксируем и рассмотрим
-цепочки – последовательности элементов с индексами:
…
Всего будет цепочек длиной .
№8 слайд
Содержание слайда: Сортировка вставкам с шагом h
Сортировка одной цепочки: ,
сортировка всех цепочек: .
После упорядочения всех цепочек с шагом массив не будет отсортирован, но число инверсий в нем уменьшится. Если повторить этот проход с шагом, меньшим , то инверсий станет еще меньше и, соответственно, уменьшится трудоемкость выполнения следующего прохода.
№9 слайд
Содержание слайда: Сортировка Шелла: идея и требования
Идея: сортировка всех -цепочек с последовательным уменьшением значений
. С каждым проходом массив становится все ближе к упорядоченному, поэтому и трудоемкость проходов будет уменьшаться.
Требования:
(число проходов) должно быть небольшим
-цепочки должны максимально перемешиваться с -цепочками (чтобы при следующем проходе сравнивались элементы из разных цепочек предыдущего прохода).
№10 слайд
Содержание слайда: Сортировка Шелла: выбор шага h
Д. Кнут показал:
Выбор шага - неудачный, т.к. при этом
Цепочки хорошо перемешиваются при выборе взаимно простых .
Хорошие последовательности для значений :
.
При выборе таких последовательностей:
№11 слайд
Содержание слайда: Сортировка Шелла: алгоритм
Используется последовательность , начальное значение вычисляется таким образом, чтобы начальные цепочки содержали элементов.
void shell_sort(double *A, int n)
{
int i, j, h;
for (h = 1; h <= n / 9; h = h * 3 + 1);
while (h >= 1)
{
for (i = h; i < n; i++)
for (j=i-h; j>=0&& A[j]>A[j+h]; j-=h)
swap(A[j], A[j+h]);
h = (h - 1) / 3;
}
}
№12 слайд
Содержание слайда: Пирамидальная сортировка
В алгоритме строится пирамида (бинарная куча), которую можно представить в виде бинарного дерева:
каждой вершине соответствует элемент массива
каждая вершина имеет 2 вершин-сыновей
заполнены все уровни, кроме, возможно, последнего
значение-отец всегда не меньше значений-сыновей.
Просеивание в пирамиде (если нарушено условие):
9 <= 2 8 8
/ \ / \ / \
8 6 2 6 5 6
/ \ / \ => / \ / \ => / \ / \
5 3 1 4 5 3 1 4 2 3 1 4
/ \ / \ / / \ / \ / / \ / \ /
0 2 3 1 0 0 2 3 1 0 0 2 3 1 0
№13 слайд
Содержание слайда: Свойства пирамиды (бинарной кучи)
В корне пирамиды располагается максимальный элемент.
Если пирамида имеет уровней и все уровни заполнены, то общее число вершин
.
Если , то -й уровень заполнен не до конца.
Пирамида с вершинами имеет уровней, поэтому максимальное число сравнений при просеивании
.
Пирамиду можно построить непосредственно на массиве:
для любого элемента-отца сыновьями будут и
условие пирамиды:
№14 слайд
Содержание слайда: Идея сортировки
Пусть на массиве длины построена пирамида и номер ее последнего элемента .
Если поменять местами элементы с индексами 0 и , то максимальный элемент встанет на свое (последнее) место в упорядоченном массиве.
Для 0-го элемента условие пирамиды будет нарушено. Чтобы восстановить пирамиду, этот элемент нужно просеять, не изменяя положение максимального элемента , т.е. в пирамиде длины .
Далее необходимо повторить эти действия для всех значений , убывающих от до 1.
Трудоемкость сортировки:
№15 слайд
Содержание слайда: Построение пирамиды
При построении пирамиды также проводится просеивание элементов. Просеивать можно только в пирамиде, поэтому она будет строиться снизу вверх:
элементы с номерами не имеют потомков и образуют нижний уровень пирамиды (их просеивать не нужно)
элементы с номерами от до 0 последовательно просеиваются в уже построенных частях пирамиды.
№16 слайд
Содержание слайда: Трудоемкость построения пирамиды
Пусть пирамида имеет уровней, и все они заполнены. Тогда:
на уровне находятся вершин, которые не надо просеивать
на уровне находятся вершин, которые при просеивании могут сместиться только на 1 уровень
на уровне находятся вершин, которые при просеивании могут сместиться только на 2 уровня
и т.д. вплоть до 1-го уровня с 1 вершиной.
№17 слайд
Содержание слайда: Трудоемкость построения пирамиды
Таким образом, максимальное число уровней, которые могут пройти все вершины, составляет (при ):
Следовательно, трудоемкость построения пирамиды в наихудшем: .
№18 слайд
Содержание слайда: Функция просеивания в пирамиде
Параметры и переменные функции sift:
i – начальный номер просеиваемого элемента,
m – номер конечного элемента в текущей пирамиде,
j – текущий номер просеиваемого элемента,
k – номер левого или большего сына j.
void sift(double *A, int i, int m)
{
int j = i, k = i*2+1; // левый сын
while (k <= m)
{
if (k<m && A[k]<A[k+1]) k++; // больший сын
if (A[j] < A[k])
{ swap(A[j], A[k]); j = k; k = k*2+1; }
else break;
}
}
№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; m--)
{
swap(A[0], A[m]);
sift(A, 0, m-1);
}
}
№20 слайд
Содержание слайда: Быстрая сортировка (Хоар)
В быстрой сортировке проводится рекурсивная обработка массива и его отдельных частей. При каждом рекурсивном вызове задаются границы текущей части. Обозначим индексы ее начального и конечного элементов и (при первом вызове ).
Основной шаг сортировки – разделение текущей части массива опорным элементом: выбирается некоторый элемент и текущая часть приводится к виду
№21 слайд
Содержание слайда: Быстрая сортировка
После разделения элемент окажется на своем месте в упорядоченном массиве, а части и можно сортировать рекурсивно и независимо.
Разделение массива длины необходимо проводить за элементарных шагов, при этом:
наилучшее разделение – 2 подмассива длины и
наихудшее – 1 подмассив длины (второй будет пустым) и
№22 слайд
Содержание слайда: Быстрая сортировка: трудоемкость в среднем
и отличаются в порядках, поэтому нужно оценить трудоемкость в среднем:
различные случаи соответствуют различным позициям
вероятности для всех случаев равны
для любого фиксированного .
Таким образом, трудоемкость в среднем:
№23 слайд
Содержание слайда: Трудоемкость в среднем: доказательство
Положим и .
Покажем, что .
Доказательство (мат. индукция):
Базис
Пусть выполняется ,
тогда
№24 слайд
Содержание слайда: Трудоемкость в среднем: доказательство
Оценка для суммы:
Здесь интеграл взят по частям: ,
и в нашем случае .
№25 слайд
Содержание слайда: Трудоемкость в среднем: доказательство
Таким образом:
№26 слайд
Содержание слайда: Разделение массива: 1-й способ
Текущая разделяемая часть массива: .
– текущий индекс опорного элемента (начальные значения ).
– самый правый непроверенный элемент (начальное значение ).
k = b; j = e; x = A[b];
while (k < j)
if (A[j] >= x) j--;
else
{ A[k]=A[j]; A[j]=A[k+1]; A[k+1]=x; k++; }
№27 слайд
Содержание слайда: Разделение массива: 2-й способ
Опорный элемент можно выбрать на любой позиции разделяемой части, его индекс не важен.
и – левая и правая границы непроверенной части (начальные значения ).
Пока :
Пропускаются все с увеличением на 1
Пропускаются все с уменьшением j на 1
Если , то и меняются местами, увеличивается, уменьшается на 1.
№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] > x) j--;
if (i <= j) {
{ swap(A[i], A[j]); i++; j--; }
}
if (b < j) quick_sort_2(A, b, j);
if (i < e) quick_sort_2(A, i, e);
}
№29 слайд
Содержание слайда: Быстрая сортировка с 1 рекурсивным вызовом
В наихудшем случае опорный элемент после разделения текущей части всегда оказывается либо в позиции , либо в позиции , т.е. нужно рекурсивно сортировать либо , либо .
В этом случае не только , но и глубина рекурсии составит . При каждом рекурсивном вызове в стеке выделяется память для параметров и внутренних переменных функции, и в наихудшем случае потребуется памяти в 5-6 раз больше, чем занимает исходный массив.
Для уменьшения глубины рекурсии нужно избавиться от рекурсивной обработки большей из 2 частей, полученных в результате разделения.
№30 слайд
Содержание слайда: Быстрая сортировка с 1 рекурсивным вызовом
Идея сортировки с 1 рекурсивным вызовом:
устанавливаются текущие границы (нижняя) и (верхняя),
текущая часть массива делится опорным элементом на 2 части,
меньшая часть сортируется рекурсивно,
большая часть становится текущей – для этого изменяется либо (большая часть справа), либо (большая часть слева),
обработка продолжается в цикле, пока .
№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] < x) i++;
while (A[j] > x) j--;
if (i <= j)
{ swap(A[i], A[j]); i++; j--; }
}
if (j-c < d-i)
{ if (c < j) quick_sort(A,c,j); c = i; }
else { if (i<d) quick_sort(A,i,d); d = j; }
}
}
№32 слайд
Содержание слайда: Свойства алгоритмов сортировки
Сравнение алгоритмов сортировки по :
быстрая < слияние < пирамидальная
Выбор при различных :
десятки – простые алгоритмы,
сотни или несколько тысяч – алгоритм Шелла
Сортировка называется устойчивой, если она сохраняет порядок следования равных элементов:
пусть в исходном массиве существуют ,
и после сортировки займет позицию , – .
Если при этом , то сортировка устойчива.
№33 слайд
Содержание слайда: Поиск k-го минимального элемента
Задача: в массиве найти -й по значению элемент (т.е. элемент, который стоял бы на позиции , если бы массив был упорядочен по возрастанию).
Варианты решения:
Для используются элементарные алгоритмы.
Если число запросов на поиск , то массив лучше отсортировать (прямо или косвенно).
Если или , то можно построить бинарную кучу и провести шагов, как в пирамидальной сортировке.
№34 слайд
Содержание слайда: Поиск k-го минимального элемента
Идея для общего случая:
разделение массива опорным элементом, как в быстрой сортировке (пусть опорный элемент после разделения попадает на позицию )
рекурсивная или рекуррентная обработка той части массива, в которую попадает -й элемент (возможны 3 варианта, в зависимости от того, какое из трех условий выполняется).
№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
{ A[j++] = A[i]; A[i] = A[j]; A[j] = x; }
if (k < j) e = j-1;
else if (k > j) b = j+1;
else { b = j; break; }
}
return A[b];
}
№36 слайд
Содержание слайда: Цифровая сортировка
Пусть для целочисленного массива выполняется:
, где и – целые и .
Тогда для сортировки массива достаточно сформировать счетчик (целочисленный массив count[0…e-b]), подсчитать частоты всех значений и записать в все группы одинаковых значений по возрастанию.
При этом , счетчик count[i] будет задавать общее число значений, равных (или наоборот, значение некоторого элемента A[j] соответствует счетчику count[A[j]-b]).
№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; i++)
count[A[i]-b]++;
for (k = i = 0; i <= e-b; i++)
for (j = 0; j < count[i]; j++)
A[k++] = b + i;
delete [] count;
}
Трудоемкость данного алгоритма .
№38 слайд
Содержание слайда: Косвенная цифровая сортировка
Пусть при тех же условиях массив A нужно упорядочить косвенно, т.е. сформировать массив индексов в порядке возрастания элементов A.
В этом случае нам понадобятся 3 целочисленных массива:
формируемый массив индексов Ind[0…n-1],
массив счетчиков count[0…e-b],
массив pos[0…e-b] текущих позиций в Ind индексов элементов массива A (индекс i очередного выбираемого элемента A[i] будет записан в Ind на позиции pos[A[i]-b]).
№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 <= e-b; i++) count[i] = 0;
for (i = 0; i < n; i++) count[A[i]-b]++;
for (pos[0] = 0, i = 1; i <= e-b; i++)
pos[i] = pos[i-1] + count[i-1];
for (i = 0; i < n; i++)
Ind[pos[A[i]-b]++] = i;
delete [] count; delete [] pos;
return Ind;
}
Трудоемкость данного алгоритма .
№40 слайд
Содержание слайда: Косвенная цифровая сортировка со списками
Если использовать списки целых (класс List из раздела «Линейные списки»), то можно записать более элегантный алгоритм косвенной сортировки массива A.
В этом случае нам понадобятся:
формируемый список индексов LRes – очередь индексов в порядке возрастания значений A,
массив списков LMas[0…e-b] (индекс i очередного выбираемого элемента A[i] будет добавлен в конец списка LMas[A[i]-b]).
Выходной список (очередь) LRes формируется с помощью последовательного объединения списков LMas.
№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 = 0; i <= e-b; i++)
LRes.join(LMas[i]);
delete [] LMas;
return LRes;
}
Трудоемкость данного алгоритма .
№42 слайд
Содержание слайда: Цифровая сортировка целых чисел
Целые 4-байтовые числа можно делить на отдельные байты и сортировать по байтам (косвенно), начиная с младших (). При сортировке по байту необходимо:
выбирать числа в порядке очереди, полученной в результате сортировки по предыдущему байту (начальная очередь при содержит последовательность индексов от 0 до )
разносить индексы по 256 спискам в соответствии со значением -го байта чисел
сцепить полученные списки в единую очередь (она будет определять порядок выбора чисел при сортировке по байту или окончательный порядок при ).
№43 слайд
Содержание слайда: Цифровая сортировка целых чисел
Отметим, что положительные и отрицательные целые числа имеют разную внутреннюю кодировку, поэтому их нужно сортировать раздельно. Мы рассмотрим только неотрицательные числа.
Цифровая сортировка является устойчивой, поэтому если по байту , то упорядоченность по байту не нарушится.
Для получения значения -го байта числа необходимо сдвинуть битовое представление числа на бит вправо и поделить по модулю 256. Результат будет в младшем байте, остальные байты – нули.
№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; k++)
{
for (i = 0; i < n; i++) {
j = LRes.pop_front(); m=(A[j]>>(k*8))%256;
LMas[m].push_back(j);
}
for (i = 0; i < 256; i++) LRes.join(LMas[i]);
}
delete [] LMas;
return LRes;
}
Трудоемкость данного алгоритма .
Скачать все slide презентации Основы программирования. Эффективные алгоритмы сортировки одним архивом:
