Сортировка массива простым выбором

Метод основан на следующем правиле:

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

Он меняется местами с последним элементом arr [s-1]. Затем эти операции повторяются с оставшимися первыми s-1 элементами, затем - с s-2 первыми элементами и т.д. до тех пор, пока не останется только первый элемент - наименьший. Пример сортировки методом простого выбора показан на рисунке 4:

Рисунок 4. Сортировка массива простым выбором

Эффективность сортировки простым выбором. Число сравнений ключей не зависит от начального порядка ключей. Операция сравнения выполняется в теле цикла с управляющей переменной k и средним числом повторений size/2. Этот цикл, в свою очередь, находится в теле цикла с управляющей переменной L и числом повторений size − 1. Таким образом, число сравнений

С= (size − 1) * size − 1/2

Число пересылок, напротив, зависит от начального порядка ключей. Если принять, что операция сравнения в теле цикла по k дает результат " истина" в половине случаев, то среднее число пересылок в этом цикле равно size/4. Цикл по L, как указывалось выше, выполняется size − 1 раз и в теле цикла выполняется три пересылки и цикл по k. С учетом этого число пересылок:

М= (3+ size/4) * (size − 1)

Получаем, что при сортировке простым выбором и число сравнений, и число пересылок пропорционально .