2. Класс выбора - из неупордяченной последовательности тем или иным образом выбирается элемент, и помещается (просто добавляется в выходные последовательность, которая становится упорядоченной)

3. Класс вставки - выбирается очередной элемент из неупорядоченной последовательности, для которого ищется подходящее место в упорядоченности, после чего этот элемент вставляется в нужное место в упорядоченную последовательность.

4. Класс сортировки подсчетом - основан на том, что свое окончательное место упорядоченной последовательности с номером j элемент занимает в том и только том случае, если в этой последовательности оказалось ровно j-1 элемент, меньшей (сортировка по возрастанию), или по больших элемент, то есть для упорядочивания, а точнее нахождения места в упорядоченной последовательности для элемента достаточно подсчитать количество меньших ключей.

5. Класс сортировок слиянием, основан на объединении двух или более упорядоченных последовательностей, из которых без возвратов можно получить новую упорядоченную последовательность, включающую элементы объединение. применяется во внешней сортировке.

1 - пузырек, алгоритм Хоару (quicksort)

2 - простой выбор (min/max), пирамидальная сортировка

3 - простая вставка, алгоритм Шелла, бинарная

4 - сравнение и подсчет, распределяющий обмена (часть карманной сортировки)

5 - слияние: естественное двухпутевое слияние, фиксированное двухпутевое слияние

Постановка задачи сортировки

Пусть имеется N элементов R1, R2, …, Rn - записи, т.к. для удобства в каждом из этих элементов одно поле ключевое, а вторые поля – сопутствующие, или информационные.

R1, R2, …, Rn

Важно: с точки зрения программирования доступ к полю k R[i].k тоже самое, что k[i], но R[i] ↔ R[j]

Ключ – это поле, которое управляет процессом сортировки, причем на множестве ключей (вспомним, что ключевое поле необязательно численное ). Определим отношение порядка “>” таким образом, чтобы для любых трех значений ключей a,b,c выполнялись следующие законы:

1. Если, а > b и b>c то a>c – закон транзитивности

2. Справедливо одно и только одно из соотношений либо a<b либо a>b либо a=b закон трихотомии

Может быть доказано, что любое множество (ключей), на котором определены отношение порядка меньше либо больше используя законы 1 и 2, может быть упорядочено, так как эти законы определяют математическое понятие линейного упорядочивания, или по-другому – совершенно упорядочение.

Тогда задача сортировки заключается, чтобы найти такую перестановку записей, чтобы ключи k1, k2, ..., kn расположились в неубывающем порядке.

Методы сортировок

Методы сортировок описывают способ реализации перестановки записей (ключей):

1. Если записи небольшие, то можно осуществить их физическое переразмещение в памяти

2. Создать специальную таблицу, описывающую перестановку элементов, и обеспечивающую доступ к элементам, не двигая их так, чтобы в соответствии с упорядоченностью ключей. Перестановка P[i]=j массив перестановок P означает или реализует следующее: i-тая запись займет в ходе перестановки j-тое место. Ki (i=1..n)  Result[p[j]] = R[j]

3. Если записи длинные, а ключи короткие, то для повышения скорости сортировки ключи можно вынести в таблицу ключей – сортировка ключей

4. Если сопутствующая информация и/или ключи занимают много байт памяти, то можно составить новую таблицу адресов, которая указывает на записи. Создаем ссылки и переразмещаем

5. В каждую запись добавляется специальное поле связи, образующее связанный список. Тогда сортировка заключается в изменении этих полей связи так (не переразмещая сами записи), чтобы линейный порядок обхода образовывал упорядоченную последовательность

Типы сортировок

Типы сортировок: внутренняя и внешняя.

Внутренняя предполагает хранение всех записей (исходных результирующих и т.д.) в оперативной памяти, причем в любой момент времени доступен любой элемент.

Внешняя сортировка – данные хранятся на внешнем медленном носителе, а в памяти хранится их подмножество, после операции, над которым данные помещаются обратно на внешнее ЗУ и считывается следующая порция данных.

Критерии оценки сортировок

1. Сравнить по количеству выполняемых операций.

2. Количество сравнений ключей

Заметим, что максимально возможное количество сравнений происходит в случае, когда каждый ключ сравнивается с каждым другим (попарное сравнение) N сравнений. Однако в бинарном поиске, где тоже сравнение, число сравнение равно log₂ N. Так как нам надо расположить N ключей, то можно предположить, что трудоемкость сортировки (при условии времени доступа за O(1) ограниченным диапазоном).

N log₂ N ≤ Ө сортировка ≤ N²

При этом наихудшее время N² имеют алгоритмы, которые нерационально сравнивать. К таким алгоритмам относят пузырек, простую вставку, простой выбор.

Простые схемы сортировок

F(n)= ∑_i=1ⁿ ∑_j=1ⁿ 1=1+2+3+....+n = n/2(n+-1)=(n²+-n)/2

0(f(n))=max { n²/2; n/2 } = n²

