Задача сортировки Програмирование на языке высокого уровня Т. Г. Чурина




НазваниеЗадача сортировки Програмирование на языке высокого уровня Т. Г. Чурина
Дата конвертации01.07.2013
Размер445 b.
ТипЗадача


Задача сортировки Програмирование на языке высокого уровня Т.Г.Чурина


Методы сортировки обычно разделяют на две

категории: внутреннюю сортировку массивов и внешнюю — сортировку файлов.

Задача сортировки состоит в том, чтобы

упорядочить N объектов a1, ... , аN:

переставить их в такой последовательности аp1,..., apN,

чтобы их ключи расположились в неубывающем

порядке

kp1 < kp2 < ... < kpN.

Сортировка называется устойчивой,

если она удовлетворяет условию, согласно

которому записи с одинаковыми ключами

остаются в прежнем порядке:

kРi = kРj и i < j, то pi < pj

При устойчивой сортировке относительный

порядок элементов с одинаковыми ключами

не меняется.

Методы сортировки можно разбить на

несколько основных классов в зависимости

от лежащего в их основе приема сортировки:

— включения;

— выбора;

— обмена;

— подсчета;

— разделения;

— слияния.

Разделим условно все элементы массива

на две последовательности: входную ai, ... , аN

и готовую последовательность a1, ... , аi-1

элементы которой уже отсортированы.

В алгоритмах, основанных на методе включения, на

каждом i-м шаге i-й элемент входной

последовательности вставляется в подходящее

место готовой последовательности.

Сортировка простыми включениями наиболее очевидна.

Пусть 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.

Процесс сортировки включениями покажем на примере

последовательности, состоящей из восьми ключей:

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 |





Сортировка бинарными включениями

Для нахождения места для i-го элемента можно

использовать метод бинарного поиска элемента в

отсортированном массиве, в котором на i-ом шаге

выполняется ~ log2i сравнений.

Поэтому всего будет произведено ~ Nlog2N сравнений.

Но количество пересылок в этом методе не изменится.

Сортировка включениями с убывающим шагом. Метод Шелла

Хоар, Флойд, Шелл: для алгоритмов сортировки,

перемещающих в последовательности запись вправо или

влево только на одну позицию, среднее время работы будет

в лучшем случае пропорционально N2.

Хотелось бы, чтобы записи перемещались «большими

скачками, а не короткими шажками».

Д. Шелл предложил в 1959 г. метод, названный

сортировкой с убывающим шагом.







Итак:





Чтобы выбрать некоторую хорошую последовательность

шагов сортировки, нужно проанализировать время работы

как функцию от этих шагов.

До сих пор не удалось найти наилучшую возможную

последовательность шагов 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



Утверждение.

Утверждение.

Если 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

Сортировка простым выбором

Методы сортировки посредством выбора основаны на идее

многократного выбора.

На i-м шаге выбирается наименьший элемент из входной

последовательности ai, ..., an и меняется местами с ai-м.

Таким образом, после шага i на первом месте во входной

последовательности будет находиться наименьший элемент.

Затем этот элемент перемещается из входной в готовую

последовательность.

Процесс выбора наименьшего элемента из входной

последовательности повторяется до тех пор, пока в ней

останется только один элемент.

Проиллюстрируем этот метод на той же последовательности

Проиллюстрируем этот метод на той же последовательности

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





Анализ

Число Сi сравнений на i-м шаге не зависит от начального порядка

элементов.

На первом шаге первый элемент сравнивается с остальными N - 1

элементами, на втором шаге число сравнений будет — N - 2 и т. д.

Поэтому число сравнений есть

С = (N – 1) + (N – 2) + ... + 1 = N * (N - 1)/2

Максимальное число пересылок Мmах = N -1 так как на каждом

проходе выполняется обмен найденного минимального элемента с i-м.

Вероятность того, что i-й элемент уже стоит на месте, невелика, поэтому

средняя оценка М близка к максимальной.



Пирамидальная сортировка

При сортировке методом простого выбора на каждом шаге

