Considereu els números següents:
50 60 30 10 80 70 20 40
Si aquesta llista s'ordena en ordre ascendent, seria:
10 20 30 40 50 60 70 80
Si s'ordena en ordre descendent, seria:
80 70 60 50 40 30 20 10
L'ordenació per inserció és un algorisme d'ordenació que s'utilitza per ordenar la llista en ordre ascendent o descendent. Aquest article només tracta de l'ordenació en ordre ascendent. L'ordenació en ordre descendent segueix la mateixa lògica que es dóna en aquest document. L'objectiu d'aquest article és explicar l'ordenació d'inserció. La programació es fa a l'exemple següent en C. L'ordenació d'inserció s'explica aquí utilitzant una matriu.
Algorisme per a l'ordenació d'inserció
Es dóna una llista sense ordenar. L'objectiu és ordenar la llista en ordre ascendent utilitzant la mateixa llista. Es diu que l'ordenació d'una matriu no ordenada utilitzant la mateixa matriu s'està ordenant al lloc. Aquí s'utilitza la indexació basada en zero. Els passos són els següents:
-
- La llista s'escaneja des del principi.
- Mentre l'escaneig continua, qualsevol número inferior al seu predecessor s'intercanvia amb el seu predecessor.
- Aquest intercanvi continua al llarg de la llista, fins que ja no és possible l'intercanvi.
- Quan l'escaneig arriba al final, l'ordenació s'ha completat.
Il·lustració d'ordenació d'inserció
Quan es tracta de la complexitat del temps, és el pitjor cas el que normalment es té en compte. El pitjor arranjament per a la llista anterior és:
80 70 60 50 40 30 20 10
Hi ha vuit elements amb índexs de zero a 7.
A l'índex zero, l'escaneig passa a 80. Aquest és un moviment. Aquest moviment és una operació. Hi ha un total d'una operació fins ara (un moviment, sense comparació i sense intercanvi). El resultat és:
| 80 70 60 50 40 30 20 10
A l'índex 1, hi ha un moviment cap a 70. 70 es compara amb 80. 70 i 80 s'intercanvien. Un moviment és una operació. Una comparació és també una operació. Un intercanvi també és una operació. Aquesta secció ofereix tres operacions. Hi ha un total de quatre operacions fins ara (1 + 3 = 4). El resultat és el següent:
70 | 80 60 50 40 30 20 10
A l'índex dos, hi ha un moviment cap a 60. 60 es compara amb 80, després 60 i 80 s'intercanvien. 60 es compara amb 70, després s'intercanvien 60 i 70. Un moviment és una operació. Dues comparacions són dues operacions. Dos intercanvis són dues operacions. Aquesta secció ofereix cinc operacions. Hi ha un total de nou operacions fins ara (4 + 5 = 9). El resultat és el següent:
60 70 | 80 50 40 30 20 10
A l'índex tres, hi ha un moviment cap a 50. 50 es compara amb 80, després 50 i 80 s'intercanvien. 50 es compara amb 70, després s'intercanvien 50 i 70. 50 es compara amb 60, després 50 i 60 s'intercanvien. Un moviment és una operació. Tres comparacions són tres operacions. Tres intercanvis són tres operacions. Aquesta secció ofereix set operacions. Hi ha un total de setze operacions fins ara (9 + 7 = 16). El resultat és el següent:
50 60 70 | 80 40 30 20 10
A l'índex quatre, hi ha un moviment cap a 40. 40 es compara amb 80, després s'intercanvien 40 i 80. 40 es compara amb 70, després s'intercanvien 40 i 70. 40 es compara amb 60, després s'intercanvien 40 i 60. 40 es compara amb 50, després s'intercanvien 40 i 50. Un moviment és una operació. Quatre comparacions són quatre operacions. Quatre intercanvis són quatre operacions. Aquesta secció ofereix nou operacions. Hi ha un total de vint-i-cinc operacions fins ara (16 + 9 = 25). El resultat és el següent:
40 50 60 70 80 | 30 20 10
A l'índex cinc, hi ha un moviment cap a 30. 30 es compara amb 80, després s'intercanvien 30 i 80. 30 es compara amb 70, després s'intercanvien 30 i 70. 30 es compara amb 60, després s'intercanvien 30 i 60. 30 es compara amb 50, després s'intercanvien 30 i 50. 30 es compara amb 40, després s'intercanvien 30 i 40. Un moviment és una operació. Cinc comparacions són cinc operacions. Cinc intercanvis són cinc operacions. Aquesta secció ofereix onze operacions. Hi ha un total de trenta-sis operacions fins ara (25 + 11 = 36). El resultat és el següent:
30 40 50 60 70 80 | 20 10
A l'índex sis, hi ha un moviment cap a 20. 20 es compara amb 80, després 20 i 80 s'intercanvien. 20 es compara amb 70, després s'intercanvien 20 i 70. 20 es compara amb 60, després s'intercanvien 20 i 60. 20 es compara amb 50, després s'intercanvien 20 i 50. 20 es compara amb 40, després s'intercanvien 20 i 40. 20 es compara amb 30, després s'intercanvien 20 i 30. Un moviment és una operació. Sis comparacions són sis operacions. Sis intercanvis són sis operacions. Aquesta secció inclou tretze operacions. Hi ha un total de quaranta-nou operacions fins ara (36 + 13 = 49). El resultat és el següent:
20 30 40 50 60 70 80 | 10
A l'índex set, hi ha un moviment cap a 10. 10 es compara amb 80, després 10 i 80 s'intercanvien. 10 es compara amb 70, després s'intercanvien 10 i 70. 10 es compara amb 60, després 10 i 60 s'intercanvien. 10 es compara amb 50, després s'intercanvien 10 i 50. 10 es compara amb 30, després s'intercanvien 10 i 40. 10 es compara amb 30, després s'intercanvien 10 i 30. 10 es compara amb 20, després s'intercanvien 10 i 20. Un moviment és una operació. Set comparacions són set operacions. Set swaps són set operacions. Aquesta secció inclou quinze operacions. Hi ha un total de seixanta-quatre operacions fins ara (49 + 15 = 64). El resultat és el següent:
10 20 30 40 50 60 70 80 10 |
La feina està feta! S'han implicat 64 operacions.
64 = 8 x 8 = 8 2
Complexitat temporal per a l'ordenació d'inserció
Si hi ha n elements per ordenar amb Insertion Sort, el nombre màxim d'operacions possibles seria n2, com s'ha demostrat anteriorment. La complexitat del temps d'ordenació d'inserció és:
O (n 2 )
Això utilitza la notació Big-O. La notació Big-O comença amb O en majúscula, seguida de parèntesis. Dins dels parèntesis hi ha l'expressió del màxim nombre possible d'operacions.
Codificació en C
Al principi de l'exploració, el primer element no pot canviar la seva posició. El programa és bàsicament el següent:
#inclouvoid insertionSort ( int A [ ] , int N ) {
per ( int i = 0 ; i < N; i++ ) {
int j = i;
mentre ( A [ j ] < A [ j- 1 ] && j- 1 > = 0 ) {
int temp = A [ j ] ; A [ j ] = A [ j- 1 ] ; A [ j- 1 ] = temperatura; // intercanviar
j--;
}
}
}
La definició de la funció insertionSort() utilitza l'algorisme tal com es descriu. Tingueu en compte les condicions del bucle while. Una funció principal C adequada per a aquest programa és:
{
int n = 8 ;
int A [ ] = { 50 , 60 , 30 , 10 , 80 , 70 , 20 , 40 } ;
insercióOrdenar ( A, n ) ;
per ( int i = 0 ; i < n; i++ ) {
imprimirf ( '%i' , A [ i ] ) ;
}
imprimirf ( ' \n ' ) ;
tornar 0 ;
}
Conclusió
La complexitat del temps per a l'ordenació d'inserció es dóna com:
O (n 2 )
El lector podria haver sentit parlar d'una complexitat de temps pitjor, complexitat de temps mitjana i complexitat de temps en el millor dels casos. Aquestes variacions de la complexitat del temps d'ordenació d'inserció es discuteixen al següent article del nostre lloc web.