Home-theater-designers
Sortarea prin inserție este o tehnică care funcționează utilizând o sublistă sortată și adăugând continuu o valoare din lista nesortată până când se ordonează întreaga listă.
Algoritmul începe cu primul element de listă ca sublistă sortată. Apoi compară următorul număr cu primul. Dacă este mai mare, atunci este inserat în primul index. În caz contrar, este lăsat în index.
A treia valoare este apoi comparată cu celelalte două și apoi inserată în indexul corect. Acest proces continuă până când întreaga listă este sortată.
O privire mai atentă la sortarea inserției
Este posibil ca descrierea de mai sus să nu fi avut sens pentru dvs. Un exemplu ar trebui să vă ajute să înțelegeți mult mai bine.
Să presupunem că aveți o listă: [39, 6, 2, 51, 30, 42, 7].
Algoritmul identifică 39 ca prima valoare a sublistului sortat. Evaluarea trece apoi la a doua poziție.
Related: Programare dinamică: exemple, probleme comune și soluții
6 este apoi comparat cu 39. Deoarece 6 este mai mic decât 39, 6 este introdus în prima poziție și 39 în a doua. Noua ordine de listă este după ce prima trecere este acum:
[6, 39, 2, 51, 30, 42, 7]
Evaluarea trece acum la a treia poziție. 2 este comparat cu ultimele două numere și apoi introdus în poziția corectă. Noua ordine de listă este după ce a doua trecere este acum:
[2, 6, 39, 51, 30, 42, 7]
Pentru a treia trecere, ordinea listei este:
[2, 6, 39, 51, 30, 42, 7]
Procesul se repetă până când întreaga listă este sortată.
Vedeți diagrama de mai jos care rezumă aceste operațiuni:
Analiza algoritmului
Complexitatea în timp a sortării prin inserție este O (n2), la fel ca sortare cu bule . Numărul de comparații în cel mai rău caz este suma tuturor numerelor întregi de la 1 la (n-1), oferind o sumă pătratică.
Implementarea codului
Codul Python și Java de mai jos arată cum puteți implementa metoda de sortare prin inserție.
Piton:
def insertionSort(mylist):
for step in range(1, len(mylist)):
current_element = mylist[step]
position = step
while position > 0 and mylist[position - 1] > current_element:
mylist[position] = mylist[position - 1]
position = position - 1
mylist[position] = current_elementJava:
void insertionSort(int[] myarray) {
int n = myarray.length;
for (int x = 1; x int key = myarray[x];
int y = x-1;
while ( (y > -1) && ( myarray [y] > key ) ) {
myarray [y+1] = myarray [y];
y--;
}
myarray[y+1] = key;
}
} Codificare mai bună cu pseudocod
Exemplele de cod de mai sus au fost date fără nici un pseudocod la care puteți face referire pentru a scrie acest algoritm în alte limbi. Majorității programatorilor (inclusiv autorul) le place să ruleze la tastatură după ce li se spune „șoapte” despre modul în care funcționează un program.
Din păcate, această abordare este predispusă la erori, deoarece logica programului devine mai complicată. Cum ați dori să vă ridicați jocul de programare învățând cum să utilizați pseudocodul?
Acțiune Acțiune Tweet E-mail Ce este pseudocodul și cum te face să fii un dezvoltator mai bun?Vă luptați să învățați programarea? Faceți cunoștință cu codul învățând pseudocodul. Dar ce este pseudocodul și poate ajuta cu adevărat?
Citiți în continuare Subiecte asemănătoare- Programare
- Java
- Piton
- Tutoriale de codare
Jerome este personal scriitor la MakeUseOf. El acoperă articole despre programare și Linux. El este, de asemenea, un entuziast criptografic și ține mereu la curent industria cripto.
cum să verificați driverele învechiteMai multe de la Jerome Davidson
Aboneaza-te la newsletter-ul nostru
Alăturați-vă newsletter-ului pentru sfaturi tehnice, recenzii, cărți electronice gratuite și oferte exclusive!
Faceți clic aici pentru a vă abona