Выполняется линейный поиск минимального элемента.

Линейная сложность этого поиска делает сложность всей

сортировки квадратичной.

Возможно ли найти минимальный элемент за время лучшее

линейного?

Оказывается, что это возможно, если использовать на

каждом следующем шаге информацию о взаимных

отношениях элементов, накопленную на предыдущих шагах.



Пусть дана последовательность h1, ..., hn.

Пусть дана последовательность h1, ..., hn.

Элемент hi образует пирамиду в этой последовательности,

если выполнены следующие условия:
  • — если 2  in, то hi h2i и h2i образует пирамиду;

  • — если 2  i + 1 ≤ n, то hi h2i+1 и h2i+1 образует пирамиду.

Элементы hn/2+1, ..., hn всегда образуют тривиальные

пирамиды, поскольку для них приведенные условия имеют

ложные посылки.

Если элемент h1 образует пирамиду, то и каждый элемент

Если элемент h1 образует пирамиду, то и каждый элемент

последовательности образует пирамиду.

В этом случае будем говорить, что вся последовательность

является полной пирамидой.

Полная пирамида может быть изображена в виде корневого

бинарного дерева, в котором элементы h2i и h2i+1 являются

сыновьями элемента hi.

Элемент в любом узле численно не меньше всех своих потомков, а

вершина полной пирамиды h1 содержит максимальный элемент всей

последовательности.







Идея метода пирамидальной сортировки:

Идея метода пирамидальной сортировки:

1. Подготовка к сортировке: входная неупорядоченная последовательность перестраивается в пирамиду.

2. Сортировка: входная и готовая последовательности хранятся в одном массиве, причем готовая последовательность формируется в хвосте массива, а входная остается в начале массива.

Основой реализации метода является следующая процедура

Основой реализации метода является следующая процедура

просеивания.

Пусть в последовательности h1, ..., hn элементы hi+1, ..., hn

уже образуют пирамиды.

Требуется перестроить последовательность так, чтобы

пирамиду образовывал элемент hi.



На каждой итерации цикла наибольший из трех элементов

На каждой итерации цикла наибольший из трех элементов

hi, h2i и h2i+1 путем обмена оказывается в корне текущего

поддерева, что обеспечивает истинность условий пирамиды

в этом корне.

Если при этом изменяется корень левого или правого

поддерева, то просеивание продолжается для него.



Сортировка

Сортировка

На каждом шаге сортировки первый элемент массива, т. е.

максимальный элемент пирамиды, переносится в начало

готовой последовательности путем обмена с последним

элементом пирамиды, занимающим его место.

Затем остаток входной последовательности вновь

перестраивается в пирамиду, обеспечивая корректность

следующего шага.

В начале i-го шага элементы a1, .., ai, по предположению,

В начале i-го шага элементы a1, .., ai, по предположению,

хранят входную последовательность как пирамиду, а

ai+1, .., aN – упорядоченную по возрастанию готовую

последовательность (изначально пустую).

На i-м шаге текущий максимальный элемент пирамиды а1

Обменивается с аi, становясь началом новой готовой

последовательности, где он будет новым минимальным

элементом. Входная последовательность (пирамида) при

этом претерпевает два изменения:

— она теряет последний элемент, что не нарушает условий пирамиды ни в одном узле;

— ее первый элемент становится произвольным, что может нарушать условие пирамиды только в первом узле.

Таким образом, для новой входной последовательности

Таким образом, для новой входной последовательности

a1, ..., ai-1

условия пирамиды выполнены для всех элементов,

кроме первого.

Применение процедуры просеивания к a1 восстанавливает

полную пирамиду в a1, ..., ai-1, что обеспечивает условия

осуществимости следующего шага.



void Sift(key а[], int i, int n) {

void 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;

}

}

void heap_sort(key a[], int N) {

void 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); /*просеивание*/

}

}

Анализ

Число итераций цикла в процедуре просеивания не

превосходит высоты пирамиды.

Высота полного бинарного дерева из N узлов, каковым

является пирамида, равна [log2 N].

