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

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

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

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

При первом проходе ищется минимальное значение массива array, которое затем меняется местами с первым элементом array[1]. Затем поиск продолжается на оставшихся n-1 элементах, ищется второй минимум, который переставляется с элементом array[2] и т.д.

Cсортировка методом отбора тоже является n-квадратичным алгоритмом. Внешний цикл исполняется n-1 раз, а внутренний - n/2 раз. В результате сортировка методом отбора требует сравнений, что сильно замедляет работу при большом количестве элементов. Количества перестановок, требующиеся в наилучшем и наихудшем случаях для метода сортировки отбором, будут следующими:

В лучшем случае: 3(n-1) , В худшем случае:

В наилучшем случае, если список уже упорядочен, требуется сравнить только (n-1) элемент, и каждое сравнение требует трех промежуточных шагов. Наихудший случай аппроксимирует количество сравнений. Средний случай вычисляется по следующей формуле:

n(log n + y), где y - константа Эйлера, примерно равная 0.577216.

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

void select_sort(int *array, int n)

{

int i, j, temp;

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

for (j = i+1; j < n; j++)

if (array[j] < array[i]) {

temp = array[i];

array[i] = array[j];

array[j] = temp;

}

}

Вопрос 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 . Эти дополнительные проверки в некоторой степени снизят производительность алгоритма Шелла. Улучшенные сии алгоритма используют специальные элементы массива, называемые стражами. Стражи не являются частью сортируемого массива. Они содержат завершающие элементы, обозначающие наибольший и наименьший возможные элементы массива. Это делает ненужной проверку границ массива, но требует конкретной информации о данных, что ограничивает общность функции сортировки.