Слайд 1Задача сортировки
Програмирование на языке высокого уровня
Т.Г.Чурина
Слайд 2
Методы сортировки обычно разделяют на две
категории:
внутреннюю сортировку массивов и внешнюю — сортировку файлов.
Задача сортировки состоит в том, чтобы
упорядочить N объектов a1, ... , аN:
переставить их в такой последовательности аp1,..., apN,
чтобы их ключи расположились в неубывающем
порядке
kp1 < kp2 < ... < kpN.
Слайд 3
Сортировка называется устойчивой,
если она удовлетворяет условию, согласно
которому
записи с одинаковыми ключами
остаются в прежнем порядке:
kРi = kРj
и i < j, то pi < pj
При устойчивой сортировке относительный
порядок элементов с одинаковыми ключами
не меняется.
Слайд 4
Методы сортировки можно разбить на
несколько основных классов в
зависимости
от лежащего в их основе приема сортировки:
— включения;
— выбора;
—
обмена;
— подсчета;
— разделения;
— слияния.
Слайд 5
Разделим условно все элементы массива
на две последовательности: входную
ai,
... , аN
и готовую последовательность a1, ... , аi-1
элементы которой уже отсортированы.
В алгоритмах, основанных на методе включения, на
каждом i-м шаге i-й элемент входной
последовательности вставляется в подходящее
место готовой последовательности.
Слайд 6
Сортировка простыми включениями наиболее очевидна.
Пусть 2 < i
< N, a1, ... , аi-1 уже отсортированы:
a1 а2
... ai-1.
Будем сравнивать по очереди аi с ai-1, аi-2, ... до тех пор, пока
не обнаружим, что элемент аi следует вставить между
aj и aj+1 (0 j i - 1) элементами.
После этого или в процессе поиска подвинем записи
aj+1, ..., ai-1 на одно место вправо и переместим запись
аi в позицию j + 1.
Слайд 7
Процесс сортировки включениями покажем на примере
последовательности, состоящей из
восьми ключей:
i = 1 40 | 51 8
38 90 14 2 63 (13)
i = 2 40 51 | 8 38 90 14 2 63
i = 3 8 40 51 | 38 90 14 2 63
i = 4 8 38 40 51 | 90 14 2 63
i = 5 8 38 40 51 90 | 14 2 63
i = 6 8 14 38 40 51 90 | 2 63
i = 7 2 8 14 38 40 51 90 | 63
i = 8 2 8 14 38 40 51 63 90 |
Слайд 8void sort_by_insertion(key a[], int N)
{ key x;
int
i, j ;
for (i=l; i < N; i++)
{
x = a[i];
for (j=i-1;(j>=0) && (x
a[j+1]= a[j];
a[j+1]=x;
}
}
Слайд 9Анализ. На i-м шаге максимально возможное число сравнений Сi во
внутреннем цикле равно i -1;
если предположить, что все перестановки
N ключей равновероятны, число сравнений в среднем равно i/2.
Для Mi, количества пересылок на i-м шаге, максимальное Мi = Сi + 2. Всего шагов N - 1.
Следовательно, количество сравнений и пересылок в худшем и лучшем случаях:
Слайд 10Сортировка бинарными включениями
Для нахождения места для i-го элемента можно
использовать метод бинарного поиска элемента в
отсортированном массиве, в котором
на i-ом шаге
выполняется ~ log2i сравнений.
Поэтому всего будет произведено ~ Nlog2N сравнений.
Но количество пересылок в этом методе не изменится.
Слайд 11Сортировка включениями с убывающим шагом.
Метод Шелла
Хоар, Флойд, Шелл: для
алгоритмов сортировки,
перемещающих в последовательности запись вправо или
влево только
на одну позицию, среднее время работы будет
в лучшем случае пропорционально N2.
Хотелось бы, чтобы записи перемещались «большими
скачками, а не короткими шажками».
Д. Шелл предложил в 1959 г. метод, названный
сортировкой с убывающим шагом.
Слайд 12На первом проходе выделим в подпоследовательности
элементы, отстоящие друг от
друга на четыре позиции:
Полученные 4 последовательности отсортируем на месте
независимо
друг от друга методом простых включений.
Этот процесс называется 4-сортировкой.
Слайд 13В результате 4-сортировки получим последовательность:
_________________________________
| | | |
40 14 2 38 90 51 8 63
|__________|__________|___________|
На следующем шаге элементы, отстоящие друг от друга на две позиции, объединяются в подпоследовательности.
Этот процесс называется 2-сортировкой.
Слайд 14После 2-сортировки получим последовательность:
Две новые подпоследовательности таковы:
40, 2, 90,
8 14,
38, 51, 63.
2 14 8 38 40 51 90 63
_________________________________
| | | |
40 14 2 38 90 51 8 63
|__________|__________|___________|
2 14 8 38 40 51 90 63
Слайд 16Наконец, на третьем шаге все элементы сортируются методом
простых включений.
К последнему шагу элементы довольно хорошо упорядочены,
поэтому требуется мало
перемещений.
Данный процесс называется 1-сортировкой.
В сортировке методом Шелла можно использовать
любую убывающую последовательность шагов
ht, ht-1, ..., h1
Слайд 17Чтобы выбрать некоторую хорошую последовательность
шагов сортировки, нужно проанализировать время работы
как
функцию от этих шагов.
До сих пор не удалось найти наилучшую
возможную
последовательность шагов ht, ht-1, ..., h1 для больших N.
Кнут:
..., 121, 40, 13, 4, 1, где hk+1= 3 hk + 1, h1 = 1
..., 31, 15, 7, 3, 1, где hk+1 = 2 hk + 1, h1 = 1
Слайд 18Выявлен примечательный факт, что элементы
последовательностей приращений не должны быть
кратны
друг другу.
Это позволяет на каждом проходе сортировки перемешивать
цепочки, которые
ранее никак не взаимодействовали.
Желательно, чтобы взаимодействие между разными
цепочками происходило как можно чаще.
Слайд 19Утверждение.
Если k-отсортироваиная последовательность
i-сортируется (k > i), то она
остается k-отсортированной.
→ C каждым следующим шагом сортировки с убывающим приращением
количество отсортированных элементов в последовательности возрастает.
Для последовательности шагов 2k+1, ..., 9, 5, 3, 1
количество пересылок пропорционально N1.27,
для последовательности 2k–1, ..., 15, 7, 3, 1 — N1.26,
для последовательности (3k - 1)/2, ..., 40, 13, 4, 1 — N1.25
N3/2
Слайд 20Сортировка простым выбором
Методы сортировки посредством выбора основаны на идее
многократного
выбора.
На i-м шаге выбирается наименьший элемент из входной
последовательности
ai, ..., an и меняется местами с ai-м.
Таким образом, после шага i на первом месте во входной
последовательности будет находиться наименьший элемент.
Затем этот элемент перемещается из входной в готовую
последовательность.
Процесс выбора наименьшего элемента из входной
последовательности повторяется до тех пор, пока в ней
останется только один элемент.
Слайд 21Проиллюстрируем этот метод на той же последовательности
40 51 8
38 90 14 2 63.
На первом шаге находим наименьший элемент
2,
обмениваем его с первым элементом 40 и перемещаем
в готовую последовательность:
2 51 8 38 90 14 40 63
2 8 51 38 90 14 40 63
2 8 14 38 90 51 40 63
2 8 14 38 90 51 40 63
2 8 14 38 40 51 90 63
2 8 14 38 40 51 90 63
2 8 14 38 40 51 63 90
Слайд 22Данный метод в некотором смысле противоположен сортировке
простыми включениями.
При сортировке
простым выбором рассматриваются все элементы
входной последовательности и для фиксированного места
из нее
выбирается наименьший элемент.
При этом не возникает необходимости "сдвига" участка массива,
поскольку выбранный элемент вставляется всегда в конец готовой
последовательности. Вытесняемый же элемент достаточно
переставить на освободившееся место в неотсортированной входной части.
Слайд 23void sort_by_selection(key a[], int N)
{ int i,j,k;
key x;
for( i=0; i < N-1; i++) {
k=i;
for
(j=i+l; j < N; j++)
if(a[k] > a[j]) /* k хранит индекс текущего */
k=j; /* минимального элемента */
if (i!=k) {
x=a[i]; a[i]=a[k]; a[k]=x;
}
}
}
Слайд 24Анализ
Число Сi сравнений на i-м шаге не зависит от начального
порядка
элементов.
На первом шаге первый элемент сравнивается с остальными N
- 1
элементами, на втором шаге число сравнений будет — N - 2 и т. д.
Поэтому число сравнений есть
С = (N – 1) + (N – 2) + ... + 1 = N * (N - 1)/2
Максимальное число пересылок Мmах = N -1 так как на каждом
проходе выполняется обмен найденного минимального элемента с i-м.
Вероятность того, что i-й элемент уже стоит на месте, невелика, поэтому
средняя оценка М близка к максимальной.
Слайд 25Мы видим, что число сравнений в методе выбора
сегда равно
максимальному числу сравнений в методе
простых включений, в то время
как число перемещений,
наоборот, минимально.
Если вспомнить, что сравниваются ключи позиций, а
перемещаются записи целиком, то метод выбора,
экономящий число перемещений может на практике
оказаться предпочтительней.
Слайд 26Пирамидальная сортировка
При сортировке методом простого выбора на каждом шаге
Выполняется линейный
поиск минимального элемента.
Линейная сложность этого поиска делает сложность всей
сортировки квадратичной.
Возможно
ли найти минимальный элемент за время лучшее
линейного?
Оказывается, что это возможно, если использовать на
каждом следующем шаге информацию о взаимных
отношениях элементов, накопленную на предыдущих шагах.
Слайд 27Идея бинарного выбора может быть эффективно применена,
если организовать входные данные
в виде так называемой
пирамиды (или сбалансированного бинарного дерева поиска)
и поддерживать их в этом виде в процессе сортировки.
Метод сортировки с использованием такой пирамиды был
предложен Р. У. Флойдом в 1964 г. под названием
«Heap sort» — пирамидальной сортировки
или сортировки кучей.
Слайд 28Пусть дана последовательность h1, ..., hn.
Элемент hi образует пирамиду
в этой последовательности,
если выполнены следующие условия:
— если 2 i
≤ n, то hi ≥ h2i и h2i образует пирамиду;
— если 2 i + 1 ≤ n, то hi ≥ h2i+1 и h2i+1 образует пирамиду.
Элементы hn/2+1, ..., hn всегда образуют тривиальные
пирамиды, поскольку для них приведенные условия имеют
ложные посылки.
Слайд 29Если элемент h1 образует пирамиду, то и каждый элемент
последовательности
образует пирамиду.
В этом случае будем говорить, что вся последовательность
является
полной пирамидой.
Полная пирамида может быть изображена в виде корневого
бинарного дерева, в котором элементы h2i и h2i+1 являются
сыновьями элемента hi.
Элемент в любом узле численно не меньше всех своих потомков, а
вершина полной пирамиды h1 содержит максимальный элемент всей
последовательности.
Слайд 30На рисунке показана полная пирамида при n = 15.
Слайд 31Если число элементов в полной пирамиде не равно 2k –
1,
самый нижний уровень дерева будет неполным:
недостающих сыновей можно достроить, добавив
в
пирамиду несколько заключительных «минимальных»
элементов «о», не нарушающих условия пирамиды.
Последовательность, упорядоченная по убыванию, является полной пирамидой.
Например, последовательность из 12 элементов
12, 11, 7, 8, 10, 6, 3, 2, 1, 5, 9, 4
является полной пирамидой с вершиной 12.
Слайд 33Идея метода пирамидальной сортировки:
1. Подготовка к сортировке: входная неупорядоченная последовательность
перестраивается в пирамиду.
2. Сортировка: входная и готовая последовательности хранятся в
одном массиве, причем готовая последовательность формируется в хвосте массива, а входная остается в начале массива.
Слайд 34Основой реализации метода является следующая процедура
просеивания.
Пусть в последовательности h1,
..., hn элементы hi+1, ..., hn
уже образуют пирамиды.
Требуется
перестроить последовательность так, чтобы
пирамиду образовывал элемент hi.
Слайд 35Просеять (i, n):
пока 2 i < n цикл
/* цикл просеивания hi в поддеревья*/
hl = h2i;
если 2
i + 1 < n то hr : = h2i+1 иначе hr : = о;
если hi > hl и hi > hr то
выход; /* условие пирамиды в hi выполнено*/
если hl > hr то
обменять hi и h2i; /*просеять в левое поддерево*/
i := 2 i;
иначе если hr > о то /*просеять в правое, если оно есть*/
обменять hi и h2i+1;
i :=2 i + 1;
конец цикла
конец
Слайд 36На каждой итерации цикла наибольший из трех элементов
hi, h2i
и h2i+1 путем обмена оказывается в корне текущего
поддерева, что обеспечивает
истинность условий пирамиды
в этом корне.
Если при этом изменяется корень левого или правого
поддерева, то просеивание продолжается для него.
Слайд 38Сортировка
На каждом шаге сортировки первый элемент массива, т. е.
максимальный элемент
пирамиды, переносится в начало
готовой последовательности путем обмена с последним
элементом пирамиды,
занимающим его место.
Затем остаток входной последовательности вновь
перестраивается в пирамиду, обеспечивая корректность
следующего шага.
Слайд 39В начале i-го шага элементы a1, .., ai, по предположению,
хранят входную последовательность как пирамиду, а
ai+1, .., aN –
упорядоченную по возрастанию готовую
последовательность (изначально пустую).
На i-м шаге текущий максимальный элемент пирамиды а1
Обменивается с аi, становясь началом новой готовой
последовательности, где он будет новым минимальным
элементом. Входная последовательность (пирамида) при
этом претерпевает два изменения:
— она теряет последний элемент, что не нарушает условий пирамиды ни в одном узле;
— ее первый элемент становится произвольным, что может нарушать условие пирамиды только в первом узле.
Слайд 40Таким образом, для новой входной последовательности
a1, ..., ai-1
условия
пирамиды выполнены для всех элементов,
кроме первого.
Применение процедуры просеивания к
a1 восстанавливает
полную пирамиду в a1, ..., ai-1, что обеспечивает условия
осуществимости следующего шага.
Слайд 42void Sift(key а[], int i, int n) {
int 1, r, k;
key t;
i++;
while ((l=2*i)
n) {
r = (l+1 <= n)? l+1 : i;
if ((a[i-1]>=a[l-l])&&(a[i-l]>=a[r-l]))
return;
k = (a[l-1]>= a[r-l]) ? 1 : r;
t = a[i-l];
a[i-l] = a[k-l];
a[k-l] = t;
i = k;
}
}
Слайд 43void heap_sort(key a[], int N) {
int i;
key t;
for (i = N/2; i >=
0; i--) /*подготовка*/
Sift (a, i, N);
for (i = N-l; i > 0; i--) { /*сортировка*/
t = a[0];
a[0] = a[i];
a[i] = t;
Sift (a, 0, i); /*просеивание*/
}
}
Слайд 44Анализ
Число итераций цикла в процедуре просеивания не
превосходит высоты пирамиды.
Высота
полного бинарного дерева из N узлов, каковым
является пирамида, равна [log2
N].
Просеивание имеет логарифмическую сложность.
Итоговая сложность пирамидальной сортировки ~N log2 N.
Наилучший случай – обратное упорядочение входной
Последовательности.
Слайд 45Сортировка простым обменом
Метод основан на принципе сравнения и обмена
пар соседних
элементов. На первом шаге сравним последний и предпоследний
элементы, если
они не упорядочены, поменяем их местами. Далее
проделаем то же со вторым и третьим элементами от конца массива,
третьим и четвертым и т. д. до первого и второго с начала массива.
При выполнении этой последовательности операций меньшие элементы
в каждой паре продвинутся влево, наименьший займет первое место в
массиве.
Повторим этот же процесс от N-го до 2-го элемента, потом от N-го до 3-го
и т. д.
i-й проход по массиву приводит к «всплыванию» наименьшего элемента
из входной последовательности на i-e место в готовую
последовательность.
Слайд 46Метод пузырька
void bubble_sort(key a[], int N){
int i,
j;
key x;
for (i=0; i
for (j=N-l; j>i; j--)
if (a[j-l]>a[j]) {
x=a[j];
a[j]=a[j-1];
a [j-1]=x;
}
}
Слайд 47Анализ
Количество сравнений Сi на i - мпроходе равно N -
i,
что приводит к уже известному выражению для С:
С
= (N - 1) + (N - 2) + ... + 1 = N∙(N - 1)/2
Минимальное количество пересылок Mmin= 0,
если массив уже упорядочен,
максимальное Мтах = С, если массив упорядочен по
убыванию.
Слайд 48Шейкер-сортировка
1) Нередко случается, что последние проходы сортировки
простым обменом
работают «вхолостую», так как элементы
уже упорядочены.
Один из способов улучшения
алгоритма сортировки
пузырьком состоит в том, чтобы запомнить, производился ли
на очередном проходе какой-либо обмен.
Если ни одного обмена не было, то алгоритм может
закончить работу.
Слайд 492) Асимметрия метода: один неправильно расположенный
«пузырек» на «тяжелом» конце
почти отсортированного
массива «всплывет» на место за один проход:
Неправильно расположенный
«камень» на «легком»
конце будет «опускаться» на правильное место только
только по одному шажку на каждом проходе:
Слайд 50Поэтому еще одно улучшение алгоритма состоит в
том, чтобы чередовать
направление проходов.
На нечетном проходе будем сравнивать пары от
конца массива
к началу, в результате «легкие»
элементы будут продвигаться к началу массива.
На четных проходах будем сравнивать пары от
начала массива к концу, в результате «тяжелые»
элементы будут продвигаться к концу массива.
Левая и правая границы продвижения на каждом
проходе будут также поочередно сдвигаться на 1.
Слайд 51void shaker_sort (key a[], int N) {
int
j, k, l, r;
int fl;
key x;
l = 0;
r = k = N-l;
do {
fl = 1;
for (j = r; j > 1; j--) {
if (a[j-1] > a[j]) {
fl = 0;
x = a[j-l];
a[j-l] = a[j];
a[j]= x;
к = j-1; /* позиция пузырька */
}
}
Слайд 52l = k+1;
if (!fl)
for (j = 1+1; j
{
if (a[j-l] > a[j]) {
x = a [j-1];
a[j-l]
= a[j];
a[j] = x;
k = j; /* позиция камня */
}
}
r = k-1;
} while ((l}
Слайд 53Анализ
Стin= N –1. Кнут показал, что среднее число сравнений
пропорционально N2
- N.
Но все предложенные улучшения не влияют на число
обменов.
В самом деле, каждый обмен уменьшает число инверсий в
массиве на 1, следовательно, при любом алгоритме,
основанном на обмене пар соседних элементов, число
необходимых перестановок одинаково и равно числу
инверсий в массиве.
Cортировка обменом и ее улучшенная сортировка хуже,
чем сортировка включениями и выбором.
Шейкер-сортировку выгодно использовать тогда, когда массив
почти упорядочен.
Слайд 54Сортировка с разделением. Быстрая сортировка Ч. Э. Р. Хоар
Метод
сортировки, при котором обмениваются местами
пары несоседних элементов, а задача сортировки
последовательности
рекурсивно сводится к задачам
сортировки ее меньших частей.
Слайд 55Допустим сначала, что мы уже переупорядочили
некоторым образом элементы входной
последовательности, после
чего оказалось
возможным разделить ее на две непустые части по
границе некоторого
индекса т:
левую (индексы 1...т) и
правую (индексы т+1...N);
причем все элементы левой части не превосходят всех
элементов правой части:
i, j: 1 i m и m < j N выполнено: аi ≤ aj. (14)
Слайд 56Индекс т назовем медианой.
Отсортируем любым методом обмена отдельно левую
часть,
не затрагивая элементов правой части, а затем отдельно
правую, не трогая
левой.
При этом обмениваться могут только пары элементов,
находящиеся в одной части, поэтому никакой обмен не
нарушает свойство (14).
Значит, оно будет верно и для результирующей
последовательности, которая в силу этого оказывается
упорядоченной в целом.
Слайд 57 СортировкаРазделением (l, r)
/* l, r – границы сортируемой подпоследовательности
*/
/* Разделение */
привести подпоследовательность аl ,…, аr к условию (14)
и
определить медиану m;
/* Рекурсивный спуск */
если l < m то /* части длины 0 и 1 не сортируем */
СортировкаРазделением (l, m);
если m + 1 < m то /* части длины 0 и 1 не сортируем */
СортировкаРазделением (m + 1, r);
конец
Слайд 58Получается, что в процессе дробления исходной задачи на подзадачи мы
приходим к тривиальным подзадачам:
cортировке последовательностей длины 0 и 1.
Не приходится ничего делать и для слияния решений подзадач в
решение исходной задачи во время возврата из рекурсии:
упорядоченные последовательности образуются сами собой по мере
упорядочения их частей.
Где же тогда фактически выполняется сортировка?
На фазе разделения, иллюстрируя, как хорошая подготовка условий для
решения зачастую уже и дает решение!
Слайд 59В качестве критерия разделения нам понадобится так называемый
пилотируемый элемент х.
В классической версии алгоритма в качестве x выбирается произвольный
элемент сортируемой
последовательности: первый, последний,
расположенный в середине или иначе.
Влияние его выбора на эффективность алогритма мы обсудим ниже.
В процессе разделения мы соберем в левой части последовательности
все элементы аi х, а в правой — все элементы aj x.
Условие (14) при этом будет выполнено даже при возможном наличии
одинаковых элементов x в обеих частях.
Слайд 60Введем два бегущих индекса-указателя i и j, которые делят
разделяемую подпоследовательность
на три участка:
левый (al ... ai-1),
правый (aj+1 ...
ar),
средний (ai ... aj).
В левом и правом участках будут накапливаться элементы
левой и правой частей, подлежащих затем рекурсивной
сортировке, а в среднем находятся остальные, еще не
распределенные элементы.
Слайд 61Процесс разделения:
i = l; j = r;
Цикл
пока ai
х цикл /* проверка i < r
не нужна: х где-то есть */
i := i + 1; /* в конце ai х */
конец цикла;
пока х < aj цикл /* проверка j > i не нужна: х есть */
j := j – 1; /* в конце aj х */
конец цикла;
если i ≤ j то /* если i = j, a[i = j] = x, нужен сдвиг индексов
для выхода из цикла */
обменять ai и aj /* теперь ai х aj */
i := i + 1; /*на случай ai = х : добавить в левую часть */
j := j – 1; /* на случай aj = х : добавить в правую часть */
пока i < j
Слайд 62Циклы по встречным индексам переносят из средней части в левую
или
правую элементы, строго меньшие или большие х, которые могут быть
добавлены
в эти части без перестановки.
После их выполнения процесс разделения либо заканчивается
(если i j), либо пара ai и aj образует инверсию.
В последнем случае их следует обменять и включить в левую и правую
части.
Вот здесь и происходят упорядочивающие обмены с уменьшением числа
инверсий в последовательности!
Слайд 63Проверка того, что бегущие индексы не выходят за границы l...r,
строго
говоря, необходима, но фактически не нужна:
на первом проходе
выход за границы немозможен, так как в массиве
есть сам элемент х и оба цикла остановятся на нем.
В конце же первого прохода происходит обмен элементов и обе части
становятся не пусты, что гарантирует остановку циклов по встречным
индексам в пределах интервала l...r и на следующих проходах.
Слайд 64Цикл оканчивается при i j.
Однако нам еще надо определить
медиану.
Определенные границы левой части – l...i – 1,
правой
– j + 1...r, однако интервал j + 1...i – 1 может быть не
вырожден и заполнен элементами х (почему?).
Эти элементы останутся на своих местах в процессе
сортировки (почему?), поэтому их можно исключить из
левой и правой частей.
Окончательно границами левой части можно считать l...j,
а правой – i...r.
Слайд 67void quicksort(key a[], int 1, int r) {
key
x, w; int i, j;
i = 1;
j
= r;
x = a[(l+r)/2];
do {
while (a[i] < x) i++;
while (x < a[j]) j--;
if(i <= j) {
w = a[i];
a[i] = a[j] ;
a[j] = w;
i++; j--;
}
} while (i if (l if (i}
Слайд 68Анализ
Процессу разбиения подвергается весь массив,
следовательно выполняется N сравнений.
Число обменов?
Пусть после разделения х будет занимать в массиве
позицию k.
Число
требующихся обменов равно числу элементов в левой
части массива (k - 1), умноженному на вероятность того, что
элемент нужно обменять.
Элемент обменивается, если он не меньше, чем х.
Вероятность этого равна (N - (k - 1))/N.
Слайд 69Просуммируем всевозможные варианты выбора медианы и
разделим эту сумму на N,
в результате получим ожидаемое
число обменов:
Ожидаемое число обменов равно приблизительно N/6.
В лучшем случае каждое разделение разбивает массив на две равные части, а число проходов, необходимых для сортировки, равно log2 N. Тогда общее число сравнений равно N log2 N.
Слайд 70Однако в худшем случае сортировка становится
«медленной».
Например, когда в качестве
пилотируемого элемента всегда
выбирается наибольшее значение. Тогда в результате
разбиения в левой
части оказывается N - 1 элемент,
т. е. массив разбивается на подмассивы из одного элемента
и из N - 1 элемента.
В этом случае вместо log2 N разбиений необходимо сделать
~ N разбиений.
В результате в худшем случае оценка оказывается ~ N2.
что гораздо хуже пирамидальной сортировки.
Слайд 71Сортировка методом подсчета
При сортировке подсчетом каждый элемент поочередно сравнивается
со
всеми остальными и подсчитывается количество элементов,
которые меньше его. Это число
(+1) определяет позицию элемента в
отсортированной последовательности при условии, что все элементы
различны.
Простейшая реализация этого метода требует дополнительного
массива, в котором накапливаются отсортированные элементы. Это
связано с тем, что в данном методе входная последовательность не
сокращается по мере обработки элементов.
![void sort_by_insertion(key a[], int N){ key x; int i, j ; for (i=l; i <](/img/thumbs/a44cceb7c721b04abc0bf0197e034519-800x.jpg "Задача сортировки Програмирование на языке высокого уровня Т.Г.Чурина void sort_by_insertion(key a[], int N){ key x; int i, j")
![void sort_by_selection(key a[], int N){ int i,j,k; key x; for( i=0; i < N-1; i++)](/img/thumbs/0d916e2621dd73aa6e14c058d123d5b1-800x.jpg "Задача сортировки Програмирование на языке высокого уровня Т.Г.Чурина void sort_by_selection(key a[], int N){ int i,j,k; key x; for( i=0;")
![void Sift(key а[], int i, int n) { int 1, r, k; key t; i++; while](/img/thumbs/cee3d6759c894ce244172672d1b8c6c5-800x.jpg "Задача сортировки Програмирование на языке высокого уровня Т.Г.Чурина void Sift(key а[], int i, int n) { int 1,")
![void heap_sort(key a[], int N) { int i; key t; for (i = N/2;](/img/thumbs/8cc66e94610c32e18052e5fa6fecd123-800x.jpg "Задача сортировки Програмирование на языке высокого уровня Т.Г.Чурина void heap_sort(key a[], int N) { int i; key")
![Метод пузырькаvoid bubble_sort(key a[], int N){ int i, j; key x; for (i=0; ii; j--)](/img/thumbs/539908a2878eac7b3731653ead0bd02d-800x.jpg "Задача сортировки Програмирование на языке высокого уровня Т.Г.Чурина Метод пузырькаvoid bubble_sort(key a[], int N){ int i, j; key")
![void shaker_sort (key a[], int N) { int j, k, l, r; int fl;](/img/thumbs/034c056ea368b622543af5a3738a66a8-800x.jpg "Задача сортировки Програмирование на языке высокого уровня Т.Г.Чурина void shaker_sort (key a[], int N) { int j, k,")
![l = k+1; if (!fl) for (j = 1+1; j a[j]) { x = a [j-1]; a[j-l] = a[j]; a[j]](/img/thumbs/b3abe262a260eb6dce1d619cafc327ab-800x.jpg "Задача сортировки Програмирование на языке высокого уровня Т.Г.Чурина l = k+1; if (!fl) for (j = 1+1; j a[j]) {")
![void quicksort(key a[], int 1, int r) { key x, w; int i, j; i =](/img/thumbs/dfa2f1b6471e322ad2184e83c8c4c5a4-800x.jpg "Задача сортировки Програмирование на языке высокого уровня Т.Г.Чурина void quicksort(key a[], int 1, int r) { key x, w;")
