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

 

Массив разделяется на две части: отсортированную и не отсортированную. Элементы из не отсортированной части поочередно выбираются и вставляются в отсортированную часть так, чтобы не нарушить в ней упорядоченность элементов.

В начале работы алгоритмы в качестве отсортированной части массива принимают только один первый элемент, а в качестве не отсортированной части – все остальные элементы.

Таким образом, алгоритм будет состоять из n – 1-го прохода (n – размерность массива), каждый проход будет включать четыре действия:

Взятие очередного i-го не отсортированного элемента и сохранение его дополнительной переменной.

Поиск позиции j, в отсортированной части массива, в которой присутствие взятого элемента не нарушит упорядоченности элементов.

Сдвиг элементов массива от i – 1-го до j-го вправо, чтобы освободить найденную позицию вставки.

Вставка взятого элемента в найденную j-ю позицию.

1 шаг:

3

 

2 шаг:

1

 

 

3 шаг:

1

4 шаг:

1

 

 

5 шаг:

1

Результат:

 

 

БЛОК – СХЕМА

I = 2

Æ 1

 

J = 1 R = A(I) IR =

 

 

Æ 1

I = I + I

1 Æ

IR = 1

1 Æ

J = J+1

K = I - 1

1

A(J) = R IR = 2

A(K+1) = A(K) K = K - 1

 

Программа, реализующая рассмотренный алгоритм, будет иметь следующий вид.

 

Rem Sort

Const n =10 ‘длина массива

 

TVector = array [1…n] of Real;

Dim Vector(1 to n)

Defsng B

defint i, j, K

Cls

Print “Введите элементы массива:”

For i=1 to n

Input Vector (i)

Print

‘ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

for i=2 to n

B=Vector (i) ‘взятие неотсортированного элемента

‘цикл поиска позиции вставки

j=1

While B>Vector(j)

j= j+1 ‘после окончания цикла индекс j фиксирует позицию вставки

wend

‘цикл сдвига элемента для освобождения позиции вставки

for K= i-1 to j step -1

Vector (K+1) = Vector (K)

next

‘Вставка взятого элемента на найденную позицию

Vector (j) = B

‘ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

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

For i = 1 to n

Print “vector (i);

Next

End

Результат работы:

Bведите элементы массива: 7 6 5 4 0 9 8 3 2 1 Отсортированный массив: 0 1 2 3 4 5 6 7 8 9