În acest articol, vom discuta despre algoritmul de sortare prin inserare. Procedura de lucru a sortării inserției este, de asemenea, simplă. Acest articol va fi foarte util și interesant pentru studenți, deoarece aceștia s-ar putea confrunta cu sortarea de inserare ca întrebare în examenele lor. Deci, este important să discutăm subiectul.

Sortarea prin inserare funcționează similar cu sortarea cărților de joc în mâini. Se presupune că prima carte este deja sortată în jocul de cărți, apoi selectăm o carte nesortată. Dacă cardul nesortat selectat este mai mare decât primul card, acesta va fi plasat în partea dreaptă; în caz contrar, va fi plasat în partea stângă. În mod similar, toate cărțile nesortate sunt luate și puse la locul lor exact.

Aceeași abordare este aplicată în sortarea prin inserție. Ideea din spatele sortării prin inserție este că mai întâi luați un element, repetați-l prin matricea sortată. Deși este simplu de utilizat, nu este adecvat pentru seturi mari de date, deoarece complexitatea de timp a sortării inserției în cazul mediu și cel mai rău caz este Pe²) , unde n este numărul de elemente. Sortarea prin inserare este mai puțin eficientă decât ceilalți algoritmi de sortare, cum ar fi sortarea heap, sortarea rapidă, sortarea prin îmbinare etc.

Sortarea prin inserție are diverse avantaje, cum ar fi -

• Implementare simplă
• Eficient pentru seturi mici de date
• Adaptiv, adică este adecvat pentru seturile de date care sunt deja sortate în mod substanțial.

Acum, să vedem algoritmul de sortare prin inserție.

Algoritm

Pașii simpli pentru realizarea sortării prin inserare sunt enumerați după cum urmează -

Pasul 1 - Dacă elementul este primul element, presupuneți că este deja sortat. Retur 1.

in.next java

Pasul 2 - Alegeți următorul element și depozitați-l separat într-un cheie.

Pasul 3 - Acum, comparați cheie cu toate elementele din tabloul sortat.

Pasul 4 - Dacă elementul din matricea sortată este mai mic decât elementul curent, atunci treceți la următorul element. În caz contrar, deplasați elementele mai mari din matrice spre dreapta.

Pasul 5 - Introduceți valoarea.

Pasul 6 - Repetați până când matricea este sortată.

Funcționarea algoritmului de sortare prin inserție

Acum, să vedem funcționarea algoritmului de sortare a inserției.

Pentru a înțelege funcționarea algoritmului de sortare prin inserție, să luăm o matrice nesortată. Va fi mai ușor de înțeles sortarea prin inserare printr-un exemplu.

Fie elementele matricei sunt -

Inițial, primele două elemente sunt comparate în sortare de inserție.

Aici, 31 este mai mare decât 12. Asta înseamnă că ambele elemente sunt deja în ordine crescătoare. Deci, pentru moment, 12 este stocat într-o sub-matrice sortată.

Acum, treceți la următoarele două elemente și comparați-le.

Aici, 25 este mai mic decât 31. Deci, 31 nu este în poziția corectă. Acum, schimbați 31 cu 25. Împreună cu schimbarea, sortarea prin inserare o va verifica și cu toate elementele din tabloul sortat.

Deocamdată, matricea sortată are un singur element, adică 12. Deci, 25 este mai mare decât 12. Prin urmare, matricea sortată rămâne sortată după schimbare.

Acum, două elemente din matricea sortată sunt 12 și 25. Deplasați-vă la următoarele elemente care sunt 31 și 8.

Atât 31, cât și 8 nu sunt sortate. Deci, schimbă-le.

După schimbare, elementele 25 și 8 sunt nesortate.

Deci, schimbă-le.

Acum, elementele 12 și 8 sunt nesortate.

Deci, schimbă-le și tu.

Acum, matricea sortată are trei elemente care sunt 8, 12 și 25. Treceți la următoarele elemente care sunt 31 și 32.

Prin urmare, sunt deja sortate. Acum, matricea sortată include 8, 12, 25 și 31.

Treceți la următoarele elemente care sunt 32 și 17.

17 este mai mic decât 32. Deci, schimbați-le.

Schimbarea face ca 31 și 17 să nu fie sortate. Deci, schimbă-le și tu.

Acum, schimbul face ca 25 și 17 să nu fie sortate. Deci, efectuați schimbul din nou.

Acum, matricea este complet sortată.

Complexitatea sortării inserției

Acum, să vedem complexitatea de timp a sortării inserției în cel mai bun caz, în cazul mediu și în cel mai rău caz. Vom vedea, de asemenea, complexitatea spațială a sortării inserției.

1. Complexitatea timpului

Complexitatea celui mai bun caz -Apare atunci când nu este necesară sortarea, adică matricea este deja sortată. Cel mai bun caz complexitatea de timp a sortării de inserare este Pe) .Complexitatea medie a cazului -Apare atunci când elementele matricei sunt într-o ordine amestecată care nu este corect ascendentă și nu este corect descendentă. Complexitatea medie a timpului de caz a sortării de inserare este Pe²) .Complexitatea celui mai rău caz -Apare atunci când elementele matricei trebuie să fie sortate în ordine inversă. Aceasta înseamnă să presupunem că trebuie să sortați elementele matricei în ordine crescătoare, dar elementele sale sunt în ordine descrescătoare. Cel mai rău caz complexitatea timpului de sortare a inserției este Pe²) .

2. Complexitatea spațială

• Complexitatea spațială a sortării de inserție este O(1). Se datorează faptului că, în sortarea prin inserție, este necesară o variabilă suplimentară pentru schimbare.

Implementarea sortării prin inserare

Acum, să vedem programele de sortare de inserare în diferite limbaje de programare.

Program: Scrieți un program pentru a implementa sortarea prin inserare în limbajul 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 &amp;&amp; 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 &gt;= 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 &amp;&amp; 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 &amp;&amp; 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 &amp;&amp; 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>&apos;; printArray($a); for ($i = 1; $i = 0 &amp;&amp; $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>&apos;; printArray($a); ?&gt; </=></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&apos;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&apos;s complexity, working, and implementation in different programming languages.</p> <hr></=></n;></pre></=></n;></pre></=></n;></pre></a[j]></pre></=></n;>

Ieșire:

Deci, asta e totul despre articol. Sper că articolul vă va fi util și informativ.

Acest articol nu sa limitat doar la algoritm. De asemenea, am discutat despre complexitatea, funcționarea și implementarea algoritmului în diferite limbaje de programare.