Просеивание имеет логарифмическую сложность.

Итоговая сложность пирамидальной сортировки ~N  log2 N.

Наилучший случай – обратное упорядочение входной

Последовательности.

Сортировка простым обменом

Метод основан на принципе сравнения и обмена пар соседних

элементов. На первом шаге сравним последний и предпоследний

элементы, если они не упорядочены, поменяем их местами. Далее

проделаем то же со вторым и третьим элементами от конца массива,

третьим и четвертым и т. д. до первого и второго с начала массива.

При выполнении этой последовательности операций меньшие элементы

в каждой паре продвинутся влево, наименьший займет первое место в

массиве.

Повторим этот же процесс от N-го до 2-го элемента, потом от N-го до 3-го

и т. д.

i-й проход по массиву приводит к «всплыванию» наименьшего элемента

из входной последовательности на i-e место в готовую

последовательность.

Метод пузырька

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;

}

}

Анализ

Количество сравнений Сi на i - мпроходе равно N - i,

что приводит к уже известному выражению для С:

С = (N - 1) + (N - 2) + ... + 1 = N∙(N - 1)/2

Минимальное количество пересылок Mmin= 0,

если массив уже упорядочен,

максимальное Мтах = С, если массив упорядочен по

убыванию.

Шейкер-сортировка

1) Нередко случается, что последние проходы сортировки

простым обменом работают «вхолостую», так как элементы

уже упорядочены.

Один из способов улучшения алгоритма сортировки

пузырьком состоит в том, чтобы запомнить, производился ли

на очередном проходе какой-либо обмен.

Если ни одного обмена не было, то алгоритм может

закончить работу.

2) Асимметрия метода: один неправильно расположенный

2) Асимметрия метода: один неправильно расположенный

«пузырек» на «тяжелом» конце почти отсортированного

массива «всплывет» на место за один проход:

Поэтому еще одно улучшение алгоритма состоит в

Поэтому еще одно улучшение алгоритма состоит в

том, чтобы чередовать направление проходов.

На нечетном проходе будем сравнивать пары от

конца массива к началу, в результате «легкие»

элементы будут продвигаться к началу массива.

На четных проходах будем сравнивать пары от

начала массива к концу, в результате «тяжелые»

элементы будут продвигаться к концу массива.

Левая и правая границы продвижения на каждом

проходе будут также поочередно сдвигаться на 1.

void shaker_sort (key a[], int N) {

void 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; /* позиция пузырька */

}

}

l = k+1;

l = k+1;

if (!fl)

for (j = 1+1; j<=r; 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}

Анализ

Стin= N –1. Кнут показал, что среднее число сравнений

пропорционально N2 - N.

Но все предложенные улучшения не влияют на число

обменов.

В самом деле, каждый обмен уменьшает число инверсий в

массиве на 1, следовательно, при любом алгоритме,

основанном на обмене пар соседних элементов, число

необходимых перестановок одинаково и равно числу

инверсий в массиве.

Cортировка обменом и ее улучшенная сортировка хуже,

чем сортировка включениями и выбором.

Шейкер-сортировку выгодно использовать тогда, когда массив

почти упорядочен.

Сортировка с разделением. Быстрая сортировка Ч. Э. Р. Хоар

Метод сортировки, при котором обмениваются местами

пары несоседних элементов, а задача сортировки

последовательности рекурсивно сводится к задачам

сортировки ее меньших частей.

Допустим сначала, что мы уже переупорядочили

Допустим сначала, что мы уже переупорядочили

некоторым образом элементы входной

последовательности, после чего оказалось

возможным разделить ее на две непустые части по

границе некоторого индекса т:

левую (индексы 1...т) и

правую (индексы т+1...N);

причем все элементы левой части не превосходят всех

элементов правой части:

 i, j: 1  i m и m < j N выполнено: аiaj. (14)

Индекс т назовем медианой.

Индекс т назовем медианой.

Отсортируем любым методом обмена отдельно левую часть,

не затрагивая элементов правой части, а затем отдельно

правую, не трогая левой.

