Билет 37

1. Улучшенные методы сортировки. Сортировка Шелла, Хоара, улучшенная сортировка выбором. Сортировка с помощью дерева.

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

Сортировку можно разбить на 2 вида:

1. Простые методы сортировки – выбором, пузырьковая, вставками.

2. Улучшенные методы сортировки – Шелла, Хоара.

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

Проход 1 f d a c b e

\___\___\___/ / /

\___\_____/ / /

\_______/

Проход 2 c b a f d e

\___\___|___|___/ /

\______|______/

Проход 3 a b c d e f

|___|___|___|___|___|

Результат a b c d e f

Конкретная последовательность шагов может быть и другой. Единственное правило состоит в том, чтобы последний шаг был равен 1. Например, такая последовательность: 9, 5, 3, 2, 1

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

void shell(char *items, int count)

{

register int i, j, gap, k;

char x, a[5];

a[0]=9; a[1]=5; a[2]=3; a[3]=2; a[4]=1;

for(k=0; k < 5; k++) {

gap = a[k];

for(i=gap; i < count; ++i) {

x = items[i];

for(j=i-gap; (x < items[j]) && (j >= 0); j=j-gap)

items[j+gap] = items[j];

items[j+gap] = x;

}

}

}

Внутренний цикл for имеет два условия проверки. Очевидно, что сравнение x<items[j] необходимо для процесса сортировки. Выражение j>=0 предотвращает выход за границу массива items. Эти дополнительные проверки в некоторой степени понижают производительность сортировки Шелла.

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

Быстрая сортировка Хоара – в ее основе лежит сортировка обменами.

Быстрая сортировка построена на идее деления. Общая процедура заключается в том, чтобы выбрать некоторое значение, называемое компарандом(операнд в операции сравнения. Иногда называется также основой и критерием разбиения) ,а затем разбить массив на две части. Все элементы, большие или равные компаранду, перемещаются на одну сторону, а меньшие — на другую. Потом этот процесс повторяется для каждой части до тех пор, пока массив не будет отсортирован. Например, если исходный массив состоит из символов f e d a c b, а в качестве компаранда используется символ d, первый проход быстрой сортировки переупорядочит массив следующим образом:

Начало f e d a c b

Проход 1 b c a d e f

Затем сортировка повторяется для обеих половин массива, то есть b с а и d e f. Как вы видите, этот процесс по своей сути рекурсивный, и, действительно, в чистом виде быстрая сортировка реализуется как рекурсивная функция.

Значение компаранда можно выбирать двумя способами — случайным образом либо усреднив небольшое количество значений из массива. Для оптимальной сортировки необходимо выбирать значение, которое расположено точно в середине диапазона всех значений. Однако для большинства наборов данных это сделать непросто. В худшем случае выбранное значение оказывается одним из крайних. Тем не менее, даже в этом случае быстрая сортировка работает правильно. В приведенной ниже версии быстрой сортировки в качестве компаранда выбирается средний элемент массива.

/* Функция, фызывающая функцию быстрой сортировки. */

void quick(char *items, int count)

{

qs(items, 0, count-1);

}

/* Быстрая сортировка. */

void qs(char *items, int left, int right)

{

register int i, j;

char x, y;

i = left; j = right;

x = items[(left+right)/2]; /* выбор компаранда */

do {

while((items[i] < x) && (i < right)) i++;

while((x < items[j]) && (j > left)) j--;

if(i <= j) {

y = items[i];

items[i] = items[j];

items[j] = y;

i++; j--;

}

} while(i <= j);

if(left < j) qs(items, left, j);

if(i < right) qs(items, i, right);

}

В этой версии функция quick() готовит вызов главной сортирующей функции qs(). Это обеспечивает общий интерфейс с параметрами items и count, но несущественно, так как можно вызывать непосредственно функцию qs() с тремя аргументами.

Необходимо упомянуть об одном особенно проблематичном аспекте быстрой сортировки. Если значение компаранда в каждом делении равно наибольшему значению, быстрая сортировка становится "медленной сортировкой" со временем выполнения порядка n2. Поэтому внимательно выбирайте метод определения компаранда. Этот метод часто определяется природой сортируемых данных. Например, в очень больших списках почтовой рассылки, в которых сортировка происходит по почтовому индексу, выбор прост, потому что почтовые индексы довольно равномерно распределены — компаранд можно определить с помощью простой алгебраической функции. Однако в других базах данных зачастую лучшим выбором является случайное значение. Популярный и довольно эффективный метод — выбрать три элемента из сортируемой части массива и взять в качестве компаранда значение, расположенное между двумя другими.