SORTIRANJE UMETANJEM - VODIČ ZA DS

U ovom ćemo članku raspravljati o algoritmu sortiranja umetanjem. Radni postupak sortiranja umetanjem je također jednostavan. Ovaj će članak biti vrlo koristan i zanimljiv studentima jer bi se mogli suočiti s umetanjem kao pitanjem na svojim ispitima. Dakle, važno je razgovarati o temi.

Sortiranje umetanjem funkcionira slično kao sortiranje igraćih karata u rukama. Pretpostavlja se da je prva karta već sortirana u kartaškoj igri, a zatim odabiremo nesortiranu kartu. Ako je odabrana nerazvrstana karta veća od prve karte, bit će postavljena na desnu stranu; u suprotnom, bit će postavljen na lijevu stranu. Slično, sve nerazvrstane karte se uzimaju i stavljaju na svoje točno mjesto.

Isti pristup primjenjuje se u sortiranju umetanjem. Ideja koja stoji iza sortiranja umetanjem je da prvo uzmete jedan element, ponovite ga kroz sortirani niz. Iako je jednostavan za korištenje, nije prikladan za velike skupove podataka jer je vremenska složenost sortiranja umetanjem u prosječnom i najgorem slučaju Na²) , gdje je n broj stavki. Sortiranje umetanjem manje je učinkovito od ostalih algoritama sortiranja kao što su heap sortiranje, brzo sortiranje, sortiranje spajanjem itd.

Sortiranje umetanjem ima razne prednosti kao što su -

Jednostavna implementacija
Učinkovito za male skupove podataka
Prilagodljiv, tj. prikladan je za skupove podataka koji su već uvelike sortirani.

Sada, da vidimo algoritam sortiranja umetanjem.

Algoritam

Jednostavni koraci za postizanje sortiranja umetanjem navedeni su kako slijedi -

Korak 1 - Ako je element prvi element, pretpostavimo da je već sortiran. Povratak 1.

in.sljedeća java

Korak 2 - Odaberite sljedeći element i pohranite ga zasebno u a ključ.

Korak 3 - Sada usporedite ključ sa svim elementima u sortiranom nizu.

Korak 4 - Ako je element u sortiranom nizu manji od trenutnog elementa, prijeđite na sljedeći element. Inače, pomaknite veće elemente u nizu udesno.

Korak 5 - Unesite vrijednost.

Korak 6 - Ponavljajte dok se niz ne sortira.

Rad algoritma sortiranja umetanjem

Sada, da vidimo kako radi algoritam sortiranja umetanjem.

Da bismo razumjeli rad algoritma sortiranja umetanjem, uzmimo nesortirani niz. Lakše ćete razumjeti sortiranje umetanjem putem primjera.

Neka su elementi niza -

U početku se prva dva elementa uspoređuju u sortiranju umetanjem.

Ovdje je 31 veće od 12. To znači da su oba elementa već u rastućem redoslijedu. Dakle, za sada je 12 pohranjeno u sortiranom podnizu.

Sada prijeđite na sljedeća dva elementa i usporedite ih.

Ovdje je 25 manje od 31. Dakle, 31 nije u ispravnom položaju. Sada zamijenite 31 s 25. Uz zamjenu, sortiranje umetanjem također će ga provjeriti sa svim elementima u sortiranom nizu.

Za sada sortirani niz ima samo jedan element, tj. 12. Dakle, 25 je veće od 12. Dakle, sortirani niz ostaje sortiran nakon zamjene.

Sada, dva elementa u sortiranom nizu su 12 i 25. Prijeđite na sljedeće elemente koji su 31 i 8.

I 31 i 8 nisu razvrstani. Dakle, zamijenite ih.

Nakon zamjene, elementi 25 i 8 su nerazvrstani.

Dakle, zamijenite ih.

Sada, elementi 12 i 8 nisu razvrstani.

Dakle, zamijenite i njih.

Sada sortirani niz ima tri stavke koje su 8, 12 i 25. Prijeđite na sljedeće stavke koje su 31 i 32.

Dakle, oni su već sortirani. Sada sortirani niz uključuje 8, 12, 25 i 31.

Prijeđite na sljedeće elemente koji su 32 i 17.

17 je manje od 32. Dakle, zamijenite ih.

Zamjena čini 31 i 17 nerazvrstanim. Dakle, zamijenite i njih.

Sada, mijenjanje čini 25 i 17 nerazvrstanim. Dakle, ponovno izvršite zamjenu.

Sada je niz potpuno sortiran.

Složenost sortiranja umetanjem

Sada, da vidimo vremensku složenost sortiranja umetanjem u najboljem slučaju, prosječnom slučaju iu najgorem slučaju. Također ćemo vidjeti prostornu složenost sortiranja umetanjem.

1. Vremenska složenost

Slučaj	Vremenska složenost
Najbolji slučaj	Na)
Prosječan slučaj	Na²)
Najgori slučaj	Na²)

Na)

Na²)

2. Složenost prostora

Složenost prostora	O(1)
Stabilan	DA

Prostorna složenost sortiranja umetanjem je O(1). To je zato što je u sortiranju umetanjem dodatna varijabla potrebna za zamjenu.

Implementacija sortiranja umetanjem

Pogledajmo sada programe sortiranja umetanjem u različitim programskim jezicima.

Program: Napišite program za implementaciju sortiranja umetanjem u C jeziku.

 #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;>

Izlaz:

Dakle, to je sve o članku. Nadamo se da će vam članak biti koristan i informativan.

Ovaj članak nije bio ograničen samo na algoritam. Također smo razgovarali o složenosti algoritma, radu i implementaciji u različitim programskim jezicima.

TechCodeview

Algoritam sortiranja umetanjem