Cel mai bun răspuns
În primul rând, ar trebui să ne întrebăm de ce să folosim un algoritm de sortare pătratică atunci când există alternative asimptotic mai rapide, cum ar fi mergesort sau rapid. Pentru tablourile mici (mai puțin de 20-30 de elemente), atât sortarea de inserție, cât și sortarea de selecție sunt de obicei mai rapide decât alternativele O (n * logn). De fapt, mulți algoritmi de sortare pe baza paradigmei de divizare și cucerire trec la sortare prin inserție sau sortare prin selecție atunci când matricea este suficient de mică.
Între sortare prin inserție și sortare prin selecție, când să folosești care?
De obicei, sortarea prin inserție va efectua mai puține comparații decât sortarea de selecție, în funcție de gradul de „sortare” a matricei. În timp ce sortarea de selecție trebuie să scaneze părțile rămase ale tabloului atunci când plasați un element, sortarea prin inserție scanează doar câte elemente este necesar. Asta înseamnă că atunci când matricea este deja sortată sau aproape sortată, sortarea prin inserție se efectuează în timp O (n).
Un avantaj al sortării de selecție față de sortarea prin inserție este că numărul de scrieri (swap) este în O (n), în timp ce în sortare prin inserție este în O (n ^ 2). Acest lucru poate fi important dacă sortați pe memoria Flash, de exemplu, deoarece scrierile reduc durata de viață a memoriei Flash.
Răspundeți
Într-o sortare de selecție, pentru fiecare element care urmează să fie pentru a fi adăugat la secțiunea sortată, trebuie să scanați întreaga parte nesortată a listei pentru a găsi elementul minim rămas. Într-o sortare de inserare, trebuie să căutați secțiunea sortată pentru a afla unde merge următorul element, dar căutarea se termină după ce ați găsit punctul de inserare (aproximativ jumătate) prin secțiunea sortată în medie).
Deci, sortarea selecției necesită în medie comparații N / 2 pentru fiecare element care trebuie adăugat la secțiunea sortată, iar sortarea inserției necesită în medie comparații N / 4. Cu toate acestea, sortarea prin inserție are o penalizare suplimentară în timp la sortarea unei matrice. Fiecare dintre comparațiile N / 4 (în medie) necesită ca elementul să fie deplasat în sus, astfel încât să existe și mutări N / 4, precum și comparații. Sortarea prin selecție necesită doar un singur swap.
În general, sortarea prin inserție câștigă de obicei cursa. Acest lucru este valabil mai ales dacă există funcții rapide de „deplasare bloc” în jurul (pentru tablouri).