Метод сортировки выбором
Исходный массив длиной N разбивается на две части: итог и остаток. Участок массива, называемый итогом, располагается с начала массива и должен быть упорядоченным, а участок массива, называемый остатком, располагается вплотную за итогом и содержит исходные числа не отсортированной части исходного массива. Текстуальный алгоритм сортировки выбором. Шаг 1. Полагается i =0, т.е. считается, что итоговый участок – пуст. Шаг 2. В остатке массива ищется минимальный элемент и он меняется местом с первым элементом остатка (i -ым элементом массива). После чего значение i увеличивается на единицу, тем самым расширяя итоговый участок массива (отсортированную часть исходного массива). Шаг 3. Если i < N, то повторяется Шаг 2. В противном случае – конец алгоритма, т.к. итог становится равным всему массиву. Конец алгоритма. Схема алгоритма методом сортировки выбора представлена на рис. 1.
Рисунок 1 – Схема алгоритма сортировки методом выбора Этот метод похож на метод пузырька. Происходит такое же разбиение массива на отсортированную и не отсортированную части, но перемещение первого элемента остатка на принадлежащее ему место в итоге делается не сравнением двух соседних элементов, а с помощью метода двоичного поиска, который удобно оформить в виде отдельной процедуры. Текстуальный алгоритм методом включением. Шаг 1. Пусть i =1, т.е. итоговый участок состоит из одного элемента. Шаг 2. Берется первый элемент остатка и перемещается в отсортированную часть массива так, чтобы итоговый участок остался упорядоченным. Шаг 3. После того, как первый элемент остатка переместился в итоговый участок, увеличивается на единицу значение переменной i, тем самым увеличивая отсортированную часть массива. Если i < N, то управление передается на Шаг 2, в противном случае - работа алгоритма завершена. Конец алгоритма. Схема алгоритма метода сортировки включением представлена на рис. 3.
Рисунок 3 – Блок-схема алгоритма сортировки прямым включением
|
