Sortare prin inserție
Construiește o parte sortată în stânga, câte o valoare pe rând. Fiecare valoare nouă e scoasă și mutată spre stânga până dă de o valoare mai mică.
- Ω(n)
- Θ(n²)
- O(n²)
- O(1)
- da
- da
Cel mai bun caz: cum crește timpul cu mărimea n a listei când intrarea e cea mai ușoară pentru acest algoritm.
Caz mediu: creșterea obișnuită a timpului. La n², de două ori mai multe valori cer cam de patru ori mai mult timp; n log n crește mai lent.
Cel mai rău caz: creșterea pe intrarea cea mai grea. Util când viteza nu are voie să scadă niciodată.
Memorie: câtă memorie suplimentară e necesară pe lângă listă. 1 înseamnă câteva variabile, n înseamnă o copie a listei.
Stabil: două valori egale își păstrează ordinea inițială. Contează când sortezi după un singur câmp al unei înregistrări.
Fără memorie suplimentară: sortează chiar în listă, fără o a doua listă.
- comparare
- mutare
- în mână
- parte sortată
- pe poziția finală
Perechi în ordine greșită: 154 (la început: 154) în ordine greșită puse în ordine Ambele axe: valori de la cea mai mică la cea mai mare
Apasă pe redare: liniile arată cum crește costul în timpul sortării
Apasă pe redare sau parcurge algoritmul pas cu pas.
Space: redă sau pauză. Săgețile stânga și dreapta: pas cu pas. Home și End: salt.
Încearcă: Alege o listă aproape sortată. Aproape nimic nu se deplasează, deci termină în foarte puțini pași.
Cum funcționează
Partea din stânga e mereu sortată. Scoți următoarea valoare, deplasezi fiecare valoare mai mare din partea sortată cu o poziție la dreapta, apoi pui valoarea în golul rămas. Așa își aranjează mulți oameni cărțile de joc în mână.
Când este o alegere bună
O alegere bună pentru liste scurte și pentru liste aproape sortate, unde e foarte rapid. Bibliotecile reale de sortare îl folosesc pentru bucățile mici ale listei, în interiorul unor metode mai rapide.