Заметим, что наибольшее время будет затрачено в том случае, если кроме сравнений (попарных) будет выполнена максимальное количество обменов (сдвигов) записей. Это произойдет в случае пузырька, если самый минимальный элемент занял самое крайнее правое положение , а заодно итерацию внешнего цикла он смещается максимум на одну позицию влево. Улучшится ли время сортировки, если элементы сдвигать не на одну позицию, «скачками» перепрыгивая некоторые позиции, исключая промежуточные переприсваивания, сдвиги и т.д.

Простая вставка

В этой сортировке массив делится на 2 части: отсортированную и неотсортированную. На каждом шаге берется очередной элемент из неотсортированной части и «включается» в отсортированную часть массива.

Пусть отсортировано начало массива A[1], A[2], ..., A[i-1], а остаток массива A[i], ...,A[n] содержит неотсортированную часть. На очередном шаге будем включать элемент A[i] в отсортированную часть, ставя его на соответствующее место. При этом придется сдвинуть часть элементов, больших A[i], (если таковые есть) на одну позицию правее, чтобы освободить место для элемента A[i]. Но при сдвиге будет потеряно само значение A[i], поскольку в эту позицию запишется первый (самый правый – с самым большим индексом) сдвигаемый элемент. Поэтому прежде чем производить сдвиг элементов необходимо сохранить значение A[i] в промежуточной переменной. Так как массив из одного элемента можно считать отсортированным, начнем с i=2.

Этот алгоритм также имеет максимальную и среднюю временную сложности, пропорциональные O(n²), но в случае исходно отсортированного массива внутренний цикл не будет выполняться ни разу, поэтому метод имеет временную сложность T_min(n), пропорциональную O(n). Алгоритм сохраняет порядок элементов с одинаковыми значениями.

Алгоритм Шелла

Подобен пузырьку, в котором сравнение и обмены происходят на некоторой дистанции в зависимости от значения переменной A, называемой шагом сортировки. Метод Шелла относится к классу вставок, в котором происходит обмен записи.

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

7 5 13 6 7 10 4 7 2 (R1;R6);(R2;R7);(R3;R8)…(Ri;Ri+L)

7 4 7 2 7 10 5 13 6 (R1;R4 ;R7);(R2;R5;R8);(R3;R6;R9)

2 4 6 5 7 7 7 13 10

послед. Шаг h=1

В алгоритме Шелла неявно образуются группы из элементов, которые отстоят друг от друга на h позиций, каждая такая группа сортируется простой вставкой, после чего значение шага надо изменить.

Теорема: K-упорядоченная последовательность после h сортировки будет одновременно kh упорядочена

Самая простая последовательность шагов образуется

h={ ½; N/2 * ½; N/8; N/16; ....; 1 }, где i номер итерации

hi=(H_i-1)/2

h={16,8,4,2,1}

Что приводит к тому, что элементы в четных и нечетных позициях не взаимодействуют друг с другом , вплоть до последней итерации на которую придется максимальное количество обменов – наихудший случай выбора шагов. А наилучший – когда происходит наибольшее перемешивание групп от раза к разу.

Это достигается, если шаги взаимно простые h={13,11,7,5,3,1}. Вообще, последовательность может быть любая, главное чтоб h=1.

Например у Кнута: h_i=3_h-1+1

При этом I максимально i – max : H_imax+2 > N

h>N

Трудоемкость Шелла О(N^1,667)

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

Быстрая сортировка Хоару

В методе пузырька последовательность сравнений предопределена и на следующем шаге мы не используем ту информацию, которую могли бы извлечь из сравнений этого шага.

Рассмотрим стратегию, которая это использует.

2 6 7 10 8 1 5 7

1 2

2 6

|

5 6 7 8 10

1 2 5 6 7 8 10

i   j

i=left =1 j=right=8

начинаем сравнивать i j элементы.

Если левый i-тый элемент оказался неупорядочен относительно правого, т.е. j – они меняются местами. После обмена начинает увеличиться i или уменьшаться j, та, которая не изменялась до обмена., а другая замораживается до следующего обмена. Стадия завершается в случае j=i . Рассмотрим эту ситуацию.

В этот момент слева от этой позиции отсутствуют элементы, превышающие, а справа отсутствуют элементы меньшие. Что в каждом сравнении использовался первый элемент, который назовем опорным. Опорный элемент занял свой окончательное положение в сортируемой последовательности (т.к. слева нету элементов больших, а справа - меньших). К каждой из двух под последовательностей (левую и правую относительно опорного) можно применить ту ж процедуру. Рекурсивно применим данную процедуру до тех пор, пока right-left > 2

Procedure quicksort(left,right:integer);

Var j,i:integer;

Begin i:=left; J:=right;

Repeat

While (i<j) K[i] < K[j] do j--;

If i<j then R[i]   R[j];

If i<j then

While(i<j) and (k[i] < k[j] ) do i++;

If i<j then r[i]   R[j];

Until i=j;

If (i-left) > 1 then quicksort(left,i-1);

If (right-j) > 1 then quicksort(i+1,right);

End;