Сортировка с помощью прямого выбора
Этот приём основан на следующих принципах:
1. Выбирается элемент с наименьшим значением.
2. Он меняется местами с первым элементом A1.
3. Затем этот процесс повторяется с оставшимися n-1 элементами, n-2 элементами и т. д. до тех пор, пока не останется один, самый большой элемент.
Процесс работы этим методом с теми же восемью ключами, что и в таблице, использованной в разделе “метод прямого включения” проиллюстрирован ниже.
Алгоритм формулируется следующим образом:
FOR i := 1 ТО n-1 DO
присвоить k индекс наименьшего из a[i] .,. а[п];
поменять местами a[i] и a[k];
END;
Такой метод - его называют прямым выбором - в некотором смысле противоположен прямому включению. При прямом Включении на каждом шаге рассматриваются только один очередной элемент исходной последовательности и все элементы готовой последовательности, среди которых отыскивается точка включения; при прямом выборе для поиска одного элемента с наименьшим ключом просматриваются все элементы исходной последовательности и найденный помещается как очередной элемент в гототовую последовательность.
Анализ прямого выбора. Число сравнений ключей (С), очевидно, не зависит от начального порядка ключей. Можно сказать, что в этом смысле поведение этого метода менее естественно, чем поведение прямого включения. Для С имеем:
C=(п2-п)/2.
Число перестановок минимально:
Мmin = 3 * (n -1);
в случае изначально упорядоченных ключей и максимально:
Мmах = п2 / 4 + 3 * (n - 1),
если первоначально ключи располагались в обратном порядке. Для того чтобы определить Mavg, мы должны рассуждать так. Алгоритм просматривает массив, сравнивая каждый элемент с только что обнаруженной минимальной величиной; если он меньше первого, то выполняется некоторое присваивание. Вероятность, что второй элемент окажется меньше первого, равна 1/2, с этой же вероятностью происходят присваивания минимуму. Вероятность того, что третий элемент окажется меньше первых двух, равна 1/3, а вероятность для четвертого оказаться наименьшим - 1/4 и т. д. поэтому полное ожидаемое число пересылок равно Нn -1, где Нn – n-ное гармоническое число:
Нn = 1+ 1/ 2 + 1/3 + ...+ 1 / п.
Нn можно выразить и так:
Нn = In n + g + 1/ 2п - 1 / 12п2 + …,
где g = 0.577216 ... - константа Эйлера. Для достаточно больших n мы можем игнорировать дробные составляющие и поэтому аппроксимировать среднее число присваиваний на i-ом просмотре выражением:
Fi = In i + g+ 1.
Среднее число пересылок Mavg , в сортировке с выбором есть сумма Fi с i от 1до п:
Mavg = n *(g + 1) + (Si: 1? i ? n: In i).
Вновь аппроксимируя эту сумму дискретных членов интегралом,
Integral (1 : п) ln х dx = х * (ln х - 1) = п* ln (п) - п + 1,
получаем наконец приблизительное значение:
Mavg == п * (ln (п) + g).
Отсюда можно сделать заключение, что, как правило, алгоритм с прямым выбором предпочтительнее строгого включения. Однако, если ключи в начале упорядочены или почти упорядочены, прямое включение будет оставаться несколько более быстрым.
Другие методы сортировки:
1. Сортировки с помощью включения (by insertion).
2. Сортировки с помощью прямого выбора (by selection).
3. Сортировки с помощью обмена (by exchange).
