Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Сортировка простой вставкой



Пусть 1<j£ N и записи R1,…,Rj-1 уже размещены так, что К1 £ К2,£…£Кj -1. Будем сравнивать по очереди Кj с Кj –1, Кj-2,… до тех пор, пока не обнаружим, что запись Rj следует вставить между Ri и Ri+1; тогда подвинем записи Ri+1 ,…, Rj-1 на одно место вверх и поместим новую запись в позицию i+1. Удобно совмещать операцию сравнения и перемещения.

Алгоритм В (Сортировка простыми вставками).

(Цикл по j) Выполнить шаги с В2 по В6 при j = 2, 3,…,N. После чего алгоритм завершить.

(Установить i, К, R) Установить i:= j –1, К:=К j , R Rj (R – запись которую мы позиционируем, К – ключ позиционируемой записи, i – номер позиции за которой расположится запись R)

(Сравнить К, Кi ) Если К >= Кi, то перейти к шагу В6, (т.е. мы нашли искомое место), иначе шаги В4 и В5.

(Переместить Ri , вперед) Установить R i+1 := R i.

(Уменьшить i). Установить i:= i –1. Если i > 0, то перейти к шагу В4, иначе (т.е. если i =0, то К – наименьший из рассмотренных на данный момент ключей и R надо установить на 1 ю позицию) перейти на шаг В6.

(R на место R i ) Установить R i+1:= R.

Действие алгоритма приведено на Рис. 1

Рис. 1 Применение простых вставок

Реализация алгоритма для краткости (и общности при сравнении алгоритмов O(N2)) используется процедура Swap. На самом деле, используемое в блок-схеме «полуприсваивание» (сдвиг), значительно уменьшает общее число присваиваний

Листинг 8.3. Сортировка вставками

(1) {R[1].K уже на месте};

(2) for i:= 2 to n do

begin

(3) j:= i;

(4) while R [ j ]. K < R [ j - 1]. K do

Begin

(5) swap(R [j], R [j - 1]);

(6) j:= j - 1

End

End

Бинарные вставки.

Когда при сортировке простыми вставками обрабатывается j я запись, ее ключ сравнивается примерно с j/2 ранее отсортированными ключами; поэтому после прохода всех N записей общее число сравнений (1+2+3+…+N) / 2 = ((N+1)*N/2) / 2» N2 / 4, а это очень много даже при умеренных значений N.

Для уменьшения числа сравнений можно использовать бинарную вставку. Пусть, например, вставляется 64 запись. Можно сначала сравнить ключ К64 с К32, если он меньше, сравниваем с К16, иначе с К48. Однако, найдя номер позиции, куда надо поместить запись, надо все равно переместить j/2 записей, что высвободить место.

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





Дата публикования: 2015-01-10; Прочитано: 514 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.005 с)...