Размещение путем сравнения и обмена (просеивание)

Действия по размещению некоторого элемента, соответствующие этому варианту, могут быть оформлены в виде следующих команд (i — начальный индекс перемещаемого элемента, j — индекс, который этот элемент имеет в ходе перемещения):

Если a[i]<a[i-l] |Если нужно перемещать i-й элемент

| то j:=i

| нц

| | Swap(a[j],a[j-l]) |Смещаем его влево путем обмена

| | j:=j-l |Новый индекс перемещаемого элемента

| кц при j=1 или a[j]>=a[j-l]

все

где Swap — процедура, обеспечивающая обмен значениями двух величин.

Примечание. Использование в условии окончания цикла дополнительного условия j=l позволяет избежать сравнения j-гo элемента с несуществующим (j-1) -м, что имеет место при j-1.

Можно также использовать цикл с предусловием:

j:=i

нц пока j>l и a[j]<a[j-l] |Пока нужно перемещать i-й элемент

| Swap(a[j],a[j-l]) |Смещаем его влево путем обмена

| j:=j-1 |Новый индекс перемещаемого элемента

кц

Процедура сортировки, использующая соответствующий фрагмент с циклом с постусловием, на Паскале имеет вид:

procedure Insert_Sort(var a:arrtype);

var i, j :integer;

begin

{Выбирает последовательно элементы с индексами от 2 до n}

for i:=2 to n do

if a[i]<a[i-l] {Если нужно перемещать i-й элемент}

then begin

j:=i;

repeat

Swap(a[j],a[j-l]); {Смещаем элемент влево путем обмена}

j:=j-l {Новый индекс перемещаемого элемента}

until (j=l) or (a[j]>=a[j-l])

end

end;

где Swap — процедура, выполняющая обмен значениями двух величин:

procedure Swap(var a,b:integer);

var c:integer;

begin

c:=a; a:=b; b:=c

end

Очевидно, что использование в процедурах дополнительного условия j=1, о котором говорилось выше, приводит к существенному увеличению времени выполнения программ (для каждого элемента многократно проверяется дополнительное условие).

Этот недостаток можно устранить, если применить так называемый "барьер" — создать в сортируемом массиве элемент с индексом 0 (расширив диапазон индексов в описании массива до 0.. n) и на каждом шаге сортировки присваивать ему значение, равное значению очередного размещаемого элемента. Можно также ускорить работу, если в ходе размещения не проводить обмен значениями двух соседних элементов массива (процедура Swap выполняет 3 операции присваивания!).

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

Процедуры, применяющие "барьер" и не использующие npoцедypy Swap, имеют вид:

procedure Insert Sort(var a:arrtype);

var i,j:integer;

begin

for i:=2 to n do

if a[i]<a[i-1] then

begin

a[0]:=a [ i ]; {Создаем ."барьер"}

j:=i;

repeat

a[j]:=a[j-1]; {Смещаем соседний слева элемент вправо}

j:=j-1;

until a[0]>=a[j-1];

{'Место j, соответствующее элементу a[i], найдено}

a[j]:=a[0]; {На найденном месте размещаем элемент a[i]}

end

end;

В приведенной процедуре величина а[0] хранит значения размещаемого элемента массива a[i]; величина j имеет смысл, указанный выше (j – индекс, который элемент а [i] имеет в ходе перемещения).

Примечание. Описание типа arrtype в основной программе должно быть изменено на следующее: type arrtype=array[0. .n] of integer;

При выводе полученного отсортированного массива необходимо «не забыть» про лишний нулевой элемент.