Вопрос 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;

}

}