RAZVRŠČANJE VSTAVLJANJA

V tem članku bomo razpravljali o algoritmu za razvrščanje z vstavljanjem. Preprost je tudi delovni postopek sortiranja vstavljanja. Ta članek bo študentom zelo koristen in zanimiv, saj se lahko na izpitih soočijo z vstavljanjem kot vprašanjem. Zato je pomembno razpravljati o temi.

Razvrščanje z vstavljanjem deluje podobno kot razvrščanje igralnih kart v rokah. Predpostavlja se, da je prva karta v igri s kartami že razvrščena, nato pa izberemo nerazvrščeno karto. Če je izbrana nerazvrščena karta večja od prve karte, bo postavljena na desno stran; sicer bo postavljen na levo stran. Podobno se vse nerazvrščene karte vzamejo in postavijo na točno določeno mesto.

Enak pristop se uporablja pri razvrščanju z vstavljanjem. Ideja za razvrščanjem z vstavljanjem je, da najprej vzamete en element in ga ponovite skozi razvrščeno matriko. Čeprav je preprost za uporabo, ni primeren za velike nabore podatkov, saj je časovna zapletenost razvrščanja vstavljanja v povprečnem in najslabšem primeru O(n²) , kjer je n število elementov. Razvrščanje z vstavljanjem je manj učinkovito kot drugi algoritmi za razvrščanje, kot so razvrščanje na kup, hitro razvrščanje, razvrščanje z zlivanjem itd.

Razvrščanje vstavljanja ima številne prednosti, kot so -

Preprosta izvedba
Učinkovito za majhne nize podatkov
Prilagodljivo, tj. primerno za nabore podatkov, ki so že precej razvrščeni.

Zdaj pa si oglejmo algoritem razvrščanja vstavljanja.

Algoritem

Preprosti koraki za doseganje razvrščanja vstavljanja so navedeni na naslednji način -

Korak 1 - Če je element prvi element, predpostavimo, da je že razvrščen. Vrnitev 1.

sort arraylist v Javi

2. korak - Izberite naslednji element in ga shranite ločeno v a ključ.

3. korak - Zdaj pa primerjajte ključ z vsemi elementi v razvrščenem nizu.

4. korak - Če je element v razvrščeni matriki manjši od trenutnega elementa, se premaknite na naslednji element. V nasprotnem primeru premaknite večje elemente v nizu v desno.

5. korak - Vnesite vrednost.

6. korak - Ponavljajte, dokler niz ni razvrščen.

Delovanje algoritma za razvrščanje vstavljanja

Zdaj pa si oglejmo delovanje algoritma za razvrščanje vstavljanja.

Da bi razumeli delovanje algoritma za razvrščanje z vstavljanjem, vzemimo nerazvrščeno matriko. Razvrščanje vstavljanja bo lažje razumeti na primeru.

Naj so elementi matrike -

Na začetku se prva dva elementa primerjata pri razvrščanju vstavljanja.

Tukaj je 31 večje od 12. To pomeni, da sta oba elementa že v naraščajočem vrstnem redu. Tako je za zdaj 12 shranjenih v razvrščeni podmatriki.

Zdaj pa se premaknite na naslednja dva elementa in ju primerjajte.

Tukaj je 25 manjše od 31. Torej 31 ni v pravilnem položaju. Zdaj zamenjajte 31 s 25. Skupaj z zamenjavo bo razvrščanje z vstavljanjem preverilo tudi z vsemi elementi v razvrščeni matriki.

Zaenkrat ima razvrščena matrika le en element, to je 12. Torej je 25 večje od 12. Zato ostane razvrščena matrika po zamenjavi razvrščena.

Zdaj sta dva elementa v razvrščeni matriki 12 in 25. Premaknite se naprej do naslednjih elementov, ki sta 31 in 8.

Tako 31 kot 8 nista razvrščena. Torej, zamenjajte jih.

Po zamenjavi sta elementa 25 in 8 nerazvrščena.

Torej, zamenjajte jih.

Zdaj sta elementa 12 in 8 nerazvrščena.

Torej, zamenjajte jih tudi vi.

Sedaj ima razvrščena matrika tri elemente, ki so 8, 12 in 25. Premaknite se na naslednje elemente, ki so 31 in 32.

Zato so že razvrščeni. Zdaj razvrščeni niz vključuje 8, 12, 25 in 31.

Premaknite se na naslednja elementa, ki sta 32 in 17.

17 je manjše od 32. Torej, zamenjajte jih.

Zamenjava naredi 31 in 17 nerazvrščena. Torej, zamenjajte jih tudi vi.

Zdaj pa zamenjava naredi 25 in 17 nerazvrščena. Torej ponovno izvedite zamenjavo.

Sedaj je niz popolnoma urejen.

Kompleksnost razvrščanja vstavljanja

Zdaj pa poglejmo časovno zahtevnost razvrščanja vstavljanja v najboljšem, povprečnem primeru in v najslabšem primeru. Videli bomo tudi prostorsko kompleksnost razvrščanja vstavljanja.

1. Časovna zapletenost

Ovitek	Časovna zapletenost
Najboljši primer	O(n)
Povprečen primer	O(n²)
V najslabšem primeru	O(n²)

O(n)

O(n²)

2. Kompleksnost prostora

Kompleksnost prostora	O(1)
Stabilen	DA

Prostorska kompleksnost razvrščanja z vstavljanjem je O(1). To je zato, ker je pri razvrščanju z vstavljanjem potrebna dodatna spremenljivka za zamenjavo.

Izvedba razvrščanja vstavljanja

Zdaj pa si oglejmo programe za razvrščanje vstavljanja v različnih programskih jezikih.

Program: Napišite program za izvajanje razvrščanja z vstavljanjem v jeziku 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;>

Izhod:

Torej, to je vse o članku. Upam, da vam bo članek koristen in informativen.

Ta članek ni bil omejen le na algoritem. Razpravljali smo tudi o kompleksnosti algoritma, delovanju in implementaciji v različnih programskih jezikih.

TechCodeview

Algoritem za razvrščanje vstavljanja