Вставка з лінійним пошуком місця вставки від взятого елемента («справа») без бар’єру

 

Сортування вставкою або включенням. Суть алгоритму в наступному - елементи масиву розділяють на впорядковану частину А[1], А[2],.., А[i-1], яка розташовується на початку масиву, і останню, невпорядковану частину А[i], ……., А[N], а потім, поодинці, елементи з невпорядкованої частини переносяться у впорядковану. Перед початком сортування впорядкована частина складається всього з одного, першого елементу, а всі останні елементи розташовуються в другій частині масиву.

Послідовні кроки алгоритму сортування полягають в тому, що перший елемент з неврегульованої частини порівнюється з останнім елементом впорядкованої послідовності. Якщо виявляється, що порядок розташування порівнюваних елементів не відповідає вимогам сортування, то елемент з неврегульованої частини витягується і переноситься у впорядковану частину. Місце для цього елементу звільняється шляхом зрушення впорядкованих елементів управо на місце елементу, що вилучається. Зрушення впорядкованих елементів на одну позицію управо продовжуються до тих пір, поки не буде знайдено місце для елементу, що вилучається з неврегульованої послідовності.

Як видно з малюнка 2.2, в алгоритмі є два цикли. У зовнішньому циклі послідовно змінюється номер лівого кордону неврегульованої області від значення i = 2 до i = count. У телі цього циклу виробляється порівняння елементів, що знаходяться по обидві сторони від кордону, що розділяє впорядковану і невпорядковану частини. Якщо порядок порушений, то перший елемент неврегульованої послідовності запам'ятовується в змінній tmp і, тим самим, звільняється місце для зрушень впорядкованих елементів вправо.

Внутрішній цикл забезпечує послідовні зрушення впорядкованих елементів управо, починаючи з останнього, до тих пір, поки не буде знайдено місце для першого елементу з неврегульованої області.

Можливість вставки елементу визначається одним з двох умов.

-mas[j-1] <= buf < mas[j] і 1 < j < i, тобто знайдено місце усередині впорядкованої послідовності.

-j=1, тобто tmp є найменшим елементом і вставляється на перше місце у впорядкованій частині масиву.

Після завершення циклу зрушень елемент масиву із змінної tmp переноситься на знайдене місце у впорядкованій послідовності.

 

Малюнок 2.2 - Алгоритм сортування по неспаданню методом вставки

 

Процедура сортування методом вставки

procedure SortInsert(var a:TArray100; count: integer);

var i, j, x: integer;

begin i:= 2 to count do

// Порівнюємо елементи на границі між

// впорядкованими та невпорядкованими частинами масиву a[i] < a[i-1] then

Begin

// Порядок порушений, запамятовуємо i-й елемент

x:= a[i];

// Починаємо цикл зрушень вправо на місце i-го елементу

j:= i; // j - індекс вакантного місця

Repeat

// зрушуємо вправо

a[j]:=a[j-1];:=j-1;

// поки зліва не зявилось меньше число,

// або дішли до початку масиву

until (j = 1) or (a[j-1] <= x);

//'Тепер вставим колишній i-й елемент на нове місцез індексом j

a[j]:= x;

end;;;

Метод шейкерного сортування

 

Метод шейкерного сортування є удосконаленим методом сортування обміном із запам’ятовуванням місця останньої перестановки. Основна ідея методу полягає в тому, що послідовні проходи по масиву здійснюються з двох боків, і відсортованих частин у масиві є дві, причому вони з двох сторін «насуваються» на невпорядковану частину. Пари елементів послідовно порівнюються, та, якщо їх порядок розташування не відповідає певному критерію, елементи міняються місцями. Таким чином, найбільший елемент «спливає» у кінець масиву, а найменший - «тоне» у початок.

Метод шейкерного сортування за визначенням не зменшує кількість обмінів, але кількість порівнянь у нього є зазвичай меншою, аніж у методу обміну. Гарним прикладом переваги шейкерного методу над методом обміну може бути послідовність 2, 3, 4, 5, 1, яку необхідно впорядкувати за неспаданням. Методом шейкерного сортування достатньо 1-2 проходи (залежно від того, з якого боку починати), а методом обміну знадобилося б чотири проходи,якщо кожен раз починати прохід з початку масиву.

Складність алгоритму O(n²), для найгіршого та середнього способу розташування, якщо масив майже відсортовано - прямує до O(n).

Для сортування тривимірного масиву згідно із варіантом завдання алгоритм ускладнюється так само як і для методу обміну.

Схематично (у вигляді блок-схеми) алгоритм шейкерного сортування зображено на Рис 2.3.

Малюнок 2.3. Алгоритм шейкерного сортування (блок-схема)