Вопрос 24.1. Как реализуется сортировка Шелла и какова временная сложность этого метода сортировки

Этот метод назван по имени его изобретателя (D.L. Shell). Он построен на основе метода вставки с минимизацией промежуточных шагов. Сначала выполняется сортировка элементов, отстоящих друг от друга на три позиции. После этого сортируются элементы, отстоящие друг от друга на две позиции. Наконец выполняется сортировка смежных элементов.

Точная последовательность изменения приращений может изменяться. Единственным требованием остается равенство последнего приращения 1. Например, хорошо себя зарекомендовала последовательность 9, 5, 3, 2, 1, которая использована в нижеприведенном примере реализации алгоритма Шелла. Избегайте последовательностей степеней 2, поскольку математически строго доказано, что это снижает эффективность алгоритма (который, тем не менее, работает и в этом случае).

Время выполнения алгоритма пропорционально n^1,2 при сортировке n элементов. Это - существенный прогресс по сравнению с n-квадратичными методами сортировки. Однако метод быстрой сортировки еще более эффективен, чем метод Шелла.

void shell_sort(int *array, int n)

{

int i, j, k, gap, temp;

int a[] = {9, 5, 3, 2, 1};

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

gap = a[k];

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

temp = array[i];

for (j = i-gap; temp < array[j] && j >= 0; j-=gap)

array[j+gap] = array[j];

array[j+gap] = temp;

}

}

}

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

Вопрос 31.1. В чем состоит алгоритм "быстрой сортировки"

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

Если сортируемый файл целиком помещается в память (или целиком помещается в массив, то для него мы используем внутренние методы сортировки. Сортировка данных с ленты или диска называется внешней сортировкой.

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

Метод быстрой сортировки, разработанный и названный так его автором C.A.R. Hoare, по своим показателям превосходит все остальные алгоритмы, рассмотренные в данной работе. Более того, он считается наилучшим из разработанных на сегодняшний день универсальных алгоритмов. В его основе лежит метод перестановок.

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

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

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

Следует иметь в виду один аспект алгоритма быстрой сортировки. Если значение - компаранд для каждого из разделов является максимальным, то алгоритм становится очень медленным, со временем выполнения, пропорциональным квадрату количества элементов. Однако, как правило, этого не происходит.

void qs(int *array, int left, int right)

{

int i, j, comp, temp;

i = left; j = right;

comp = array[(left + right) / 2];

do {

while (array[i] < comp && i < right) i++;

while (array[j] > comp && j > left) j--;

if (i <= j) {

temp = array[i];

array[i] = array[j];

array[j] = temp;

i++; j--;

}

} while (i <= j);

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

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

}

void quick_sort(int *array, int n)

{

qs(array, 0, n-1);

}

Вопрос 38.1. Как может быть повышена эффективность реализации "быстрой сортировки"

Метод быстрой сортировки, разработанный и названный так его автором C.A.R. Hoare, по своим показателям превосходит все остальные алгоритмы, рассмотренные в данной работе. Более того, он считается наилучшим из разработанных на сегодняшний день универсальных алгоритмов. В его основе лежит метод перестановок.

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

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

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

Следует иметь в виду один аспект алгоритма быстрой сортировки. Если значение - компаранд для каждого из разделов является максимальным, то алгоритм становится очень медленным, со временем выполнения, пропорциональным квадрату количества элементов. Однако, как правило, этого не происходит.

Алгоритм быстрой сортировки можно реализовать не только посредством проце­дуры quicksort (см в предыдущем вопросе) так, чтобы среднее время выполнения равнялось О(п log п). Можно создать другие процедуры, реализующие этот алгоритм, которые будут иметь тот же порядок О(п log п) времени выполнения в среднем, но за счет меньшей константы пропорциональности в этой оценке будут работать несколько быстрее (напомним, что порядок времени выполнения, такой как О(п log п), определяется с точностью до константы пропорциональности). Эту константу можно уменьшить, если выбирать опорное (пограничное) значение таким, чтобы оно разбивало рассматриваемое в данный момент подмножество элементов на две примерно равные части. Можно надеяться, что при "правильном" выборе опорного значения выполнение алгоритма ускорится.

Например, можно с помощью датчика случайных чисел выбрать три элемента из подмножества и средний (по величине) из них назначить опорным значением. Можно также, задав некоторое число k, выбрать случайным образом (например, опять с по­мощью датчика случайных чисел) k элементов из подмножества, упорядочить их процедурой quicksort или посредством какой-либо простой сортировки и в качестве опорного значения взять медиану (т.е. (k+1)/2-й элемент) этих k эле­ментов. Заметим в скобках, что интересной задачей является определение наилуч­шего значения А как функции от количества элементов в подмножестве, подлежащем сортировке. Если k очень мало, то среднее время будет близко к тому, как если бы выбирался только один элемент. Если же k очень велико, то уже необходимо учиты­вать время нахождения медианы среди k элементов.

Другие реализации алгоритма быстрой сортировки можно получить в зависимости от того, что мы делаем в случае, когда получаются малые подмножества. При малых п алгоритмы с временем выполне­ния О(п²) работают быстрее, чем алгоритмы с временем выполнения порядка О(п log п). Однако понятие "малости" п зависит от многих факторов, таких как орга­низация рекурсивных вызовов, машинная архитектура и компилятор языка про­граммирования, на котором написана процедура сортировки. Предлага­ется значение 9 в качестве порогового значения размера подмножества, ниже которо­го целесообразно применять простые методы сортировки.

Существует еще один метод "ускорения" быстрой сортировки за счет увеличения используемого пространства памяти компьютера. Отметим, что этот метод применим к любым алгоритмам сортировки. Если есть достаточный объем свободной памяти, то можно создать массив указателей на записи массива А. Затем следует организовать процедуру сравнения ключей записей посредством этих указателей. В этом случае нет необходимости в физическом перемещении записей, достаточно перемещать указатели, что значительно быстрее перемещения непосредственно записей, особенно когда они большие (состоят из многих полей). В конце выполнения процедуры сортировки указа­тели будут отсортированы слева направо, указывая на записи в нужном порядке. Затем сравнительно просто можно переставить сами записи в правильном порядке.

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