En aquest article, parlarem de l'algoritme d'ordenació d'inserció. El procediment de treball de classificació d'inserció també és senzill. Aquest article serà molt útil i interessant per als estudiants, ja que podrien enfrontar-se a l'ordenació d'inserció com a pregunta en els seus exàmens. Per tant, és important parlar del tema.
L'ordenació per inserció funciona de manera similar a l'ordenació de cartes a les mans. Se suposa que la primera carta ja està ordenada al joc de cartes, i després seleccionem una carta sense classificar. Si la carta no ordenada seleccionada és més gran que la primera, es col·locarà al costat dret; en cas contrari, es col·locarà al costat esquerre. De la mateixa manera, totes les cartes sense classificar es prenen i es posen al seu lloc exacte.
El mateix enfocament s'aplica a l'ordenació d'inserció. La idea darrere de l'ordenació d'inserció és que primer agafeu un element i l'itereu a través de la matriu ordenada. Tot i que és senzill d'utilitzar, no és adequat per a grans conjunts de dades, ja que la complexitat temporal de l'ordenació d'inserció en el cas mitjà i en el pitjor dels casos és O (n2) , on n és el nombre d'elements. L'ordenació per inserció és menys eficient que els altres algorismes d'ordenació, com ara l'ordenació de pila, l'ordenació ràpida, l'ordenació per fusió, etc.
La classificació per inserció té diversos avantatges, com ara:
- Implementació senzilla
- Eficaç per a petits conjunts de dades
- Adaptatiu, és a dir, és adequat per a conjunts de dades que ja estan substancialment ordenats.
Ara, vegem l'algorisme d'ordenació d'inserció.
Algorisme
Els passos senzills per aconseguir l'ordenació d'inserció s'enumeren de la següent manera:
Pas 1 - Si l'element és el primer element, suposa que ja està ordenat. Tornar 1.
herència en c++
Pas 2 - Trieu l'element següent i deseu-lo per separat a a clau.
Pas 3 - Ara, compara el clau amb tots els elements de la matriu ordenada.
Pas 4 - Si l'element de la matriu ordenada és més petit que l'element actual, passeu a l'element següent. En cas contrari, desplaceu els elements més grans de la matriu cap a la dreta.
Pas 5 - Insereix el valor.
Pas 6 - Repetiu fins que la matriu estigui ordenada.
Funcionament de l'algoritme d'ordenació d'inserció
Ara, vegem el funcionament de l'algoritme d'ordenació d'inserció.
Per entendre el funcionament de l'algorisme d'ordenació d'inserció, prenem una matriu sense ordenar. Serà més fàcil entendre l'ordenació d'inserció mitjançant un exemple.
Siguin els elements de la matriu -
Inicialment, els dos primers elements es comparen en l'ordenació d'inserció.
Aquí, 31 és més gran que 12. Això vol dir que els dos elements ja estan en ordre ascendent. Per tant, de moment, 12 s'emmagatzema en una submatriu ordenada.
Ara, passeu als dos elements següents i compareu-los.
Aquí, 25 és més petit que 31. Per tant, 31 no està en la posició correcta. Ara, intercanvieu 31 amb 25. Juntament amb l'intercanvi, l'ordenació per inserció també el comprovarà amb tots els elements de la matriu ordenada.
De moment, la matriu ordenada només té un element, és a dir, 12. Per tant, 25 és més gran que 12. Per tant, la matriu ordenada roman ordenada després de l'intercanvi.
Ara, dos elements de la matriu ordenada són 12 i 25. Avança als següents elements que són 31 i 8.
Tant el 31 com el 8 no estan ordenats. Per tant, intercanvieu-los.
Després de l'intercanvi, els elements 25 i 8 no es classifiquen.
Per tant, intercanvieu-los.
Ara, els elements 12 i 8 no estan ordenats.
Per tant, intercanvieu-los també.
Ara, la matriu ordenada té tres elements que són 8, 12 i 25. Passeu als elements següents que són 31 i 32.
Per tant, ja estan ordenats. Ara, la matriu ordenada inclou 8, 12, 25 i 31.
Passeu als elements següents que són 32 i 17.
17 és més petit que 32. Per tant, canvieu-los.
L'intercanvi fa que el 31 i el 17 no estiguin ordenats. Per tant, intercanvieu-los també.
Ara, l'intercanvi fa que 25 i 17 no estiguin ordenats. Per tant, torneu a fer l'intercanvi.
Ara, la matriu està completament ordenada.
Complexitat d'ordenació d'inserció
Ara, vegem la complexitat temporal de l'ordenació d'inserció en el millor dels casos, en el cas mitjà i en el pitjor dels casos. També veurem la complexitat espacial de l'ordenació d'inserció.
1. Complexitat temporal
| Caixa | Complexitat temporal |
|---|---|
| Millor cas | O(n) |
| Cas mitjà | O (n2) |
| Pitjor dels casos | O (n2) |
2. Complexitat espacial
| Complexitat espacial | O(1) |
| Estable | SÍ |
- La complexitat espacial de l'ordenació d'inserció és O(1). És perquè, en l'ordenació d'inserció, es requereix una variable addicional per intercanviar.
Implementació de l'ordenació d'inserció
Ara, vegem els programes d'inserció ordenats en diferents llenguatges de programació.
Programa: Escriu un programa per implementar l'ordenació d'inserció en llenguatge 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 && 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;> Sortida:
Per tant, això és tot sobre l'article. Espero que l'article us sigui útil i informatiu.
Aquest article no es limitava només a l'algorisme. També hem comentat la complexitat, el funcionament i la implementació de l'algorisme en diferents llenguatges de programació.