Простые вставки

Пусть в заданной последовательности а₁, А₂,..., А_N первые I-1 элементов уже отсортированы. Найдем в этой части последовательности место для I-го элемента. Для этого будем сравнивать его по порядку со всеми элементами, стоящими левее, до тех пор пока не окажется, что некоторый А_{K< =} а_I. Затем сдвинем часть последовательности А_K+1, А_K+2,..., А_I-1 на один элемент вправо и освободимтаким образом место А_K+1для элемента А_I, куда его и поставим. Эта последовательность действий отображена на Рис. 2 при упорядочивании последовательности треугольников разной высоты. Считая, что первые три элементауже упорядочены, ищем место для четвертого по вышеизложенному правилу. Знак < = (а не <) показывает, когда нужно прекратить сравнения, т. е. движение влево по последовательности. При этом достигается устойчивость сортировки вставками.

После того как мы проделаем подобные действия для всех элементов от 2-го до N-го, мы получим отсортированную последовательность.Отметим очень важную деталь в наших действиях. Когда мы проводим сравнение I-го элемента со всеми, стоящими левее него, может оказаться, что не найдется такого Ак, что А_{K< =} а_I; это произойдет, если А_I меньше всех левых элементов. НаРис. 2 эта ситуация отмечена дорожным знаком " Прочие опасности". В этом случае нужно закончить просмотр (по достижении первого элемента последовательности) и осуществить сдвиг A₁,..., A_I-1 вправо, а элемент A_I поставить на первое место.

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

I: = 2;
пока I < = N
нц найти место Ак для А_I, в упорядоченной части последовательности (1)
сдвинуть элементы А_к+1, А_к+2,:, A_i-1 вправо (2)
поставить элемент А_I на нужное место (3)
I: = I+1
кц

В результате действия 1 мы должны получить номер К, индекс элемента, рядом с которым справа нужно поставить А_I.

Чтобы найти место для А_I, нужно сравнивать его последовательно со всеми левыми соседями до элемента А_{K< =} а_I и, если такового не окажется, остановиться на первом элементе. Действия эти - циклические, причем удобнее оформить цикл по текущему номеру элемента. Получим:

1 инициализация цикла (1.1)
пока J> 0
нц сравнить элементы а_I и a_J (1.2)
кц

Обдумывая пункт 1.1 - инициализацию цикла, мы должны предусмотреть три момента. Во-первых, значение элемента а_I; нужно запомнить, так как иначе при сдвиге оно может потеряться. Во-вторых, нужно зафиксировать номер I-1 - с этого элемента начнется сравнение. В-третьих, нужно позаботиться о том, чтобы в ситуации, когда а_I, меньше A₁, A₂..., A_I-1, он смог встать на первое место. Следовательно, получаем:

1.1 X: = A[I]; J: = I-1; K: = 1

Далее, по результатам сравнения а_I, и a_J мы должны сделать вывод о том, продолжать сравнение или нужный элемент уже найден и пора закончить цикл. Закончить цикл можно присваиванием переменной J нулевого значения. Имеем:

1.2 если A[I] > = A[J]
то K: = J+1; J: = 0
иначе J: = J-1
все

Перейдем к детализации пункта 2. Для сдвига последовательности вправо нужно просматривать ее из конца в начало и последовательно сдвигать элементы.

2. J: = I
пока J> K
нц A[J]: = A[J-1]
J: = J-1
кц

Пункт 3 - это один оператор присваивания:

3. A[K]: = X

И наконец, законченный алгоритм сортировки простыми вставками.
алг ВСТАВКА (цел N, вещтаб A[1: N])
арг A, N
рез A
начцел I, J, K, вещ X
I: = 2
пока I < = N
нц X: = A[I]; J: = I-1; K: = 1
пока J> 0
нцесли A[I] > = A[J]
то K: = J+1; J: = 0
иначе J: = J-1
все
кц
J: = I
пока J> K
нц A[J]: = A[J-1]
J: = J-1
кц
A[K]: = X;
I: = I+1
кц
кон