Tässä artikkelissa käsittelemme lisäyslajittelualgoritmia. Myös lisäyslajitteluprosessi on yksinkertainen. Tämä artikkeli on erittäin hyödyllinen ja mielenkiintoinen opiskelijoille, koska he saattavat kohdata lisäyslajittelun kysymyksenä kokeissaan. Joten on tärkeää keskustella aiheesta.

Lisäyslajittelu toimii samalla tavalla kuin pelikorttien lajittelu käsissä. Oletetaan, että ensimmäinen kortti on jo lajiteltu korttipelissä, ja sitten valitsemme lajittelemattoman kortin. Jos valittu lajittelematon kortti on suurempi kuin ensimmäinen kortti, se sijoitetaan oikealle puolelle; muuten se sijoitetaan vasemmalle puolelle. Samoin kaikki lajittelemattomat kortit otetaan ja laitetaan paikoilleen.

Samaa lähestymistapaa sovelletaan lisäyslajittelussa. Lisäyslajittelun ideana on, että otetaan ensin yksi elementti ja iteroidaan se lajitellun taulukon läpi. Vaikka se on yksinkertainen käyttää, se ei sovellu suurille tietojoukoille, koska lisäyslajittelun aika monimutkaisuus keskimääräisessä ja pahimmassa tapauksessa on Päällä²) , jossa n on kohteiden lukumäärä. Lisäyslajittelu on vähemmän tehokas kuin muut lajittelualgoritmit, kuten kasalajittelu, pikalajittelu, yhdistämislajittelu jne.

Lisäyslajittelulla on useita etuja, kuten -

• Yksinkertainen toteutus
• Tehokas pienille tietojoukoille
• Adaptiivinen, eli se sopii tietojoukoille, jotka ovat jo oleellisesti lajiteltuja.

Katsotaanpa nyt lisäyslajittelun algoritmia.

Algoritmi

Yksinkertaiset vaiheet lisäyslajittelun saavuttamiseksi on lueteltu seuraavasti -

Vaihe 1 - Jos elementti on ensimmäinen elementti, oletetaan, että se on jo lajiteltu. Paluu 1.

nfa esimerkkejä

Vaihe 2 - Valitse seuraava elementti ja säilytä se erikseen a avain.

Vaihe 3 - Vertaa nyt avain kaikki lajitellun taulukon elementit.

Vaihe 4 - Jos lajitellun taulukon elementti on pienempi kuin nykyinen elementti, siirry seuraavaan elementtiin. Muutoin siirrä suurempia elementtejä taulukossa oikealle.

Vaihe 5 - Lisää arvo.

Vaihe 6 - Toista, kunnes taulukko on lajiteltu.

Lisäyslajittelualgoritmin toiminta

Katsotaanpa nyt lisäyslajittelualgoritmin toimintaa.

Ymmärtääksemme lisäyslajittelualgoritmin toiminnan, otetaan lajittelematon matriisi. Lisäyslajittelu on helpompi ymmärtää esimerkin avulla.

Olkoon taulukon elementit -

Aluksi kahta ensimmäistä elementtiä verrataan lisäyslajittelussa.

Tässä 31 on suurempi kuin 12. Tämä tarkoittaa, että molemmat elementit ovat jo nousevassa järjestyksessä. Joten toistaiseksi 12 on tallennettu lajiteltuun alitaulukkoon.

Siirry nyt kahteen seuraavaan elementtiin ja vertaa niitä.

Tässä 25 on pienempi kuin 31. Joten 31 ei ole oikeassa paikassa. Vaihda nyt 31 25:een. Vaihdon ohella lisäyslajittelu tarkistaa sen myös kaikista lajitellun taulukon elementeistä.

Toistaiseksi lajitetussa taulukossa on vain yksi elementti, eli 12. Joten 25 on suurempi kuin 12. Näin ollen lajiteltu matriisi pysyy lajiteltuna vaihdon jälkeen.

Nyt lajitellun taulukon kaksi elementtiä ovat 12 ja 25. Siirry eteenpäin seuraaviin elementteihin, jotka ovat 31 ja 8.

Sekä 31 että 8 ei ole lajiteltu. Joten vaihda ne.

Vaihdon jälkeen elementit 25 ja 8 ovat lajittelemattomia.

Joten vaihda ne.

Nyt elementit 12 ja 8 ovat lajittelemattomia.

Joten vaihda nekin.

Nyt lajitetussa taulukossa on kolme kohdetta, jotka ovat 8, 12 ja 25. Siirry seuraaviin alkioihin, jotka ovat 31 ja 32.

Siksi ne on jo lajiteltu. Nyt lajiteltu matriisi sisältää 8, 12, 25 ja 31.

Siirry seuraaviin elementteihin, jotka ovat 32 ja 17.

17 on pienempi kuin 32. Joten vaihda ne.

Vaihto tekee 31 ja 17 lajittelematta. Joten vaihda nekin.

Nyt vaihto tekee 25 ja 17 lajittelematta. Suorita siis vaihto uudelleen.

Nyt matriisi on täysin lajiteltu.

Lisäyksen lajittelun monimutkaisuus

Katsotaan nyt lisäyslajittelun aikamonimutkaisuus parhaassa tapauksessa, keskimääräisessä tapauksessa ja pahimmassa tapauksessa. Näemme myös lisäyslajittelun avaruuden monimutkaisuuden.

1. Aika monimutkaisuus

Paras tapauksen monimutkaisuus -Se tapahtuu, kun lajittelua ei vaadita, eli matriisi on jo lajiteltu. Lisäyslajittelun paras aika monimutkaisuus on Päällä) .Keskimääräinen tapauksen monimutkaisuus -Se tapahtuu, kun taulukon elementit ovat sekaisin järjestyksessä, joka ei ole oikein nouseva eikä oikein laskeva. Lisäyslajittelun tapauksen keskimääräinen aika monimutkaisuus on Päällä²) .Pahimman tapauksen monimutkaisuus -Se tapahtuu, kun taulukon elementit on lajiteltava käänteisessä järjestyksessä. Tämä tarkoittaa, että sinun on lajiteltava taulukon elementit nousevaan järjestykseen, mutta sen elementit ovat laskevassa järjestyksessä. Lisäyslajittelun pahin aika monimutkaisuus on Päällä²) .

2. Tilan monimutkaisuus

• Lisäyslajittelun monimutkaisuus on O(1). Tämä johtuu siitä, että lisäyslajittelussa vaihtamiseen tarvitaan ylimääräinen muuttuja.

Lisäyslajittelun toteutus

Katsotaanpa nyt lisäysohjelmien lajittelua eri ohjelmointikielillä.

Ohjelmoida: Kirjoita ohjelma, joka toteuttaa lisäyslajittelun C-kielellä.

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

Lähtö:

Eli siinä kaikki artikkelista. Toivottavasti artikkeli on hyödyllinen ja informatiivinen sinulle.

Tämä artikkeli ei rajoittunut vain algoritmiin. Olemme myös käsitelleet algoritmin monimutkaisuutta, toimivuutta ja toteutusta eri ohjelmointikielillä.