У цій статті ми обговоримо алгоритм сортування вставкою. Робоча процедура сортування вставкою також проста. Ця стаття буде дуже корисною та цікавою для студентів, оскільки вони можуть зіткнутися зі вставкою як запитання під час своїх іспитів. Тому важливо обговорити тему.
Сортування за допомогою вставки працює подібно до сортування гральних карт у руках. Передбачається, що перша карта вже відсортована в картковій грі, а потім ми вибираємо невідсортовану картку. Якщо вибрана несортована картка більша за першу, вона буде розміщена праворуч; інакше він буде розміщено зліва. Подібним чином усі несортовані картки беруться та кладуться на своє місце.
Той самий підхід застосовано до сортування вставкою. Ідея сортування вставкою полягає в тому, що спочатку візьміть один елемент і повторіть його через відсортований масив. Незважаючи на те, що він простий у використанні, він не підходить для великих наборів даних, оскільки часова складність сортування вставки в середньому та гіршому випадку становить O(n2) , де n – кількість предметів. Сортування за допомогою вставки є менш ефективним, ніж інші алгоритми сортування, такі як сортування купи, швидке сортування, сортування злиттям тощо.
Сортування вставлення має ряд переваг, таких як:
- Проста реалізація
- Ефективно для невеликих наборів даних
- Адаптивний, тобто підходить для наборів даних, які вже значною мірою відсортовані.
Тепер розглянемо алгоритм сортування вставкою.
Алгоритм
Нижче наведено прості кроки для досягнення сортування вставкою:
Крок 1 - Якщо елемент є першим елементом, припустимо, що він уже відсортований. Повернення 1.
картинки з icloud на android
Крок 2 - Виберіть наступний елемент і збережіть його окремо в a ключ.
крок 3 - Тепер порівняйте ключ з усіма елементами в сортованому масиві.
Крок 4 - Якщо елемент у відсортованому масиві менший за поточний елемент, перейдіть до наступного елемента. Інакше перемістіть більші елементи в масиві вправо.
Крок 5 - Вставте значення.
Крок 6 - Повторюйте, доки масив не буде відсортований.
Робота алгоритму сортування вставкою
Тепер давайте подивимося, як працює алгоритм сортування вставкою.
Щоб зрозуміти роботу алгоритму сортування вставкою, візьмемо невідсортований масив. Зрозуміти сортування вставкою буде легше на прикладі.
Нехай елементи масиву -
Спочатку перші два елементи порівнюються під час сортування вставкою.
Тут 31 більше за 12. Це означає, що обидва елементи вже в порядку зростання. Отже, наразі 12 зберігається у відсортованому підмасиві.
Тепер перейдіть до наступних двох елементів і порівняйте їх.
Тут 25 менше, ніж 31. Отже, 31 не в правильному положенні. Тепер поміняйте місцями 31 на 25. Разом із заміною, сортування вставкою також перевірить його з усіма елементами в сортованому масиві.
Наразі відсортований масив має лише один елемент, тобто 12. Отже, 25 більше за 12. Отже, відсортований масив залишається відсортованим після заміни.
Тепер у відсортованому масиві два елементи — 12 і 25. Перейдіть до наступних елементів — 31 і 8.
І 31, і 8 не сортуються. Отже, поміняйте їх.
Після заміни елементи 25 і 8 не сортуються.
Отже, поміняйте їх.
Тепер елементи 12 і 8 не відсортовані.
Тож поміняйте їх теж.
Тепер відсортований масив містить три елементи: 8, 12 і 25. Перейдіть до наступних елементів, які мають номери 31 і 32.
Отже, вони вже відсортовані. Тепер відсортований масив включає 8, 12, 25 і 31.
Перейдіть до наступних елементів 32 і 17.
17 менше, ніж 32. Отже, поміняйте їх місцями.
Обмін робить 31 і 17 несортованими. Тож поміняйте їх теж.
Тепер заміна робить 25 і 17 несортованими. Отже, знову виконайте обмін.
Тепер масив повністю відсортований.
Складність сортування вставкою
Тепер давайте подивимося на часову складність сортування вставки в найкращому, середньому випадку та в гіршому випадку. Ми також побачимо просторову складність сортування вставкою.
1. Складність часу
| Справа | Складність часу |
|---|---|
| Кращий випадок | O(n) |
| Середній випадок | O(n2) |
| Найгірший випадок | O(n2) |
2. Просторова складність
| Космічна складність | O(1) |
| Стабільний | ТАК |
- Просторова складність сортування вставкою дорівнює O(1). Це тому, що при сортуванні вставкою потрібна додаткова змінна для заміни.
Реалізація сортування вставкою
Тепер давайте подивимося на програми сортування вставкою на різних мовах програмування.
програма: Напишіть програму для реалізації сортування вставкою мовою C.
#include void insert(int a[], int n) /* function to sort an aay with insertion sort */ { int i, j, temp; for (i = 1; i <n; i++) { temp="a[i];" j="i" - 1; while(j>=0 && temp <= 17 a[j]) * move the elements greater than temp to one position ahead from their current position* { a[j+1]="a[j];" j="j-1;" } void printarr(int a[], int n) function print array i; for (i="0;" i < n; i++) printf('%d ', a[i]); main() a[]="{" 12, 31, 25, 8, 32, }; n="sizeof(a)" sizeof(a[0]); printf('before sorting are -
'); printarr(a, n); insert(a, printf('
after return 0; pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-18.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in python.</p> <pre> def insertionSort(a): # Function to implement insertion sort for i in range(1, len(a)): temp = a[i] # Move the elements greater than temp to one position #ahead from their current position j = i-1 while j >= 0 and temp <a[j] : a[j + 1]="a[j]" j="j-1" def printarr(a): # function to print the array for i in range(len(a)): (a[i], end=" " ) a="[70," 15, 2, 51, 60] print('before sorting elements are - ') printarr(a) insertionsort(a) print('
after < pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-19.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in C++ language.</p> <pre> #include using namespace std; void insert(int a[], int n) /* function to sort an aay with insertion sort */ { int i, j, temp; for (i = 1; i <n; i++) { temp="a[i];" j="i" - 1; while(j>=0 && temp <= 2 a[j]) * move the elements greater than temp to one position ahead from their current position* { a[j+1]="a[j];" j="j-1;" } void printarr(int a[], int n) function print array i; for (i="0;" i < n; i++) cout << a[i] <<' '; main() a[]="{" 89, 45, 35, 8, 12, }; n="sizeof(a)" sizeof(a[0]); cout<<'before sorting are - '<<endl; printarr(a, n); insert(a, cout<<'
after return 0; pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-20.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in C# language.</p> <pre> using System; class Insertion { static void insert(int[] a) /* function to sort an aay with insertion sort */ { int i, j, temp; int n = a.Length; for (i = 1; i <n; i++) { temp="a[i];" j="i" - 1; while(j>=0 && temp <= 12 a[j]) * move the elements greater than temp to one position ahead from their current position* { a[j+1]="a[j];" j="j-1;" } static void printarr(int[] a) function print array int i; n="a.Length;" for (i="0;" i < n; i++) console.write(a[i] + ' '); main() int[] a="{" 98, 54, 53, 18, 21, }; console.write('before sorting are -
'); printarr(a); insert(a); console.write('
after pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-21.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in Java.</p> <pre> public class Insert { void insert(int a[]) /* function to sort an aay with insertion sort */ { int i, j, temp; int n = a.length; for (i = 1; i <n; i++) { temp="a[i];" j="i" - 1; while(j>=0 && temp <= 22 a[j]) * move the elements greater than temp to one position ahead from their current position* { a[j+1]="a[j];" j="j-1;" } void printarr(int a[]) function print array int i; n="a.length;" for (i="0;" i < n; i++) system.out.print(a[i] + ' '); public static main(string[] args) a[]="{" 92, 50, 5, 20, 11, }; insert i1="new" insert(); system.out.println('
before sorting are - i1.printarr(a); i1.insert(a); system.out.println('
after system.out.println(); pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-22.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in PHP.</p> <pre> <?php $a = array( 92, 50, 5, 20, 11, 22 ); function printArray($a) { for($i = 0; $i < 6; $i++) { print_r($a[$i]); echo ' '; } } echo 'Before sorting array elements are - <br>'; printArray($a); for ($i = 1; $i = 0 && $temp <= $a[$j]) * move the elements greater than temp to one position ahead from their current position* { $a[$j+1]="$a[$j];" $j="$j-1;" } echo ' <br> After sorting array elements are - <br>'; printArray($a); ?> </=></pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-23.webp" alt="Insertion Sort Algorithm"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the algorithm's complexity, working, and implementation in different programming languages.</p> <hr></=></n;></pre></=></n;></pre></=></n;></pre></a[j]></pre></=></n;> Вихід:
Отже, це все про статтю. Сподіваюся, стаття буде для вас корисною та інформативною.
Ця стаття не обмежилася лише алгоритмом. Ми також обговорили складність алгоритму, роботу та реалізацію на різних мовах програмування.