Luați în considerare următoarele numere:
50 60 30 10 80 70 20 40
Dacă această listă este sortată în ordine crescătoare, ar fi:
10 20 30 40 50 60 70 80
Dacă este sortat în ordine descrescătoare, ar fi:
80 70 60 50 40 30 20 10
Sortare prin inserție este un algoritm de sortare care este folosit pentru a sorta lista în ordine crescătoare sau descrescătoare. Acest articol tratează doar sortarea în ordine crescătoare. Sortarea în ordine descrescătoare urmează aceeași logică dată în acest document. Scopul acestui articol este de a explica sortarea inserției. Programarea se face în exemplul următor în C. Sortarea de inserare este explicată aici folosind o singură matrice.
Algoritm pentru sortarea prin inserare
Se oferă o listă nesortată. Scopul este de a sorta lista în ordine crescătoare folosind aceeași listă. Sortarea unei matrice nesortate folosind aceeași matrice se spune că este sortarea la locul lor. Aici se utilizează indexarea pe bază de zero. Pașii sunt următorii:
-
- Lista este scanată de la început.
- În timpul scanării, orice număr mai mic decât predecesorul său este schimbat cu predecesorul său.
- Această schimbare continuă de-a lungul listei, până când nu mai este posibilă schimbarea.
- Când scanarea ajunge la sfârșit, sortarea este completă.
Ilustrație de sortare prin inserare
Atunci când se ocupă de complexitatea timpului, este cel mai rău caz care este luat în considerare în mod normal. Cel mai prost aranjament pentru lista anterioară este:
80 70 60 50 40 30 20 10
Există opt elemente cu indici de la zero la 7.
La indicele zero, scanarea merge la 80. Aceasta este o mișcare. Această mișcare este o operație. Există în total o operație până acum (o mișcare, nicio comparație și nicio schimbare). Rezultatul este:
| 80 70 60 50 40 30 20 10
La indicele unu, există o mișcare către 70. 70 este comparat cu 80. 70 și 80 sunt schimbate. O mișcare este o operație. O comparație este și o operație. Un schimb este, de asemenea, o operațiune. Această secțiune oferă trei operațiuni. Există un total de patru operații până acum (1 + 3 = 4). Rezultatul este următorul:
70 | 80 60 50 40 30 20 10
La indicele doi, există o mișcare către 60. 60 este comparat cu 80, apoi 60 și 80 sunt schimbate. 60 este comparat cu 70, apoi 60 și 70 sunt schimbate. O mișcare este o operație. Două comparații sunt două operații. Două schimburi sunt două operațiuni. Această secțiune oferă cinci operațiuni. Există un total de nouă operațiuni până acum (4 + 5 = 9). Rezultatul este următorul:
60 70 | 80 50 40 30 20 10
La indicele trei, există o mișcare către 50. 50 este comparat cu 80, apoi 50 și 80 sunt schimbate. 50 este comparat cu 70, apoi 50 și 70 sunt schimbate. 50 este comparat cu 60, apoi 50 și 60 sunt schimbate. O mișcare este o operație. Trei comparații sunt trei operațiuni. Trei schimburi sunt trei operațiuni. Această secțiune oferă șapte operațiuni. Există un total de șaisprezece operațiuni până acum (9 + 7 = 16). Rezultatul este următorul:
50 60 70 | 80 40 30 20 10
La indicele patru, există o mișcare către 40. 40 este comparat cu 80, apoi 40 și 80 sunt schimbate. 40 este comparat cu 70, apoi 40 și 70 sunt schimbate. 40 este comparat cu 60, apoi 40 și 60 sunt schimbate. 40 este comparat cu 50, apoi 40 și 50 sunt schimbate. O mișcare este o operație. Patru comparații sunt patru operații. Patru schimburi sunt patru operațiuni. Această secțiune oferă nouă operațiuni. Există un total de douăzeci și cinci de operațiuni până acum (16 + 9 = 25). Rezultatul este următorul:
40 50 60 70 80 | 30 20 10
La indicele cinci, există o mișcare către 30. 30 este comparat cu 80, apoi 30 și 80 sunt schimbate. 30 este comparat cu 70, apoi 30 și 70 sunt schimbate. 30 este comparat cu 60, apoi 30 și 60 sunt schimbate. 30 este comparat cu 50, apoi 30 și 50 sunt schimbate. 30 este comparat cu 40, apoi 30 și 40 sunt schimbate. O mișcare este o operație. Cinci comparații sunt cinci operațiuni. Cinci schimburi sunt cinci operațiuni. Această secțiune oferă unsprezece operațiuni. Există un total de treizeci și șase de operații până acum (25 + 11 = 36). Rezultatul este următorul:
30 40 50 60 70 80 | 20 10
La indicele șase, există o mișcare către 20. 20 este comparat cu 80, apoi 20 și 80 sunt schimbate. 20 este comparat cu 70, apoi 20 și 70 sunt schimbate. 20 este comparat cu 60, apoi 20 și 60 sunt schimbate. 20 este comparat cu 50, apoi 20 și 50 sunt schimbate. 20 este comparat cu 40, apoi 20 și 40 sunt schimbate. 20 este comparat cu 30, apoi 20 și 30 sunt schimbate. O mișcare este o operație. Șase comparații sunt șase operațiuni. Șase schimburi sunt șase operațiuni. Această secțiune oferă treisprezece operațiuni. Există un total de patruzeci și nouă de operațiuni până acum (36 + 13 = 49). Rezultatul este următorul:
20 30 40 50 60 70 80 | 10
La indicele șapte, există o mișcare către 10. 10 este comparat cu 80, apoi 10 și 80 sunt schimbate. 10 este comparat cu 70, apoi 10 și 70 sunt schimbate. 10 este comparat cu 60, apoi 10 și 60 sunt schimbate. 10 este comparat cu 50, apoi 10 și 50 sunt schimbate. 10 este comparat cu 30, apoi 10 și 40 sunt schimbate. 10 este comparat cu 30, apoi 10 și 30 sunt schimbate. 10 este comparat cu 20, apoi 10 și 20 sunt schimbate. O mișcare este o operație. Șapte comparații sunt șapte operațiuni. Șapte schimburi sunt șapte operațiuni. Această secțiune oferă cincisprezece operațiuni. Există un total de șaizeci și patru de operațiuni până acum (49 + 15 = 64). Rezultatul este următorul:
10 20 30 40 50 60 70 80 10 |
Treaba este gata! Au fost implicate 64 de operațiuni.
64 = 8 x 8 = 8 Două
Complexitatea timpului pentru sortarea inserției
Dacă există n elemente de sortat cu Insertion Sort, numărul maxim de operații posibile ar fi n2, așa cum sa demonstrat anterior. Complexitatea Insertion Sort Time este:
Pe Două )
Aceasta folosește notația Big-O. Notația Big-O începe cu O în majuscule, urmată de paranteze. În paranteze se află expresia pentru numărul maxim posibil de operații.
Codarea în C
Chiar la începutul scanării, primul element nu își poate schimba poziția. Programul este în esență următorul:
#includevoid insertionSort ( int A [ ] , int N ) {
pentru ( int i = 0 ; i < N; i++ ) {
int j = i;
in timp ce ( A [ j ] < A [ j- 1 ] && j- 1 > = 0 ) {
int temp = A [ j ] ; A [ j ] = A [ j- 1 ] ; A [ j- 1 ] = temperatură; // schimb
j--;
}
}
}
Definiția funcției insertionSort() folosește algoritmul așa cum este descris. Observați condițiile pentru bucla while. O funcție principală C potrivită pentru acest program este:
{
int n = 8 ;
int A [ ] = { cincizeci , 60 , 30 , 10 , 80 , 70 , douăzeci , 40 } ;
insertionSort ( A, n ) ;
pentru ( int i = 0 ; i < n; i++ ) {
printf ( '%i' , A [ i ] ) ;
}
printf ( ' \n ' ) ;
întoarcere 0 ;
}
Concluzie
Complexitatea timpului pentru sortarea prin inserare este dată astfel:
Pe Două )
Cititorul s-ar putea să fi auzit de complexitatea timpului în cazul mai rău, complexitatea timpului în cazul mediu și complexitatea timpului în cel mai bun caz. Aceste variații ale complexității timpului de sortare a inserției sunt discutate în următorul articol de pe site-ul nostru.