24. Сортировка с помощью вставки (включения)

Метод заключается в следующем. Сначала упорядочиваются элементы mas[0] и mas[1] исходного массива (они меняются местами, если только mas[0] > mas[1]). Далее в это упорядоченное двухэлементное множество вставляется элемент mas[2], перемещаясь справа налево по методу пузырька в то положение, которое образует упорядоченную тройку элементов. Затем аналогичным образом добавляется элемент mas[3], образуя упорядоченную четверку элементов и т.д. Эта операция повторяется для каждого из оставшихся элементов массива, расширяя текущее упорядоченное подмножество элементов до тех пор, пока оно не будет содержать в себе все элементы исходного массива. В результате данные содержащиеся в массиве, окажутся упорядоченными. Усовершенствованный метод пузырька позволяет сократить число по парных сравнений и перестановок элементов сортируемого массива.

void vstavka(int *arr,int size){

int i,x;

for(i=1;i<size;i++)

for(x=i;;x--)

if(arr[x]<arr[x-1]) perestanovka(&arr[x],&arr[x-1]);

else break; }

Хорошим показателем такой сортировки является весьма естественное поведение: почти отсортированный массив будет досортирован очень быстро. Это, вместе с устойчивостью алгоритма, делает метод хорошим выбором в соответствующих ситуациях.

25. Сортировка с помощью выделения (прямого выбора)

1. Выбирается элемент с наименьшим ключом.

2. Он меняется местами с первым элементом a₁.

3. Затем процесс повторяется с оставшимися n-1 элементами, n-2 элементами и т.д. до тех пор, пока не останется один, самый большой элемент.

void min_znach(int *arr,int size) {

int i,kol,min,x=0;

for(kol=0;kol<size;kol++) {

min=arr[kol];

for(i=kol+1;i<size;i++) {

if(arr[i]<min)

{

min=arr[i];

x=i;

}

}

if(min!=arr[kol])

perestanovka(&arr[kol],&arr[x]);

}

}

26. Сортировка с помощью обменов (пузырьковая сортировка)

Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами. После нулевого прохода по массиву "вверху" оказывается самый "легкий" элемент - отсюда аналогия с пузырьком. Следующий проход делается до второго сверху элемента, таким образом, второй по величине элемент поднимается на правильную позицию. Делаем проходы по все уменьшающейся нижней части массива до тех пор, пока в ней не останется только один элемент. На этом сортировка заканчивается.

void puz(int *arr, int size){

int i,kol,x=size-1;

for(kol=0;kol<size;kol++)

for(i=0;i<size-1;i++)

if(arr[i]>arr[i+1]) perestanovka(&arr[i],&arr[i+1]);

}

Алгоритм пузырьковой сортировки можно улучшить, если заметить некоторые особенности его поведения для конкретных примеров. Так, для примера 67 67 67 94 94 94 94 94, последние проходы работают вхолостую – все элементы уже отсортированы. Очевидный прием улучшения этого алгоритма – запоминать, были ли перестановки в процессе некоторого прохода, и если нет – заканчивать работу алгоритма. Это улучшение можно опять же улучшить, если запоминать не только сам факт обмена, но и положение (индекс) последнего обмена. Ясно, что все пары соседних элементов выше этого индекса k уже находятся в желаемом порядке. Поэтому просмотры можно заканчивать на этом индексе, а не идти до заранее определенного нижнего предела для i.

27. Шейкерная сортировка Пример

Анализируя пузырьковую сортировку можно заметить некоторую асимметрию: всплывает пузырек сразу, за один проход, а тонет очень медленно - за один проход на одну позицию. Отсюда и возникает идея третьего улучшения алгоритма: чередовать направление последовательных просмотров. Получающийся при этом алгоритм называется «шейкерной» сортировкой (ShakerSort).

28. Сортировка Шелла

