Простая сортировка вставками

На этапе j имя x_j вставляется на свое правильное место среди x₁, x₂, …, x_n. При вставке x_j временно размещается в ячейке X и просматриваются имена x_j-1, x_j-2, …, x₁. Они сравниваются с Х и сдвигаются вправо, если обнаруживается, что они больше Х. Имеется фиктивное имя x₀, значение которого –¥ служит для остановки просмотра слева.

	x0 ¬ – ¥ for j = 2 to n do	i ¬ j – 1 X ¬ xj while X < xi do xi+1 ¬ X	xi+1 ¬ xi i ¬ i – 1
x0	x1	x2	x3	x4	x5
– ¥	8					j=2
– ¥	7					j=3
– ¥		7				j=4
– ¥			7			j=5
– ¥

Рис. 3.4. Простая сортировка вставками для пяти имен.

Пунктирные вертикальные линии разделяют уже отсортированную часть таблицы от еще не отсортированной.

Приведем программную реализацию алгоритма на основе языка С++.

#include "stdafx.h"

#include <iostream>

using namespace std;

#include <conio.h>

int main ()

{

int A[20],i,n;

cout<<"Enter size A[] , n= ";

cin>>n;

cout<<"\n Enter elements: \n";

for(i=0;i<n;i++) cin>>A[i];

int zm; // для выноса элемента

int ip; // индекс предыдущего элемента

for (i = 1; i < n; i++)

// цикл по числам и каждому числу ищется свое место, т.е.это прогоны

{

zm = A[i];

ip = i-1; // предыдущее место

while(ip >= 0 && A[ip] > zm)

// пока индекс не равен 0 и предыдущий элемент массива больше текущего

{

A[ip + 1] = A[ip]; // перестановка элементов массива

A[ip] = zm;

ip--;

}

cout<<"\n Work array: \n"; // отладочная печать

for(int v=0; v<n; v++) cout<<A[v]<<" ";

}

cout<<"\n Resultat: \n";

for(i=0;i<n;i++) cout<<A[i]<<" ";

_getch();

return 0;

}