5.2. Сортировка вставками

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

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

A

S

O

R

T

I

N

G

E

X

A

M

P

L

E

A

S

O

R

T

I

N

G

E

X

A

M

P

L

E

A

O

S

R

T

I

N

G

E

X

A

M

P

L

E

A

O

R

S

T

I

N

G

E

X

A

M

P

L

E

A

O

R

S

T

I

N

G

E

X

A

M

P

L

E

A

I

O

R

S

T

N

G

E

X

A

M

P

L

E

A

I

N

O

R

S

T

G

E

X

A

M

P

L

E

A

G

I

N

O

R

S

T

E

X

A

M

P

L

E

A

E

G

I

N

O

R

S

T

X

A

M

P

L

E

A

E

G

I

N

O

R

S

T

X

A

M

P

L

E

A

A

E

G

I

N

O

R

S

T

X

M

P

L

E

A

A

E

G

I

M

N

O

R

S

T

X

P

L

E

A

A

E

G

I

M

N

O

P

R

S

T

X

L

E

A

A

E

G

I

L

M

N

O

P

R

S

T

X

E

A

A

E

E

G

I

L

M

N

O

P

R

S

T

X

Рис.2. Пример работа сортировки вставками

Во время первого прохода сортировки вставками элемент S, занимающий вторую позицию, больше А, так что трогать его не надо. На втором проходе, когда в третьей позиции встречается элемент О, он меняется местами с S, так что последовательность становится АО S отсортированной и т.д.