В 1959 году Шеллом было предложено усовершенствование сортировки с помощью прямого включения. На начальном этапе реализуется по парное сравнение, и если требуется, обмен значениями далеко отстоящих друг от друга элементов массива. Интервал между сравниваемыми элементами (step) постепенно уменьшается до единицы, что приводит к перестановке соседних элементов на последних этапах сортировки (если это необходимо). Начальный шаг сортировки принимается равным N/2, т.е. половине длины массива, и после каждого прохода он будет уменьшаться в два раза. Проход с тем же шагом повторяется, если была выполнена хотя бы одна перестановка элементов. Таким образом, после каждого этапа отстоящие на step элементы оказываются попарно упорядоченными. Единственной характеристикой сортировки Шелла является приращение (инкремент) - расстояние между сортируемыми элементами, в зависимости от прохода. В конце приращение всегда равно единице - метод завершается обычной сортировкой вставками, но именно последовательность приращений определяет рост эффективности.

Однако гораздо лучший вариант инкрементов предложил Р.Седжвик.

При использовании таких приращений среднее количество операций: O(n7/6), в худшем случае - порядка O(n4/3). Обратим внимание на то, что последовательность вычисляется в порядке, противоположном используемому: inc[0] = 1, inc[1] = 5, ... Поэтому массив приращений inc вычисляется перед запуском собственно сортировки. При использовании формулы Седжвика следует остановиться на значении inc[s-1], если 3*inc[s] > size.

int increment(long* inc, long size) {

int p1, p2, p3, s;

p1 = p2 = p3 = 1;

s = -1;

do {

if (++s % 2) inc[s] = 8*p1 - 6*p2 + 1;

else {

inc[s] = 9*p1 - 9*p3 + 1;

p2 *= 2;

p3 *= 2; }

p1 *= 2;

} while(3*inc[s] < size);

return s > 0 ? --s : 0;}

void shellSort(long* a, long size) {

long inc, i, j, seq[40];

int s;// вычисление последовательности приращений

s = increment(seq, size);

while (s >= 0) { // сортировка вставками с инкрементами inc[]

inc = seq[s--];

for (i = inc; i < size; i++) {

long temp = a[i];

for (j = i-inc; (j >= 0) && (a[j] > temp); j -= inc) a[j+inc] = a[j];

a[j+inc] = temp;}}}

29. Сравнение рассмотренных сортировок

Мы рассмотрели алгоритмы сортировки, имеющие либо квадратичный, либо субквадратичный порядок сложности. Изображенный ниже график иллюстрирует разницу в эффективности изученных алгоритмов.

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

Д ерево с базовым типом Т – это либо: пустое дерево; некоторая вершина типа Т с конечным числом связанных с ней отдельных деревьев с базовым типом Т, называемых поддеревьями.

Упорядоченное дерево – это дерево, у которого ребра (ветви, дуги), исходящие из каждой вершины упорядочены.

Вершина y, находящаяся непосредственно ниже вершины x, называется непосредственным потомком x; и, наоборот, вершину x называют непосредственным предком y. Употребляют также термины «родитель» и «сын». Все элементы дерева также называют «узлами». Считается, что корень дерева находится на уровне 0. Максимальный уровень какой-либо из вершин дерева называется его высотой.

Итак, назовем пирамидой (Heap) бинарное дерево высоты k, в котором

• в се узлы имеют глубину k или k-1 - дерево сбалансированное.

• при этом уровень k-1 полностью заполнен, а уровень k заполнен слева направо, т.е форма пирамиды имеет приблизительно такой вид.

• выполняется "свойство пирамиды": каждый элемент меньше, либо равен родителю.

К ак хранить пирамиду? Наименее хлопотно - поместить ее в массив.

Соответствие между геометрической структурой пирамиды как дерева и массивом устанавливается по следующей схеме в a[0] хранится корень дерева; левый и правый сыновья элемента a[i] хранятся, соответственно, в a[2i+1] и a[2i+2]. Таким образом, для массива, хранящего в себе пирамиду, выполняется следующее характеристическое свойство: a[i] >= a[2i+1] и a[i] >= a[2i+2].