Меню

Сортування вставки в C ++ із прикладами

insertion sort c with examples

Спробуйте Наш Інструмент Для Усунення Проблем

Поглиблений погляд на сортування вставки на класичних прикладах.

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

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

=> Ознайомтеся з найкращими навчальними посібниками з C ++ тут.

СОРТ ВСТАВКИ

Що ви дізнаєтесь:

Огляд

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

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

найкращий відеоконвертер для Windows 7

Зв’язані списки мають вказівник на наступний елемент (у разі однопов’язаного списку), а також вказівник на попередній елемент (у разі подвійного пов’язаного списку). Отже, стає простіше впровадити сортування вставки для пов'язаного списку.

Давайте вивчимо все про сортування вставки в цьому посібнику.

Загальний алгоритм

Крок 1 : Повторіть кроки 2 - 5 для K = 1 - N-1
Крок 2 : встановити температуру = A (K)
Крок 3 : встановити J = K - 1
Крок 4 : Повторювати під час темп<=A(J)
встановити A (J + 1) = A (J)
встановити J = J - 1
(кінець внутрішнього циклу)
Крок 5 : встановити A (J + 1) = темп
(кінець циклу)
Крок 6 : вихід

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

Псевдокод

Псевдо-код для сортування вставки наведено нижче.

procedure insertionSort(array,N ) array – array to be sorted N- number of elements begin int freePosition int insert_val for i = 1 to N -1 do: insert_val = array(i) freePosition = i //locate free position to insert the element whilefreePosition> 0 and array(freePosition -1) >insert_val do: array (freePosition) = array (freePosition -1) freePosition = freePosition -1 end while //insert the number at free position array (freePosition) = insert_val end for end procedure

Вище наведено псевдо-код для сортування вставки, далі ми проілюструємо цей спосіб у наступному прикладі.

Ілюстрація

Масив для сортування має такий вигляд:

масив для сортування

Тепер для кожного проходу ми порівнюємо поточний елемент з усіма його попередніми елементами. Отже, під час першого проходу ми починаємо з другого елемента.

Сортування вставки - ілюстрація

Таким чином, нам потрібно N кількість проходів, щоб повністю сортувати масив, що містить N кількість елементів.

Наведену ілюстрацію можна узагальнити у табличній формі:

ПройтиНесортований списокпорівнянняВідсортований список
один{12,3,5,10,8,1}{12.3}{3,12,5,10,8,1}
два{3,12,5,10,8,1}{3,12,5}{3,5,12,10,8,1}
3{3,5,12,10,8,1}{3,5,12,10}{3,5,10,12,8,1}
4{3,5,10,12,8,1}{3,5,10,12,8}{3,5,8,10,12,1}
5{3,5,8,10,12,1}{3,5,8,10,12,1}{1,3,5,8,10,12}
6{}{}{1,3,5,8,10,12}

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

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

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

Далі ми продемонструємо реалізацію техніки сортування вставки мовою С ++.

Приклад С ++

#include using namespace std; int main () { int myarray(10) = { 12,4,3,1,15,45,33,21,10,2}; cout<<' Input list is '; for(int i=0;i<10;i++) { cout <

Вихід:

Список вводу:

12 4 3 1 15 45 33 21 10 2

як запустити торрентований файл -

Відсортований список -

1 2 3 4 10 12 15 21 33 45

Далі ми побачимо реалізацію Java техніки сортування Insertion.

Приклад Java

public class Main { public static void main(String() args) { int() myarray = {12,4,3,1,15,45,33,21,10,2}; System.out.println('Input list of elements ...'); for(int i=0;i<10;i++) { System.out.print(myarray(i) + ' '); } for(int k=1; k=0 && temp <= myarray(j)) { myarray(j+1) = myarray(j); j = j-1; } myarray(j+1) = temp; } System.out.println(' sorted list of elements ...'); for(int i=0;i<10;i++) { System.out.print(myarray(i) + ' '); } } }

Вихід:

Вхідний список елементів…

12 4 3 1 15 45 33 21 10 2

відсортований список елементів ...

1 2 3 4 10 12 15 21 33 45

В обох реалізаціях ми бачимо, що розпочинаємо сортування з 2йелемент масиву (змінна циклу j = 1) і неодноразово порівнюйте поточний елемент з усіма його попередніми елементами, а потім сортуйте елемент, щоб розмістити його у правильному положенні, якщо поточний елемент не в порядку з усіма його попередніми елементами.

Сортування вставки працює найкраще і може бути виконане за меншу кількість проходів, якщо масив частково відсортований. Але по мірі збільшення списку його продуктивність зменшується. Ще однією перевагою Insertion sort є те, що це стабільний сорт, що означає, що він підтримує порядок рівних елементів у списку.

Аналіз складності алгоритму сортування вставки

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

Однак навіть якщо ми передаємо відсортований масив техніці Insertion sort, він все одно виконає зовнішній цикл for, вимагаючи n кількості кроків для сортування вже відсортованого масиву. Це робить найкращу за часом складність вставки сортуванням лінійною функцією N, де N - кількість елементів у масиві.

Таким чином, різні складності для техніки сортування вставки наведені нижче:

Найгірша складність часуO (n 2)
Найкраща складність часуO (n)
Середня часова складністьO (n 2)
Складність просторуO (1)

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

Висновок

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

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

реалізація алгоритму найкоротшого шляху Дейкстри в Java

У нашому майбутньому уроці ми обговоримо “Сортування оболонки”, що є покращенням порівняно із сортуванням “Вибір”.

У сортуванні оболонки ми вводимо змінну, відому як «приріст» або «розрив», за допомогою якої ми ділимо список на підсписки, що містять несуміжні елементи, що «розрив» один від одного. Сортування оболонки вимагає менше проходів у порівнянні з сортуванням вставки, а також швидше.

У наших майбутніх навчальних посібниках ми дізнаємося про дві техніки сортування, “Quicksort” та “Mergesort”, які використовують стратегію “Розділяй і володарюй” для сортування списків даних.

=> Зверніть увагу на навчальний посібник для початківців C ++ тут.

Рекомендована література

^