При этом обмениваться могут только пары элементов,

находящиеся в одной части, поэтому никакой обмен не

нарушает свойство (14).

Значит, оно будет верно и для результирующей

последовательности, которая в силу этого оказывается

упорядоченной в целом.

СортировкаРазделением (l, r)

СортировкаРазделением (l, r)

/* l, r – границы сортируемой подпоследовательности */

/* Разделение */

привести подпоследовательность аl ,…, аr к условию (14)

и определить медиану m;

/* Рекурсивный спуск */

если l < m то /* части длины 0 и 1 не сортируем */

СортировкаРазделением (l, m);

если m + 1 < m то /* части длины 0 и 1 не сортируем */

СортировкаРазделением (m + 1, r);

конец

Получается, что в процессе дробления исходной задачи на подзадачи мы

Получается, что в процессе дробления исходной задачи на подзадачи мы

приходим к тривиальным подзадачам:

cортировке последовательностей длины 0 и 1.

Не приходится ничего делать и для слияния решений подзадач в

решение исходной задачи во время возврата из рекурсии:

упорядоченные последовательности образуются сами собой по мере

упорядочения их частей.

Где же тогда фактически выполняется сортировка?

На фазе разделения, иллюстрируя, как хорошая подготовка условий для

решения зачастую уже и дает решение!

В качестве критерия разделения нам понадобится так называемый

В качестве критерия разделения нам понадобится так называемый

пилотируемый элемент х.

В классической версии алгоритма в качестве x выбирается произвольный

элемент сортируемой последовательности: первый, последний,

расположенный в середине или иначе.

Влияние его выбора на эффективность алогритма мы обсудим ниже.

В процессе разделения мы соберем в левой части последовательности

все элементы аiх, а в правой — все элементы aj  x.

Условие (14) при этом будет выполнено даже при возможном наличии

одинаковых элементов x в обеих частях.

Введем два бегущих индекса-указателя i и j, которые делят

Введем два бегущих индекса-указателя i и j, которые делят

разделяемую подпоследовательность на три участка:

левый (al ... ai-1),

правый (aj+1 ... ar),

средний (ai ... aj).

В левом и правом участках будут накапливаться элементы

левой и правой частей, подлежащих затем рекурсивной

сортировке, а в среднем находятся остальные, еще не

распределенные элементы.

Процесс разделения:

Процесс разделения:

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

Циклы по встречным индексам переносят из средней части в левую или

Циклы по встречным индексам переносят из средней части в левую или

правую элементы, строго меньшие или большие х, которые могут быть

добавлены в эти части без перестановки.

После их выполнения процесс разделения либо заканчивается

(если i  j), либо пара ai и aj образует инверсию.

В последнем случае их следует обменять и включить в левую и правую

части.

Вот здесь и происходят упорядочивающие обмены с уменьшением числа

инверсий в последовательности!

Проверка того, что бегущие индексы не выходят за границы l...r, строго

Проверка того, что бегущие индексы не выходят за границы l...r, строго

говоря, необходима, но фактически не нужна:

на первом проходе выход за границы немозможен, так как в массиве

есть сам элемент х и оба цикла остановятся на нем.

В конце же первого прохода происходит обмен элементов и обе части

становятся не пусты, что гарантирует остановку циклов по встречным

индексам в пределах интервала l...r и на следующих проходах.

Цикл оканчивается при i j.

Цикл оканчивается при i j.

Однако нам еще надо определить медиану.

Определенные границы левой части – l...i – 1,

правой – j + 1...r, однако интервал j + 1...i – 1 может быть не

вырожден и заполнен элементами х (почему?).

Эти элементы останутся на своих местах в процессе

сортировки (почему?), поэтому их можно исключить из

левой и правой частей.

Окончательно границами левой части можно считать l...j,

а правой – i...r.





void quicksort(key a[], int 1, int r) {

void 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}

Анализ

Процессу разбиения подвергается весь массив,

следовательно выполняется N сравнений.

Число обменов?

Пусть после разделения х будет занимать в массиве

