В) Сортировка с помощью прямого Включения Идея метода

Совокупность элементов { a₀ , a₁ , … , a _i-1 , a_i , a_i+1, … ,a _n-1 } в каждый момент можно рассматривать как две совокупности

S₁ = { a₀ , a₁ , … , a _i-1 } и S₂ = { a_i , a_i+1, … ,a _n-1 } , где S₁ — упорядочена, и метод сортировки состоит в последовательном включении элементов второй совокупности { a_i , a_i+1, … ,a _n-1 } на свои места в первую совокупность. Сначала

S₁ состоит из одного элемента { a₀}, затем из двух, но упорядоченных { a₀, a₁ } и т.д. пока все элементы { a_i , a_i+1, … ,a _n-1 } (i=2,3…n) не будут включены в S₁ на свои места.

Cхема алгоритма:

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

{R = a[i];

<Включить R в сегмент { a₀ , a₁ , … , a _i-1 , , a _i} на своё место >

}

Включение R в упорядоченный сегмент предполагает:

• поиск места вставки { a₀ , … , a_k ,  a _k+1 … , a _i-1 , a_i};

• освободить место вставки, сдвинув вправо на 1 позицию элементы a_k+1, … , a_i-1 ;

• поместить R на освободившееся место a _k+1= R.

//сортировка методом включения (вставками)

voidinsertion(inta[ ],intn)

{for(int i=1; i<n; i++) //перебор элементов

{int r=a[i];

// поиск места вставки эл-та r

int j=i-1;

bool p=true;

while (j>=0 && p)

if (a[j]>r) {a[j+1]=a[j]; j--;}

elsep=false;

//поместить r на свое место

a[j+1]=r;

}

}

Характеристики алгоритма сортировки с помощью прямого Включения:

M(n)_min=2*(n-1)

Порядок метода О(n²)

Модификации прямого Включения:

1.Модификация. Поиск места вставки — линейный слева направо, его уже нельзя совместить со сдвигом.

Поиск места вставки — линейный с барьером. Возможны два направления поиска: а) поиск слева направо с правым барьером, барьером служит сам элемент a _i ;

б)поиск справа налево с левым барьером; барьер устанавливается на место первого элемента a₀.

Самим рассмотреть этот вариант.

voidinsertion(inta[ ],intn)

{for(int i=1; i<n; i++) //перебор элементов

{int r=a[i];

int j=0;

//поиск места вставки- линейный --> с барьером (a[i])

while(a[j]<r)j++;

//смещение (сдвиг ) элементов

for(int m=i-1;m>=j;m--) a[m+1]=a[m];

//поместить r на свое место

a[j]=r;

}

}

2. Модификация.Cортировка методом включения (вставками) улучшенная!!

void insertion11 (int a[], int n)

{int i;

for(i=n-1;i>0; i--)

if (a[i]<a[i-1]){int x=a[i]); a[i]= a[i-1]; a[i-1]=x;}

//минимальный встал в начало и будет служить барьером!!

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

{int r=a[i];

// поиск места вставки эл-та r

int j=i;

while (r<a[j-1]){ a[j]=a[j-1]; j--;}

a[j]=r;

}

}

3. Модификация. Так как совокупность { a₀ , a₁ , … , a _i-1 } упорядочена, то для поиска места вставки можно использовать метод Двоичного поиска; метод сортировки в этом случае называют Двоичное включение.

void Binaryinsert (int a[], int n)

{for(int i=1;i<n;i++) //перебор элементов

{int r=a[i];

// двоичный поиск места вставки эл-та r

int l=0,p=i;

while (l < p)

{ int m=(l+p)/2;

if (a[m]<r) l=m+1;

elsep=m;

} //p– место вставки

for(int j=i-1;j>=p;j--)a[j+1]=a[j]; //сдвиг элементов

//поместить r на свое место

a[p]=r;

}

}