В тази статия ще обсъдим алгоритъма за сортиране чрез вмъкване. Работната процедура за сортиране на вмъкване също е проста. Тази статия ще бъде много полезна и интересна за студентите, тъй като те може да се сблъскат с вмъкване като въпрос на своите изпити. Така че е важно да обсъдим темата.
Сортирането чрез вмъкване работи подобно на сортирането на карти за игра в ръце. Предполага се, че първата карта вече е сортирана в играта с карти и след това избираме несортирана карта. Ако избраната несортирана карта е по-голяма от първата карта, тя ще бъде поставена от дясната страна; в противен случай ще бъде поставен от лявата страна. По същия начин всички несортирани карти се вземат и поставят на точното им място.
Същият подход се прилага при сортиране чрез вмъкване. Идеята зад сортирането чрез вмъкване е, че първо вземете един елемент, итерирайте го през сортирания масив. Въпреки че е лесен за използване, той не е подходящ за големи набори от данни, тъй като времевата сложност на сортирането на вмъкване в средния и най-лошия случай е На2) , където n е броят на елементите. Сортирането чрез вмъкване е по-малко ефективно от другите алгоритми за сортиране като сортиране на купчина, бързо сортиране, сортиране чрез сливане и т.н.
Сортирането чрез вмъкване има различни предимства като -
- Просто изпълнение
- Ефективен за малки набори от данни
- Адаптивен, т.е. подходящ е за набори от данни, които вече са значително сортирани.
Сега нека видим алгоритъма за сортиране при вмъкване.
Алгоритъм
Простите стъпки за постигане на сортиране на вмъкване са изброени, както следва -
Етап 1 - Ако елементът е първият елемент, приемете, че вече е сортиран. Връщане 1.
не е равно на mysql
Стъпка 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. Времева сложност
| Случай | Времева сложност |
|---|---|
| Най-добър случай | На) |
| Среден случай | На2) |
| Най-лошия случай | На2) |
2. Космическа сложност
| Космическа сложност | О(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;> Изход:
И така, това е всичко за статията. Надяваме се, че статията ще ви бъде полезна и информативна.
Тази статия не беше ограничена само до алгоритъма. Ние също така обсъдихме сложността на алгоритъма, работата и изпълнението на различни езици за програмиране.