Прямого обмена

Сортировка методом

Прямого выбора

Сортировка методом

Прямого включения

Сортировка методом

Имеется последовательность элементов а0, а1, а2,...,а_п-1. Эта последовательность мысленно делится на две последовательности: упорядоченную последовательность а₀, а₁,..., а_i-1 и исходную, неупорядоченную аi, аi+1, ..., аn-1. Очевидно, что первоначально упорядоченная последовательность состоит из единственного элемента а0. При каждом шаге, начиная с i = 1 и увеличивая i каждый раз на единицу, из исходной последовательности извлекается i -й элемент аi и вставляется в готовую последовательность в нужное место, при необходимости сдвигая элементы готовой последовательности на одну позицию вправо вплоть до i -й позиции. Поиск подходящего места осуществляется сравнением а_i с элементами аj, j=i-1,i-2, …,0, и одновременным обменом местами аi и аj, если аi < аj, т.е. сдвигом аj на одну позицию вправо. Процесс поиска заканчивается при выполнении одного из условий:

• а_i > = аj,

• достигнут левый конец готовой последовательности.

Этот метод обеспечивает устойчивую сортировку.

Для процедуры сортировки методом прямого включения число сравнений С и число пересылок М таковы: Cmin = n - 1; Cсредн = (п² + п - 2)/4; Сmax = (п² - п)/2 - 1; Mсредн = (n² + 9п - 10)/4.

Исходный массив:

27 412 71 81 59 14 273 87

Отладочная печать по шагам сортировки:

i=1 27 412 71 81 59 14 273 87

i=2 27 71 412 81 59 14 273 87

i=3 27 71 81 412 59 14 273 87

i=4 27 59 71 81 412 14 273 87

i=5 14 27 59 71 81 412 273 87

i=6 14 27 59 71 81 273 412 87

i=7 14 27 59 71 81 87 273 412

Отсортированный массив:

14 27 59 71 81 87 273 412.

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

Среднее число сравнений здесь С= O(n1оg2n), а среднее число сдвигов М = О(п²).

Алгоритм сортировки заключается в следующем:

1. В исходной последовательности из п элементов отыскивается элемент с наименьшим ключом.

2. Он меняется местами с первым элементом.

3. В оставшейся последовательности из (п - 1) элементов отыскивается минимальный элемент и меняется местами со вторым элементом и т.д., пока не останется один, самый болыиой эле-мент.

Число сравнений С = (п² - п), число перестановок: Мсредн = n(ln п + g), где g= 0.577216 — константа Эйлера.

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

(сортировка методом пузырька)

Алгоритм прямого обмена основывается на сравнении и смене мест для пары соседних элементов, в результате одного прохода через последовательность по направлению с ее конца к началу самый меньший (легкий) элемент оказывается в начале последовательности (или самый большой элемент в конце последовательности при обратном направлении). При втором проходе следующий меньший элемент сдвинется к началу последовательности и т.д., пока все элементы не будут упорядочены.

Алгоритм можно улучшить с учетом того, что если в очередном проходе не было обмена, то последовательность упорядочена. Число сравнений в прямом обменном алгоритме

Cmin = n; Сmax = (п² - п)/2, число перестановок Mсредн = 3(n²-n)/4.

Исходный массив:

27 412 71 81 59 14 273 87.

Отладочная печать по шагам сортировки:

i=0 14 27 412 71 81 59 87 273

i = 1 14 27 59 412 71 81 87 273

i = 2 14 27 59 71 412 81 87 273

i= 3 14 27 59 71 81 412 87 273

i = 414 27 59 71 81 87 412 273

i=5 14 27 59 71 81 87 273 412

Отсортированный массив:

14 27 59 71 81 87 273 412.

Дата добавления: 2017-01-14