Сортування масиву із методом прямого включення. Сортування методом прямого включення. Ефективність алгоритму прямого включення

Необхідні визначення та класифікація сортувань.

Сортування. Необхідні визначення та класифікація сортувань. Сортування прямого включення та вибору. Їхня ефективність

Сортування– це розташування даних у пам'яті в регулярному вигляді за їхніми ключами. Так що при обробці даних важливо знати інформаційне поле даних та розміщення їх у машині. Тому розрізняють внутрішню(Сортування в оперативній пам'яті) та зовнішнє сортування(Сортування у зовнішній пам'яті). Регулярністьрозташування елементів - це зростання (зменшення) значення ключа від початку до кінця в масиві.

Якщо сортовані записи займають великий обсяг пам'яті, їх переміщення вимагає великих витрат. Для того, щоб їх зменшити, використовують метод сортування таблиці адрес. Цей метод застосовують у таблиці адрес ключів. Виробляють перестановку покажчиків, тобто. Сам масив не переміщується. При сортуванні можуть зустрітись і однакові ключі. У цьому випадку однакові ключі бажано розташувати після сортування в тому самому порядку, що й у вихідному файлі. Цей принцип використовується для стійкого сортування.

Ефективність сортування можна розглядати з кількох критеріїв:

1) час, що витрачається на сортування;

2) обсяг оперативної пам'яті, необхідної для сортування;

3) час, витрачений програмістом написання програми.

Час, витрачений на сортування, пропорційно до кількості порівнянь при виконанні сортування та кількості переміщень елементів.

Вважається, що порядок числа порівняння при сортуванні може бути в межах від о(nlogn)до о(n 2), де про(n)- ідеальний та недосяжний випадок.

Методи сортування можна класифікувати приблизно так:

1) суворі (прямі) методи(їх ефективність приблизно однакова):

· прямого включення;

· прямого вибору;

· прямого обміну;

2) покращені методи.

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

Елементи подумки діляться вже готову послідовність a 1 ,...,a i-1та вихідну послідовність. У готовій послідовності елементи розташовуються в заданому порядку (за спаданням або зростанням). А у вихідній послідовності розташовуються елементи, які потрібно відсортувати. При кожному етапі елементи вихідної послідовності зменшуються на одиницю, а готова збільшується на одиницю. Це відбувається через те, що з вихідної послідовності вилучається i-й елемент і перекладається готову послідовність, у своїй він вставляється на потрібне місце серед елементів готової послідовності.

Розглянемо приклад сортування шляхом прямого включення на послідовності елементів: 10, 3, 11, 8, 2, 15, 44, 9 (табл. 11.1). Необхідно її відсортувати за зростанням.

Спочатку готова послідовність немає елементів. На першому етапі перший елемент вихідної послідовності – це 10, стає першим елементом готової послідовності. Далі другий крок: елемент 3 вихідної послідовності міститься в готову. Це відбувається так. Якщо елемент більше 10, він залишається на своєму місці, а якщо менше, то 10 зрушується на одиницю вправо і на її місце ставиться елемент. Оскільки 3<10, то готовая последовательность теперь будет иметь вид: 3, 10, а исходная – 11, 8, 2, 15, 44, 9. Далее на третьем шаге из исходной последовательности выбирается 11 и помещается в готовую последовательность. Сначала 11 сравнивается с 10, и так как 11>10, то 11 залишається дома. Вихідна послідовність тепер дорівнює: 8, 2, 15, 44, 9. Наступні кроки виконуються аналогічним чином.

Таблиця 11.1

Принцип роботи сортування прямим включенням

Число кроків у даному сортуванні (табл. 11.1) дорівнює числу елементів у послідовності, що сортується, тобто. 8 кроків = 8 елементів.

Існують два способи реалізації даного методу – без бар'єру (рис. 11.1) і з бар'єром (рис. 11.2).

Метод: Метод непрямого вимірювання вологості речовин, що ґрунтується на залежності діелектричної проникності цих речовин від їх вологості. Джерело: РМГ 75 2004 року: Державна система забезпечення їжі …

КРОВ- КРОВ, рідина, що заповнює артерії, вени та капіляри організму і складається з прозорої блідо-жовтуватої. кольору плазу ми і зважених у ній формених елементів: червоних кров'яних тілець, або еритроцитів, білих, або лейкоцитів, і кров'яних бляшок, або … Велика медична енциклопедія

Нерухомість- (Real estate) Визначення нерухомості, види нерухомості, оренда та продаж нерухомості Інформація про поняття нерухомість, види нерухомості, оренда та продаж нерухомості, оподаткування та страхування Зміст - це вид майна, … Енциклопедія інвестора

У цього терміна існують і інші значення, див. C. Див також: Сі (мова програмування) C++ Семантика: мультипарадигмальна: об'єктно орієнтоване, узагальнене, процедурне, метапрограмування Тип виконання: компілюваний З'явився в … Вікіпедія

ОЦІНКА ВАРТІСТЬ НЕМАТЕРІАЛЬНИХ АКТИВІВ- (англ. intangible assets appraisal) – визначення вартості обсягу прав підприємства на певну групу об'єктів, які не мають матеріально речового утримання та приносять підприємству дохід протягом періоду, обумовленого національним… Фінансово-кредитний енциклопедичний словник

ШКОЛА загальноосвітня- Навч. виховат. установа, базовий елемент утвор. системи. У цьому ролі Ш. предмет дослідження разл. дисциплін: пед., іст., демографіч., Соціологія, та ін. Тільки в педагогіці проблематика Ш. займає цілком самостійно. місце. Вивченість… … Російська педагогічна енциклопедія

час- 3.3.4 час tE (time tE): час нагріву початковим пусковим змінним струмом IА обмотки ротора або статора від температури, що досягається в номінальному режимі роботи, до допустимої температури за максимальної температури навколишнього середовища. Джерело … Словник-довідник термінів нормативно-технічної документації

ГОСТ Р МЕК 60204-1-2007: Безпека машин. Електроустаткування машин та механізмів. Частина 1. Загальні вимоги- Термінологія ГОСТ Р МЕК 60204 1 2007 року: Безпека машин. Електроустаткування машин та механізмів. Частина 1. Загальні вимоги оригінал документа: TN систем харчування Випробування за методом 1 відповідно до 18.2.2 можуть бути проведені для кожного ланцюга. Словник-довідник термінів нормативно-технічної документації

автоматичний- 3.3.1 автоматичний пробовідбірник (automatic sampler): Пристрій, який використовується для вилучення представницької проби рідини, що протікає трубопроводом. Автоматичний пробовідбірник зазвичай складається з зонда (щупа), екстрактора. Словник-довідник термінів нормативно-технічної документації

напруга- 3.10 напруга: Відношення зусилля, що розтягує, до площі поперечного перерізу ланки при його номінальних розмірах.

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

27 412 71 81 59 14 273 87.

Сортований список створюється заново; спочатку він порожній. На кожній ітерації перше число невідсортованого списку видаляється з нього і поміщається на відповідне місце у відсортованому списку. І тому відсортований список проглядається, починаючи з найменшого числа, доки знаходять відповідне місце нового числа, тобто. поки всі відсортовані числа з меншими значеннями не виявляться попереду нього, а всі числа з більшими значеннями - після нього. Наступна послідовність списків показує, як це робиться:

Ітерація 0

Відсортований 27

Ітерація 1Невідсортований 412 71 81 59 14 273 87

Відсортований 27 412

Ітерація 2Невідсортований 71 81 59 14 273 87

Відсортований 27 71 412

Ітерація 3Невідсортований 81 59 14 273 87

Відсортований 27 71 81 412

Ітерація 4Невідсортований 59 14 273 87

Відсортований 27 59 71 81 412

Ітерація 5Невідсортований 14 273 87

Відсортований 14 27 59 71 81 412

Ітерація 6Невідсортований 273 87

Відсортований 14 27 59 71 81 273 412

Ітерація 7Невідсортований 87

Відсортований 14 27 59 71 81 87 273 412

У наступному алгоритмі заводиться лише один список і переорганізація чисел проводиться в старому списку.

Algorithm SIS(Сортування Прямим включенням). Відсортувати старому місці послідовність цілих чисел I(1), I(2), . . . ,I (N) у порядку зростання.

Крок 1.[ Основна ітерація ]

For J← 2 to N do throughкрок 4 od ;and STOP.

Крок 2[ Вибір наступного цілого ] Set K← I(J); and L←J−1.

Крок 3[ Порівняння з відсортованим цілими ] While K

AND L≥1 do set I (L+1) ← I(L); and L←L−1 od.

Крок 4.[ Увімкнення ] Set I(L+1)←K.

QUICKSORT:Алгоритм сортування із середнім часом роботи О(N ln N)

Основна причина повільної роботи алгоритму SIS полягає в тому, що всі порівняння та обміни між ключами в послідовності а 1, а 2, . . . ,а Nвідбуваються для пар із сусідніх елементів. При такому способі потрібно відносно велике

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Строк 38 08 16 06 79 76 57 24 56 02 58 48 04 70 45 47Дія

1 38 47 зменшення j

5 04 38 обмін

6 08 38 збільшення i

10 38 79 обмін

14 02 38 обмін

15 76 38 збільшення i,>

16 38 76 обмін

17 38 56 зменшення j

19 24 38 обмін

20 57 38 збільшення i,>

21 38 57 обмін, зменшення

22 04 08 16 06 02 24 38 57 56 76 58 48 79 70 45 47

(1 2 3 4 5 6) 7 (8 9 10 11 12 13 14 15 16)

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

К. Хоор винайшов і дуже ефективно застосував цю ідею (алгоритм QUICKSORT), скоротивши середній час роботи алгоритму SIS від порядку (N 2) до порядку (N ln N). Пояснимо цей алгоритм наступним прикладом.

Припустимо, що хочемо відсортувати послідовність чисел з першого рядка на рис. 15. Почнемо з припущення, що першийключ у цій послідовності(38) служить гарною апроксимацією ключа, який зрештою з'явиться в середині відсортованої послідовності. Використовуємо це значення як провідний елемент, щодо якого ключі можуть змінюватися місцями, і продовжимо так. Встановлюємо два покажчики I і J, з яких I починає відлік зліва (I=1), а J- зліва в послідовності (J=N). Порівнюючи а Iі а J. Якщо а I ≤a J, встановлюємо J←J−1 та проводимо наступне порівняння. Продовжуємо зменшувати J доти, доки не досягнемо а I > а J .Тоді поміняємо місцями а I ↔a J(Рис.15, рядок 5, обмін ключів 38 і 04), встановлюємо I←I+1 і продовжуємо збільшувати I доти, доки не отримаємо а I > а J .Після наступного обміну (рядок 10, 79↔38) знову зменшуємо J. Чергуючи зменшення J і збільшення I продовжуємо цей процес з обох кінців послідовності до «середини» до тих пір, поки не отримаємо I=J.

Тепер мають місце два факти. По-перше, ключ (38), який спочатку знаходився в першій позиції, до цього часу займає належне місце в послідовності, що сортується. По-перше, всі ключі ліворуч від цього елемента будуть меншими, а всі ключі справа - більшими.

Ту ж процедуру можна застосувати до лівої та правої підпослідовностей для остаточного сортування всієї послідовності. Останній рядок (з номером 22) рис.15 показує, коли буде отримано I=J, то I=7. Після цього процедура знову застосовується до підпослідовностей (1,6) та (8,16).

Рекурсивний характер алгоритму наводить на думку, що слід значення індексів крайніх елементів більшої з двох невідсортованих підпослідовностей (8,16) помістити на стек і потім перейти до сортування меншої підпослідовності (1,6).

У рядку 4 на рис.15 число 04 перейшло в позицію 2 і підлягають сортуванню підпослідовності (1,1) і (3,6). Так як (1,1) вже відсортовано (число 02), сортуємо (3,6), що у свою чергу веде до рядка 6, в якому підлягають сортуванню (3,4) та (6,6). У рядку 7 підпослідовність (1,6) відсортована. Тепер витягаємо (8,16) зі стека і починаємо сортування цієї підпослідовності. У рядку 13 знаходяться підпослідовності (8,11) та (13,16), які треба відсортувати. Поміщаємо (13,16) на стік, сортуємо (8,11) і т.д. У рядку 20 послідовність повністю відсортована.

Перш ніж описати алгоритм QUICKSORT формально, потрібно точно показати, як він працює. Ми користуємося стеком [LEFT(K), RIGHT(K)] для запам'ятовування індексів крайніх лівого та правого елементів ще не відсортованих підпослідовностей. Так як короткі підпослідовності швидше сортуються за допомогою звичайного алгоритму, алгоритм QUICKSORT має вхідний параметр М, який визначає, наскільки короткою повинна бути підпослідовність, щоб її сортувати звичайним способом. Для цієї мети користуємося сортуванням простими включеннями (SIS).

Пошук

Тепер звернемося до дослідження деяких основних проблем, які стосуються пошуку інформації на структурах даних. Як і попередньому розділі, присвяченому сортування, будемо припускати, що вся інформація зберігається у записах, які можна ідентифікувати значеннями ключів, тобто. запису R i відповідає значення ключа, що позначається K i .

Припустимо, що у файлі розташовані випадковим чином записів N у вигляді лінійного масиву. Очевидним методом пошуку цього запису буде послідовний перегляд ключів. Якщо знайдено потрібний ключ, пошук закінчується успішно; в іншому випадку будуть переглянуті всі ключі, а пошук виявиться безуспішним. Якщо всі можливі порядки розташування ключів рівноймовірні, такий алгоритм вимагає O(N) основних операцій як у гіршому, так і в середньому випадках. Час пошуку можна зменшити, якщо попередньо впорядкувати файл за ключами. Ця попередня робота має сенс, якщо файл досить великий і до нього часто звертаються.

Припустимо, що ми звернулися до середини файлу і виявили ключ K i . Порівняємо К і К i. Якщо К=К i , то потрібний запис знайдено. Якщо До<К i ,то ключ К должен находиться в части файла, предшествующей К i (если запись с ключом К вообще существует) . Аналогично, если К i <К, то дальнейший поиск следует вести в части файла, следующей за К i . Если повторять эту процедуру проверки ключа К i из середины непросмотренной части файла, тогда каждое безуспешное сравнение К с К i будет исключать из рассмотрения приблизительно половину непросмотренной части.

Блок-схема цієї процедури, відомої під назвою двійковий пошук, наведена на рис.16

Algorithm BSEARCH (Binary search- двійковий пошук) пошуку запису з ключем До файлі з N≥2 записами, ключі яких упорядковані за зростанням До 1<К 2 …<К N .

Крок 0[Ініціалізація] Set FIRST←1; LAST← N. (FIRST і LAST- покажчики першого та останнього ключів у ще не переглянутій частині файлу.)

Крок 1.[Основний цикл] While LAST≥FIRST do throughкрок 4 od.

Крок 2[Отримання центрального ключа] Set I←|_(FIRST + LAST)/2_| .(До i - ключ, розташований у середині або ліворуч від середини ще не переглянутої частини файлу.)

Крок 3[Перевірка на успішне завершення] IfК=До I then PRINT «Успішне закінчення, ключ дорівнює ДО I»; and STOP fi.

Крок 4.[ Порівняння] If K < K I then set LAST←I-1 else set FIRST←I+1 fi.

Крок 5.[Безуспішний пошук] PRINT «безуспішно»; and STOP.

Алгоритм BSEARCH використовується для відшукання К = 42 на рис.17.

Метод бінарного пошуку можна також застосувати для того, щоб представити впорядкований файл у вигляді бінарного дерева. Значення ключа, знайдене за першого виконання кроку 2 (К(8)=53), є коренем дерева. Інтервали ключів зліва (1,7) та праворуч (9,16) від цього значення поміщаються на стек. Верхній інтервал знімається зі стека і за допомогою кроку 2 в ньому знаходиться середній елемент (або елемент зліва від середини). Цей ключ (К(4)=33) стає наступним після кореня елементом вліво, якщо його значення менше значення кореня, і наступним праворуч в іншому випадку. Підінтервали цього інтервалу праворуч і ліворуч від знову доданого ключа [(1,3) , (5,7)] поміщаються тепер на стек.Ця процедура повторюється до тих пір, поки стек не виявиться порожнім. На рис.18 показано двійкове дерево, яке було побудовано для 16 упорядкованих ключів з рис.17.

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

Сортування – це розташування даних у пам'яті в регулярному вигляді за вибраним параметром. Регулярність розглядають як зростання (зменшення) значення параметра від початку до кінця масиву даних.

При обробці даних важливо знати інформаційне поле даних та розміщення їх у машині.

Розрізняють внутрішнє та зовнішнє сортування:

Внутрішнє сортування – сортування в оперативній пам'яті;

Зовнішнє сортування – сортування у зовнішній пам'яті.

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

При сортуванні можуть трапитися однакові ключі. У цьому випадку бажано після сортування розташувати однакові ключі в тому самому порядку, що й у вихідному файлі.Це - стійке сортування.

Ми розглядатимемо лише сортування, які не використовують додаткову оперативну пам'ять. Такі сортування називаються "на тому ж місці".

Ефективність сортування можна розглядати за кількома критеріями:

Час, що витрачається на сортування;

Об'єм оперативної пам'яті, необхідної для сортування;

Час, витрачений програмістом написання програми.

Виділяємо перший критерій. Еквівалентом витраченого на сортування часу можна вважати кількість порівняньі кількість переміщеньпід час виконання сортування.

Порядок числа порівнянь та переміщень при сортуванні лежить у межах

Від (n log n) до (n 2);

Про (n) - ідеальний та недосяжний випадок.

Розрізняють такі методи сортування:

Суворі (прямі) методи;

Поліпшені методи.

Суворі методи:

метод прямого включення;

метод прямого вибору;

Метод прямого обміну.

Ефективність суворих методів приблизно однакова.

Сортування методом прямого включення

Елементи подумки діляться вже готову послідовність a 1 ,...,a i-1 і вихідну послідовність.

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

Суть алгоритму така:

for i = 2 to n

X = a(i)

Знаходимо місце серед а(1)…а(i) для включення х

next i

Існують два алгоритми сортування методом прямого включення. Перший – без бар'єру

Алгоритм сортування методом прямого включення без бар'єру

for i = 2 to n

X = a(i)

Для j = i - 1 до 1

If x< a(j)

Then a(j + 1) = a(j)

Else go to L

Endif

Next j

L: a(j + 1) = x

next i

return

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

Алгоритм сортування методом прямого включення з бар'єром

for i = 2 to n

X = a(i)

A(0) = x (a(0) - бар'єр)

J = i - 1

While x< a(j) do

A(j +1) = a(j)

J = j - 1

Endwhile

A(j +1) = x

next i

return

Ефективність алгоритму прямого включення

Число порівнянь ключів Ci при i-му просіюванні найбільше дорівнює i-1, найменше - 1; якщо припустити, що це перестановки з N ключів рівноймовірні, то середнє порівнянь = i/2. Число пересилок Mi = Ci +3 (включаючи бар'єр). Мінімальні оцінки зустрічаються у разі вже впорядкованої вихідної послідовності елементів, найгірші оцінки - коли вони спочатку розташовані у зворотному порядку. У певному сенсі сортування за допомогою включення демонструє природну поведінку. Зрозуміло, що наведений алгоритм описує процес стійкого сортування: порядок елементів із рівними ключами за нього залишається незмінним.

Кількість порівнянь у гіршому випадку, коли масив відсортований протилежним чином, max = n(n - 1)/2, тобто - про (n 2). Кількість перестановок Mmax = Cmax + 3(n-1), тобто. - Про (n 2). Якщо масив вже відсортований, то число порівнянь і перестановок мінімально: C min = n-1; M min = = 3 (n-1).

Сортування за допомогою прямого обміну (пухирцеве сортування)

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

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

C min = n - 1, порядок О(n),

а переміщення взагалі відсутні

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

Такий метод широко відомий під ім'ям "бульбашкове сортування".

Алгоритм методу прямого обміну

for j = n to i step -1

if a(j)< a(j - 1) then

У нашому випадку вийшов один прохід "вхолосту". Щоб зайвий раз не переглядати елементи, а отже, проводити порівняння, витрачаючи на цей час, можна ввести прапорець fl, що залишається у значенні false, якщо за черговому проході нічого очікувати зроблено жодного обміну. На наведеному нижче алгоритмі додавання позначені жирним шрифтом.

fl = true

if fl = false then return

fl = false

for j = n to i step -1

if a(j)< a(j - 1) then

fl = true

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

Ефективність алгоритму сортування прямим обміном

Число порівнянь C max = n(n-1)/2 порядок О(n 2).

Число переміщень М max =3C max =3n(n-1)/2, порядок О(n 2).

Якщо масив вже відсортований і застосовується алгоритм з прапорцем, достатньо всього одного проходу, і тоді отримуємо мінімальну кількість порівнянь

Такий метод широко використовується при грі в карти. Елементи (карти) подумки діляться вже «готову» послідовність A 1 , A 2 ,…, A i -1 , і «решту» (не сортовану) частина: A i , A i +1 ,…, A N .

Суть методу полягає в тому, що при кожному i-му кроці (починаючи з i = 2), з невідсортованої частини витягується i-ий елемент і поміщається в «готову» частину, при цьому він вставляється на потрібне місце.

Текстовий алгоритм методу:

1. Початок.

2. Виконати цикл, доки i має значення від 2 до N,
крок = 1:

а) i-ий елемент (A(i)) помістити в комірку A(0);

б) присвоїти j = -1, тобто j дорівнює номеру елемента, що знаходиться ліворуч від випробуваного (i-го) і таким чином стоїть у «готовій» послідовності;

в) якщо А(0) ≥ А(j), то елемент А(0) помістити в комірку А(j+1), інакше елемент А(j) помістити в комірку А(j+1), зменшити значення j на одиницю та знову виконати пункт в).

На рис. 1 представлена ​​блок-схема сортування методом прямого включення.

Метод працює наступним чином: на i-му кроці (починаючи з i = 2) i-ий елемент поміщається у вільну комірку (наприклад, А(0)). Цей елемент порівнюється з елементом, що стоїть у «готовій» частині зліва від нього. Якщо елемент А(0) менше, відбувається зрушення вправо порівнюваного (j-го елемента) на одну позицію, після чого для порівняння береться наступний елемент. Якщо ж елемент А(0) при порівнянні виявляється не менше, він поміщається на місце, що стоїть відразу за порівнюваним елементом.

Мал. 1. Блок-схема сортування методом прямого включення

На рис. 2 наведено приклад виконання сортування методом прямого включення.

Початкова послідовність
	А (0)
I = 2
I = 3
I = 4
I = 5
I = 6
I = 7
I = 8
Результат

Мал. 2. Приклад сортування методом прямого включення

Сортування прямим включенням більше підходить для випадку, коли дані, що сортуються, надходять послідовно (одно за іншим).

Сортування методом прямого вибору

Суть методу ось у чому. Вибирається найменший елемент в частині, що «залишилася» (невідсортованої) і змінюється місцями з першим елементом (у цій же невідсортованій частині). Після цього довжина невідсортованої частини зменшується на один елемент (на перший), і весь процес триває вже з (n – 1) елементами, потім (n – 2) елементами і т.д., доки не залишиться один, найбільший елемент.

Цей метод у сенсі протилежний методу прямого включення. У методі прямого включення кожному кроці розглядається лише одне черговий елемент і всі елементи вже «готової» частини послідовності, серед яких знаходиться точка включення цього чергового елемента. А в методі прямого вибору для пошуку одного (мінімального) елемента переглядають усі елементи невідсортованої частини, і цей мінімальний елемент міститься як черговий елемент у вже готову частину.

Текстовий алгоритм методу:

1. Початок.

2. Виконати цикл, доки i має значення від 1 до N – 1,
крок = 1:

а) помістимо поточний (i-ий) елемент у якусь комірку пам'яті (Х) і запам'ятаємо порядковий номер (i) поточного елемента (у змінній К);

б) виконати цикл, доки j має значення від i + 1 (тобто від наступного за i елемента) до N, крок = +1:

тіло циклу: якщо Х > А(j), то поміщаємо в комірку Х елемент А(j) та запам'ятовуємо його номер у комірці К;

в) присвоїти А(К) = А(i) та А(i) = Х.

На рис. 3 наведено приклад виконання сортування методом прямого вибору.

Початкова послідовність	44						06
I = 1		55	12
I = 2			55			18
I = 3				42		55
I = 4					94		44
I = 5						55	94
I = 6							94	67
I = 7

Мал. 3. Приклад сортування методом прямого вибору