ĮTERPIMO RŪŠIAVIMAS

Šiame straipsnyje aptarsime įterpimo rūšiavimo algoritmą. Įterpimo rūšiavimo darbo procedūra taip pat paprasta. Šis straipsnis bus labai naudingas ir įdomus studentams, nes egzaminuose jie gali susidurti su įterpimo rūšiavimo klausimu. Taigi, svarbu aptarti temą.

Įdėjimo rūšiavimas veikia panašiai kaip žaidimo kortų rūšiavimas rankose. Daroma prielaida, kad kortų žaidime pirmoji kortelė jau yra surūšiuota, o tada pasirenkame nerūšiuotą kortelę. Jei pasirinkta nerūšiuota kortelė yra didesnė už pirmąją, ji bus dedama dešinėje pusėje; kitu atveju jis bus dedamas kairėje pusėje. Panašiai visos nerūšiuotos kortelės paimamos ir dedamos į tikslią vietą.

Tas pats metodas taikomas įterpimo rūšiavimui. Įterpimo rūšiavimo idėja yra ta, kad pirmiausia paimkite vieną elementą ir pakartokite jį per surūšiuotą masyvą. Nors jį paprasta naudoti, jis netinka dideliems duomenų rinkiniams, nes įterpimo rūšiavimo sudėtingumas vidutiniu ir blogiausiu atveju yra O (n²) , kur n yra elementų skaičius. Įterpimo rūšiavimas yra mažiau efektyvus nei kiti rūšiavimo algoritmai, tokie kaip krūvos rūšiavimas, greitas rūšiavimas, sujungimo rūšiavimas ir kt.

Įterpimo rūšiavimas turi įvairių privalumų, tokių kaip -

Paprastas įgyvendinimas
Veiksmingas mažiems duomenų rinkiniams
Adaptyvusis, t. y. tinka duomenų rinkiniams, kurie jau yra iš esmės surūšiuoti.

Dabar pažiūrėkime įterpimo rūšiavimo algoritmą.

Algoritmas

Paprasti žingsniai, kaip pasiekti įterpimo rūšiavimą, yra išvardyti taip:

1 žingsnis - Jei elementas yra pirmasis elementas, tarkime, kad jis jau surūšiuotas. Grąžinti 1.

ubuntu build esminiai dalykai

2 žingsnis - Pasirinkite kitą elementą ir laikykite jį atskirai a Raktas.

3 žingsnis - Dabar palyginkite Raktas su visais surūšiuoto masyvo elementais.

4 veiksmas – Jei elementas surūšiuotame masyve yra mažesnis už dabartinį elementą, pereikite prie kito elemento. Kitu atveju perkelkite didesnius masyvo elementus į dešinę.

5 veiksmas – Įveskite vertę.

6 veiksmas - Kartokite, kol masyvas bus surūšiuotas.

Įterpimo rūšiavimo algoritmo veikimas

Dabar pažiūrėkime, kaip veikia įterpimo rūšiavimo algoritmas.

Norėdami suprasti įterpimo rūšiavimo algoritmo veikimą, paimkime nerūšiuotą masyvą. Per pavyzdį bus lengviau suprasti įterpimo rūšiavimą.

Tegul masyvo elementai yra -

Iš pradžių pirmieji du elementai lyginami įterpimo rūšiavimo būdu.

Čia 31 yra didesnis nei 12. Tai reiškia, kad abu elementai jau yra didėjančia tvarka. Taigi, kol kas 12 saugomi surūšiuotame pomasyve.

Dabar pereikite prie kitų dviejų elementų ir palyginkite juos.

Čia 25 yra mažesnis nei 31. Taigi, 31 nėra teisingoje padėtyje. Dabar pakeiskite 31 į 25. Kartu su keitimu įterpimo rūšiavimas taip pat patikrins jį su visais surūšiuoto masyvo elementais.

Kol kas surūšiuotas masyvas turi tik vieną elementą, ty 12. Taigi, 25 yra didesnis nei 12. Vadinasi, surūšiuotas masyvas lieka surūšiuotas po sukeitimo.

Dabar du surūšiuoto masyvo elementai yra 12 ir 25. Pereikite prie kitų elementų, kurie yra 31 ir 8.

Tiek 31, tiek 8 nerūšiuojami. Taigi, pakeiskite juos.

Pakeitus, 25 ir 8 elementai nerūšiuojami.

Taigi, pakeiskite juos.

Dabar 12 ir 8 elementai yra nerūšiuoti.

Taigi, pakeiskite ir juos.

Dabar surūšiuotame masyve yra trys elementai, kurių skaičius yra 8, 12 ir 25. Pereikite prie kitų elementų, kurie yra 31 ir 32.

Vadinasi, jie jau surūšiuoti. Dabar surūšiuotame masyve yra 8, 12, 25 ir 31.

Pereikite prie kitų elementų, kurie yra 32 ir 17.

17 yra mažesnis nei 32. Taigi, pakeiskite juos.

Sukeitimas daro 31 ir 17 nerūšiuoti. Taigi, pakeiskite ir juos.

Dabar sukeitus 25 ir 17 lieka nerūšiuoti. Taigi, atlikite keitimą dar kartą.

Dabar masyvas yra visiškai surūšiuotas.

Įterpimo rūšiavimo sudėtingumas

Dabar pažiūrėkime į įterpimo rūšiavimo sudėtingumą geriausiu atveju, vidutiniu atveju ir blogiausiu atveju. Taip pat pamatysime įterpimo rūšiavimo erdvės sudėtingumą.

1. Laiko sudėtingumas

Byla	Laiko sudėtingumas
Geriausias atvejis	O(n)
Vidutinis atvejis	O (n²)
Blogiausiu atveju	O (n²)

O(n)

O (n²)

2. Erdvės sudėtingumas

Erdvės sudėtingumas	O(1)
Stabilus	TAIP

Įterpimo rūšiavimo erdvės sudėtingumas yra O(1). Taip yra todėl, kad rūšiuojant įterpimą reikalingas papildomas kintamasis, norint pakeisti.

Įterpimo rūšiavimo įgyvendinimas

Dabar pažiūrėkime, kaip įterpimo programos rūšiuojamos skirtingomis programavimo kalbomis.

Programa: Parašykite programą įterpimo rūšiavimui įgyvendinti C kalba.

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

Išvestis:

Taigi, viskas apie straipsnį. Tikimės, kad straipsnis bus jums naudingas ir informatyvus.

Šis straipsnis neapsiribojo tik algoritmu. Taip pat aptarėme algoritmo sudėtingumą, veikimą ir įgyvendinimą skirtingomis programavimo kalbomis.

TechCodeview

Įterpimo rūšiavimo algoritmas