Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Идея метода

Совокупность элементов { 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.

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

void insertion (int a[ ], int n)

{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--;}

else p=false;

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

a[j+1]=r;

}

}

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

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

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

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

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

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

void insertion (int a[ ], int n)

{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;

else p=m;

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

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

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

a[p]=r;

}

}