În practică, sunt adesea folosite metode îmbunătățite de sortare, deoarece metodele directe au o viteză relativ scăzută.
Totuși, cu o lungime mică a matricei și / sau un aranjament inițial special al elementelor, metodele directe dau și un rezultat bun.
Luați în considerare principiile metodelor principale de sortare (directe).
Schimbarea prin schimb (metoda cu bule)
Perele elementelor învecinate x [k] și x [k +1] (k = 1,2, n -1) sunt comparate succesiv și dacă poziția lor relativă nu satisface condiția dată, acestea sunt rearanjate (schimbate).
Elementul maxim (minim) este căutat și transferat la sfârșitul matricei. Apoi, această metodă se aplică tuturor elementelor, cu excepția ultimei (este deja în locul ei), etc.
O altă variantă a metodei este transferul elementului găsit la începutul matricei și aplicarea ulterioară a metodei la toate elementele cu excepția primului și așa mai departe.
Matricea este împărțită în două părți: sortată și nesortată. Elementele din piesa nesortată sunt alese și inserate alternativ în piesa sortată astfel încât să nu perturbe ordonarea elementelor. La început, doar un prim element este acceptat ca parte ordonată.
Prin numărul de comparații, toate metodele au o dependență patratică de lungimea matricei
Pe număr de sarcini:
· Metodele de schimb și introducere au o dependență patratică de lungimea matricei
· Metoda de selecție are numărul de sarcini ale ordinului n * ln (n)
Experții recomandă folosirea unei metode de selecție pentru a sorta structuri complexe de date, în cazul în care un număr mare de sarcini sunt efectuate pentru o singură comparație.
În medie, metodele de inserare și selecție sunt aproximativ echivalente și de câteva ori (în funcție de lungimea matricei) sunt mai bune decât metoda de schimb.
Metodele de sortare îmbunătățite includ, de exemplu, următorii algoritmi:
ü sortarea cu incluziuni cu distante descrescatoare;
ü sortarea cu ajutorul unui copac;
ü sortarea prin împărțire (sortarea rapidă a lui Hoare)
ALGORITMELE RECURSIVE
Există cazuri în care sarcina este împărțită în subtascuri, care, la rândul lor, au aceeași structură ca sarcina principală.
În astfel de cazuri, se folosește un mecanism numit recursivitate.
Metoda de apelare a unei subrutine în care o subrutină se numește se numește recursiune.
Subrutinele care implementează recursiunea sunt numite subprograme recursive.
Să explicăm mecanismul subrutinelor recursive cu ajutorul unui exemplu clasic de recursivitate.
Calcularea factorialului unui număr.
Justificarea alegerii metodei de punere în aplicare.
Atragem atenția asupra faptului că factorialul numărului N poate fi calculat după cum urmează:
Implementăm un astfel de algoritm folosind mecanismul de recurs.
Deoarece subrutina va calcula valoarea, o vom implementa sub forma unei funcții.
funcția Fact (n: octet). întreg;
dacă n = 0 atunci Fact: = 1
altfel Fact: = n * Fapt (n-1);
Mecanismul descris mai sus este deseori numit recursiune directă.
Există un alt mecanism recursiv - recursiune indirectă.
Mecanismul este utilizat pentru a implementa următoarea situație.
Primul subrutin apelează la cel de-al doilea, care nu este încă descris.
Să arătăm situația cu un exemplu.
procedura A (var x: real);
Articole similare
Trimiteți-le prietenilor: