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

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

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 при спробі відшукання До.

Так

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

Сортування цим методом проводиться послідовно крок за кроком. на k-м кроку вважається, що частина масиву, що містить перші k- 1 елемент, вже впорядкований, тобто .

Далі потрібно взяти k-й елемент і підібрати для нього місце у відсортованій частині масиву таке, щоб після його вставки впорядкованість не порушилася, тобто треба знайти таке що. Потім потрібно вставити елемент a(k)на знайдене місце.

З кожним кроком відсортована частина масиву зростає. Для виконання повного сортування потрібно виконати n- 1 крок.

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

Знайдено елемент, що говорить про необхідність вставки хміж і а(j).

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

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

Методику сортування ілюструє таблиця 2:

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

Спочатку впорядкована послідовність складається з 1 елемента 9. Елемент а( 2) =5 – перший із невпорядкованої послідовності та 5< 9, поэтому ставится на его место, а 9 сдвигается вправо. Теперь упорядоченная последовательность состоит из двух элементов 5, 9. Элемент а( 3) =15 неупорядкованої послідовності більше всіх елементів упорядкованої послідовності, тому залишається на своєму місці і на наступному кроці впорядкована послідовність складається з 5, 9, 15, а елемент 6, що розглядається. Процес відбувається до тих пір, поки послідовність не стане впорядкованою.

Шейкерне сортування

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

На цих спостереженнях заснований метод шейкерного сортування (ShakerSort). При його застосуванні на кожному наступному кроці змінюється напрямок послідовного перегляду. В результаті на одному кроці "спливає" черговий найлегший елемент, а на іншому "тоне" черговий найважчий. Приклад шейкерного сортування наведено у таблиці 3.

Таблиця 3 – Приклад шейкерного сортування

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

Д. Шеллом було запропоновано удосконалення сортування за допомогою прямого включення.

Ідея методу: всі елементи масиву розбиваються на групи таким чином, що до кожної групи входять елементи, що віддаляються один від одного на деяку кількість позицій L. Елементи кожної групи сортуються. Після цього всі елементи знову об'єднуються та сортуються у групах, при цьому відстань між елементами зменшується. Процес закінчується після того, як буде проведено впорядкування елементів з відстанню між ними, що дорівнює 1.

Приклад сортування методом Шелла наведено у таблиці 4.

Таблиця 4 – Приклад сортування методом Шелла

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

Сортування поділом (швидке сортування)

Метод сортування поділом було запропоновано Чарльзом Хоаром. Цей метод є розвитком методу простого обміну і настільки ефективний, що його стали називати методом швидкого сортування Quicksort.

Основна ідея алгоритму полягає в тому, що випадково вибирається певний елемент масиву x, після чого масив проглядається зліва, доки не зустрінеться елемент a(i)такий, що a(i) > x, а потім масив проглядається праворуч, доки не зустрінеться елемент a(i)такий, що a(i)< x. Ці два елементи змінюються місцями, і процес перегляду, порівняння та обміну продовжується, поки ми не дійдемо до елемента x. В результаті масив виявиться розбитим на дві частини - ліву, в якій значення ключів будуть меншими. x, і праву зі значеннями ключів, більшими x. Далі процес рекурсивно продовжується для лівої та правої частин масиву доти, доки кожна частина не міститиме точно один елемент. Рекурсію можна замінити на ітерації, якщо запам'ятовувати відповідні індекси масиву.

Процес сортування масиву швидким методом представлено таблиці 5.

Таблиця 5 – Приклад швидкого сортування

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

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

а ≤ а ≤ ... ≤ a .

Далі необхідно взяти k - й елемент і підібрати для нього таке місце у відсортованій частині масиву, щоб після його вставки впорядкованість не порушувалася, тобто треба знайти таке j (1 ≤ j ≤ k -1), що [j] ≤ a [ k]< a. Затем вставить элемент а [k] на найденное место.

З кожним кроком відсортована частина масиву зростає. Для виконання повного сортування потрібно виконати n-1 крок.

Розглянемо цей процес з прикладу. Нехай потрібно відсортувати масив із 10 елементів за зростанням методом прямого включення

1 - й крок

13 6 8 11 3 1 5 9 15 7 Розглядаємо частину масиву з одного еле-

менту (13). Потрібно вставити до неї другий

елемент масиву (6) так, щоб упорядкований-

ність збереглася. Оскільки 6< 13, вставляем

6 перше місце. Відсортована частина

масиву містить два елементи (6 13).

3 - й крок

6 8 13 11 3 1 5 9 15 7 Наступний елемент - 11. Він записується в упорядковану частину масиву на третє місце, оскільки 11 > 8 але 11< 13.

5- крок

3 6 8 11 13 1 5 9 15 7 З тієї ж причини 1 записуємо на перше

6 - крок

1 3 6 8 11 13 5 9 15 7 Оскільки 5 > 3, але 5< 6 то место 5 в упоря-

Доченої частини – третє.

7 -крок

1 3 5 6 8 11 13 9 15 7 Місце числа 9 – шосте.

8 -крок

1 3 5 6 8 9 11 13 15 7 Визначаємо місце для передостаннього

Елементу 15. Виявляється, що цей еле-

мент масиву вже знаходиться на своєму місці.

9 -крок

1 3 5 6 8 9 11 13 15 7 Залишилося підібрати відповідне місце для

Останній елемент (7).

1 3 5 6 7 8 9 11 13 15 Масив повністю відсортований.

Нині можна коротко описати фрагмент алгоритму сортування методом прямого включення:

Для: = 2 To n Do

(оскільки починаємо сортування з пошуку відповідного місця для a, i змінюється від 2 до n)

'вставити x на потрібне місце в a, ..., a[k] '

Залишилося відповісти на питання, як здійснити пошук потрібного місця для елемента x. Вчинимо так: переглядатимемо елементи, розташовані лівіше x (тобто ті, які вже впорядковані), рухаючись до початку масиву. Потрібно переглядати елементи a[ j ] , j змінюється від k-1 до 1. Такий перегляд має закінчитися при виконанні однієї з наступних умов:

· Знайдений елемент a [j]< x, что говорит о необходимости вставки x между a и a[j].

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

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

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

program n3; ( Сортування за спаданням )

type ar=array of integer;

procedure sorting3(var a: ar);

var i,j,x,k:integer;

for k:=2 to n do

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

while (j>0)and(x>=a[j]) do

writeln("Введіть вихідний масив:");

для i:=1 до n до read(a[i]);

writeln("Відсортований масив:");

for i:=1 to n do write(a[i]," ");

Такий метод широко використовується при грі в карти. Елементи (карти) подумки діляться вже «готову» послідовність 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. Приклад сортування методом прямого вибору