Există mai mulți algoritmi de bază pentru rezolvarea problemei sortării unui tablou. Una dintre cele mai faimoase dintre ele este sortarea prin inserție. Datorită clarității și simplității sale, dar eficienței reduse, această metodă este utilizată în principal în predarea programării. Vă permite să înțelegeți mecanismele de sortare de bază.
Descrierea algoritmului
Esența algoritmului de sortare prin inserție este că în interiorul matricei inițiale se formează un segment ordonat corespunzător. Fiecare element este comparat unul câte unul cu piesa verificată și introdus la locul potrivit. Astfel, după ce parcurg toate elementele, acestea se aliniază în ordinea corectă.
Ordinea de selectare a elementelor poate fi oricare, acestea pot fi selectate arbitrar sau în funcție de un algoritm. Cel mai adesea, enumerarea secvențială este folosită de la începutul matricei, unde se formează un segment ordonat.
Începutul sortării ar putea arăta astfel:
- Ia primul element al matricei.
- Deoarece nu există nimic cu care să-l comparați, luați elementul în sine așa cum a fost comandatsecvență.
- Accesați al doilea articol.
- Compară-l cu primul pe baza regulii de sortare.
- Dacă este necesar, schimbați elementele pe alocuri.
- Luați primele două elemente ca o secvență ordonată.
- Accesați al treilea articol.
- Compară-l cu al doilea, schimbă-l dacă este necesar.
- Dacă se face înlocuirea, comparați-o cu prima.
- Ia trei elemente ca o secvență ordonată.
Și așa mai departe până la sfârșitul matricei originale.
Sortare de inserare în viața reală
Pentru claritate, merită să oferiți un exemplu despre modul în care acest mecanism de sortare este utilizat în viața de zi cu zi.
Ia, de exemplu, un portofel. Billete de o sută, cinci sute și o mie de dolari zac în dezordine în compartimentul pentru bancnote. Aceasta este o mizerie, într-un astfel de amestec este dificil să găsești imediat bucata de hârtie potrivită. Gama de bancnote trebuie sortată.
Prima este o bancnotă de 1000 de ruble, iar imediat după aceasta - 100. Luăm o sută și o punem în față. Al treilea la rând este de 500 de ruble, locul potrivit pentru el este între o sută și o mie.
În același mod, sortăm cărțile primite atunci când jucăm „Nebunul” pentru a facilita navigarea lor.
Operatori și funcții de ajutor
Metoda de sortare prin inserție ia ca intrare un tablou inițial de sortat, o funcție de comparație și, dacă este necesar, o funcție care determină regula de enumerare a elementelor. Cel mai des folosit în schimbinstrucțiune de buclă obișnuită.
Primul element este în sine un set ordonat, deci comparația începe de la al doilea.
Algoritmul folosește adesea o funcție de ajutor pentru a schimba două valori (swap). Utilizează o variabilă temporară suplimentară, care consumă memorie și încetinește puțin codul.
O alternativă este deplasarea în masă a unui grup de elemente și apoi introducerea celui curent în spațiul liber. În acest caz, trecerea la următorul element are loc atunci când comparația a dat un rezultat pozitiv, ceea ce indică ordinea corectă.
Exemple de implementare
Implementarea specifică depinde în mare măsură de limbajul de programare utilizat, de sintaxa și structurile acestuia.
Implementare C clasică folosind o variabilă temporară pentru a schimba valori:
int i, j, temp; for (i=1; i =0; j--) { if (array[j] < temp) break; matrice[j + 1]=matrice[j]; matrice[j]=temp; } }
Implementare PHP:
funcție insertion_sort(&$a) { pentru ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }
Aici, mai întâi, toate elementele care nu se potrivesc cu condiția de sortare sunt deplasate la dreapta, iar apoi elementul curent este inserat în spațiul liber.
Cod Java folosind bucla while:
public static void insertionSort(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=arr[prevKey]; arr[prevKey]=currElem; prevKey--; } } }
Semnificația generală a codului rămâne neschimbată: fiecare element al matricei este comparat secvențial cu cele anterioare și schimbat cu ele dacă este necesar.
Timp de rulare estimat
Evident, în cel mai bun caz, intrarea algoritmului va fi o matrice deja ordonată în mod corect. În această situație, algoritmul va trebui pur și simplu să verifice fiecare element pentru a se asigura că este în locul potrivit fără a face schimburi. Astfel, timpul de rulare va depinde direct de lungimea matricei originale O(n).
Intrarea în cel mai rău caz este o matrice sortată în ordine inversă. Acest lucru va necesita un număr mare de permutări, funcția de rulare va depinde de numărul de elemente la pătrat.
Numărul exact de permutări pentru o matrice complet neordonată poate fi calculat folosind formula:
n(n-1)/2
unde n este lungimea matricei originale. Astfel, ar fi nevoie de 4950 de permutări pentru a aranja 100 de elemente în ordinea corectă.
Metoda de inserare este foarte eficientă pentru sortarea matricelor mici sau parțial sortate. Cu toate acestea, nu este recomandat să-l aplicați peste tot din cauza complexității ridicate a calculelor.
Algoritmul este folosit ca auxiliar în multe alte metode de sortare mai complexe.
Sortați valori egale
Algoritmul de inserare aparține așa-numitelor sortări stabile. Inseamna,că nu schimbă elemente identice, ci păstrează ordinea lor inițială. Indicele de stabilitate este în multe cazuri important pentru o comandă corectă.
Cele de mai sus este un exemplu vizual excelent de sortare prin inserare într-un dans.