позицию k.

Число требующихся обменов равно числу элементов в левой

части массива (k - 1), умноженному на вероятность того, что

элемент нужно обменять.

Элемент обменивается, если он не меньше, чем х.

Вероятность этого равна (N - (k - 1))/N.

Просуммируем всевозможные варианты выбора медианы и

Просуммируем всевозможные варианты выбора медианы и

разделим эту сумму на N, в результате получим ожидаемое

число обменов:

Однако в худшем случае сортировка становится

Однако в худшем случае сортировка становится

«медленной».

Например, когда в качестве пилотируемого элемента всегда

выбирается наибольшее значение. Тогда в результате

разбиения в левой части оказывается N - 1 элемент,

т. е. массив разбивается на подмассивы из одного элемента

и из N - 1 элемента.

В этом случае вместо log2 N разбиений необходимо сделать

~ N разбиений.

В результате в худшем случае оценка оказывается ~ N2.

что гораздо хуже пирамидальной сортировки.

Сортировка методом подсчета

При сортировке подсчетом каждый элемент поочередно сравнивается

со всеми остальными и подсчитывается количество элементов,

которые меньше его. Это число (+1) определяет позицию элемента в

отсортированной последовательности при условии, что все элементы

различны.

Простейшая реализация этого метода требует дополнительного

массива, в котором накапливаются отсортированные элементы. Это

связано с тем, что в данном методе входная последовательность не

сокращается по мере обработки элементов.


Похожие:

Задача сортировки Програмирование на языке высокого уровня Т. Г. Чурина iconCортировка файлов Програмирование на языке высокого уровня Т. Г. Чурина Слияние последовательностей
Как только одна из последовательностей закончится, она исключается из рассмотрения
Задача сортировки Програмирование на языке высокого уровня Т. Г. Чурина iconПрограммирование на языке высокого уровня Для студентов очно-заочной формы обучения

Задача сортировки Програмирование на языке высокого уровня Т. Г. Чурина iconРазработка приложений на языке F# Андрей Терехов Microsoft Украина Немного истории
Сложность удается частично скрыть с помощью инструментов разработки (пример: языки высокого уровня)
Задача сортировки Програмирование на языке высокого уровня Т. Г. Чурина iconКафедры вс, к т. н. Поляков Артем Юрьевич Рассматриваемые вопросы Жизненный цикл программы и место отладки в нем
Программирование на языке высокого уровня раздел Отладка компьютерных программ
Задача сортировки Програмирование на языке высокого уровня Т. Г. Чурина iconКафедры вс, к т. н. Поляков Артем Юрьевич Рассматриваемые вопросы Синтаксис языка и способы его описания
Программирование на языке высокого уровня раздел Базовые конструкции и типы данных языка Си
Задача сортировки Програмирование на языке высокого уровня Т. Г. Чурина iconОтчет комиссии высокого уровня

Задача сортировки Програмирование на языке высокого уровня Т. Г. Чурина iconНеобходимость достижения учащимися высокого уровня социальной компетентности, обеспечивающего их личностное и профессиональное самоопределение

Задача сортировки Програмирование на языке высокого уровня Т. Г. Чурина iconТребование стандарта: Требование стандарта
А 36 заданий (из них 26-базового уровня и 10 повышенного) Часть в 8 заданий повышенного уровня Часть с 6 заданий ( 1-повышенного...
Задача сортировки Програмирование на языке высокого уровня Т. Г. Чурина iconЗамечено, что черенки листьев примыкают к
Строение форм представителей более высокого уровня животного мира также подчиняется закону чисел Фибоначчи
Задача сортировки Програмирование на языке высокого уровня Т. Г. Чурина icon«Автобест украина»
Мы предлагаем Вам свои услуги на выгодных для Вас условиях. 6 лет безупречной работы на рынке Украины, гарантия качества и высокого...
Разместите кнопку на своём сайте:
dok.opredelim.com


База данных защищена авторским правом ©dok.opredelim.com 2015
обратиться к администрации
dok.opredelim.com
Главная страница