Sortarea binsort. Determinarea distributiei cheilor.

Sortarea binsort. Determinarea distributiei cheilor

In general algoritmii de sortare bazati pe metode avansate au nevoie de O(n  log n) pasi pentru a sorta n elemente.

Trebuie precizat insa faptul ca acest lucru este valabil in situatia in care nu exista nici o alta informatie suplimentara referitoare la chei, decat faptul ca pe multimea acestora este definita o relatie de ordonare, prin intermediul careia se poate preciza daca valoarea unei chei este mai mica respectiv mai mare decat o alta.

Dupa cum se va vedea in continuare, sortarea se poate face si mai rapid decat in limitele performantei O(n  log n), daca:

o      Exista si alte informatii referitoare la cheile care urmeaza a fi sortate 

o      Si se renunta macar partial la constrangerea de sortare 'in situ'.

Spre exemplu, se cere sa se sorteze un set de n chei de tip intreg, ale caror valori sunt unice si apartin intervalului de la 1 la n.

Definitia 19: Un graf se numeste conex daca oricare ar fi doua varfuri x si y, exista un lant ce le leaga.

5. Grafuri hamiltoniene

Definitia 20: Fie graful G(X,U). Daca exista un lant elementar care contine toate varfurile grafului, lantul se numeste lant hamiltonian.

Definitia 21: Daca intr-un lant hamiltonian varful initial si varful final coincid, lantul se numeste ciclu hamiltonian, iar graful ce contine un ciclu hamiltonian se numeste graf hamiltonian.

Termenul de ciclu hamiltonian a fost folosit pentru prima data in anul 1857 de in situ', element care prezinta interes din punctul de vedere al tehnicilor analizate.

o      Astfel, fiind dat tabloul a de dimensiune n, ale carui elemente au respectiv cheile 1, , n, se baleeaza pe rand elementele sale.

o      Daca elementul a[i] are cheia j, atunci se realizeaza interschimbarea lui a[i] cu a[j].

o      Fiecare interschimbare plaseaza elementul aflat in locatia i exact la locul sau in tabloul ordonat, fiind necesare in cel mai rau caz 3  n miscari pentru intreg procesul de sortare.