Šajā rakstā mēs apspriedīsim ievietošanas kārtošanas algoritmu. Arī ievietošanas kārtošanas darba procedūra ir vienkārša. Šis raksts būs ļoti noderīgs un interesants studentiem, jo eksāmenos viņi var saskarties ar ievietošanas veidu. Tāpēc ir svarīgi apspriest tēmu.
Ievietošanas kārtošana darbojas līdzīgi kā spēļu kāršu šķirošana rokās. Tiek pieņemts, ka pirmā karte jau ir sakārtota kāršu spēlē, un tad mēs izvēlamies nešķiroto karti. Ja izvēlētā nešķirotā karte ir lielāka par pirmo karti, tā tiks novietota labajā pusē; pretējā gadījumā tas tiks novietots kreisajā pusē. Tāpat visas nešķirotās kartītes tiek ņemtas un ievietotas precīzā vietā.
Tāda pati pieeja tiek izmantota ievietošanas kārtošanā. Ievietošanas kārtošanas ideja ir tāda, ka vispirms ņem vienu elementu un atkārto to caur sakārtoto masīvu. Lai gan tas ir vienkārši lietojams, tas nav piemērots lielām datu kopām, jo ievietošanas kārtošanas laika sarežģītība vidējā un sliktākajā gadījumā ir O(n2) , kur n ir vienumu skaits. Ievietošanas kārtošana ir mazāk efektīva nekā citi kārtošanas algoritmi, piemēram, kaudzes kārtošana, ātrā kārtošana, sapludināšanas kārtošana utt.
Ievietošanas šķirošanai ir dažādas priekšrocības, piemēram,
- Vienkārša ieviešana
- Efektīva mazām datu kopām
- Adaptīvs, t.i., tas ir piemērots datu kopām, kas jau ir būtiski sakārtotas.
Tagad apskatīsim ievietošanas kārtošanas algoritmu.
Algoritms
Vienkāršās ievietošanas kārtošanas sasniegšanas darbības ir norādītas šādi:
1. darbība — Ja elements ir pirmais elements, pieņemsim, ka tas jau ir sakārtots. Atgriešanās 1.
noņemiet npm kešatmiņu
2. darbība — Izvēlieties nākamo elementu un uzglabājiet to atsevišķi a taustiņu.
3. darbība - Tagad salīdziniet taustiņu ar visiem elementiem sakārtotajā masīvā.
4. darbība — Ja elements sakārtotajā masīvā ir mazāks par pašreizējo elementu, pārejiet uz nākamo elementu. Pretējā gadījumā pārvietojiet lielākus elementus masīvā pa labi.
5. darbība — Ievietojiet vērtību.
6. darbība — Atkārtojiet, līdz masīvs ir sakārtots.
Ievietošanas kārtošanas algoritma darbība
Tagad apskatīsim ievietošanas kārtošanas algoritma darbību.
Lai saprastu ievietošanas kārtošanas algoritma darbību, ņemsim nešķirotu masīvu. Ievietošanas kārtošanu būs vieglāk saprast, izmantojot piemēru.
Lai masīva elementi ir -
Sākotnēji pirmie divi elementi tiek salīdzināti ievietošanas kārtībā.
Šeit 31 ir lielāks par 12. Tas nozīmē, ka abi elementi jau ir augošā secībā. Tātad pagaidām 12 tiek glabāti sakārtotā apakšmasīvā.
Tagad pārejiet pie nākamajiem diviem elementiem un salīdziniet tos.
Šeit 25 ir mazāks par 31. Tātad 31 nav pareizā pozīcijā. Tagad samainiet 31 ar 25. Līdztekus maiņai ievietošanas kārtošana pārbaudīs to arī ar visiem elementiem sakārtotajā masīvā.
Pagaidām sakārtotajam masīvam ir tikai viens elements, t.i., 12. Tātad 25 ir lielāks par 12. Tādējādi sakārtotais masīvs paliek sakārtots arī pēc apmaiņas.
Tagad divi elementi sakārtotajā masīvā ir 12 un 25. Pārejiet uz nākamajiem elementiem, kas ir 31 un 8.
Gan 31, gan 8 nav sakārtoti. Tātad, nomainiet tos.
Pēc apmaiņas elementi 25 un 8 tiek nešķiroti.
Tātad, nomainiet tos.
Tagad elementi 12 un 8 ir nešķiroti.
Tātad, nomainiet arī tos.
Tagad sakārtotajā masīvā ir trīs vienumi, kas ir 8, 12 un 25. Pārejiet uz nākamajiem vienumiem, kas ir 31 un 32.
Tādējādi tie jau ir sakārtoti. Tagad sakārtotajā masīvā ir 8, 12, 25 un 31.
Pārejiet uz nākamajiem elementiem, kas ir 32 un 17.
17 ir mazāks par 32. Tātad, nomainiet tos.
Samaiņa padara 31 un 17 nešķirotas. Tātad, nomainiet arī tos.
Tagad, apmainot, 25 un 17 tiek nešķiroti. Tātad, veiciet maiņu vēlreiz.
Tagad masīvs ir pilnībā sakārtots.
Ievietošanas kārtošanas sarežģītība
Tagad apskatīsim ievietošanas kārtošanas laika sarežģītību labākajā gadījumā, vidējā gadījumā un sliktākajā gadījumā. Mēs redzēsim arī ievietošanas kārtošanas sarežģītību.
1. Laika sarežģītība
| Lieta | Laika sarežģītība |
|---|---|
| Labākais gadījums | O(n) |
| Vidējais gadījums | O(n2) |
| Sliktākajā gadījumā | O(n2) |
2. Telpas sarežģītība
| Kosmosa sarežģītība | O(1) |
| Stabils | JĀ |
- Ievietošanas kārtošanas telpas sarežģītība ir O(1). Tas ir tāpēc, ka ievietošanas kārtošanā ir nepieciešams papildu mainīgais apmaiņai.
Ievietošanas kārtošanas ieviešana
Tagad apskatīsim ievietošanas programmu šķirošanu dažādās programmēšanas valodās.
Programma: Uzrakstiet programmu ievietošanas kārtošanai C valodā.
#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 && 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 >= 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 && 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 && 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 && 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>'; printArray($a); for ($i = 1; $i = 0 && $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>'; printArray($a); ?> </=></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'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's complexity, working, and implementation in different programming languages.</p> <hr></=></n;></pre></=></n;></pre></=></n;></pre></a[j]></pre></=></n;> Izvade:
Tātad, tas viss par rakstu. Cerams, ka raksts jums būs noderīgs un informatīvs.
Šis raksts neaprobežojās tikai ar algoritmu. Mēs arī apspriedām algoritma sarežģītību, darbību un ieviešanu dažādās programmēšanas valodās.