Metode de sortare

Metode de sortare


Stabilitate. O metodă de sortare este considerată stabilă dacă ordinea relativă a elementelor ce au aceeași valoare a cheii și nu se modifică în procesul de sortare.

Naturalețe. O metodă de sortare este considerată naturală dacă numărul de operații scade odată cu distanța dintre tabloul inițial și cel sortat. O măsură a acestei distanțe poate fi numărul de inversiuni al permutării corespunzătoare tabloului inițial.

Eficientă. O metodă este considerată eficientă dacă nu necesită un volum mare de resurse. Din punctul de vedere al spațiului de memorie o metodă de sortare pe loc este mai eficientă decăt una bazată pe o zonă de manevră de dimensiunea tabloului. Din punct de vedere al timpului de execuție este important să fie efectuate căt mai puține operații. În general, în analiză se iau în considerare doar operațiile efectuate asupra elementelor tabloului (comparații și mutări). O metodă este considerată optimală dacă ordinul său de complexitate este cel mai mic din clasa de metode din care face parte.

Simplitate. O metodă este considerată simplă dacă este intuitivă si ușor de înțeles.

Dupa cum bine știm, fiecare algoritm de sortare are nevoie de un anumit spațiu și un anumit timp pentru executarea algorimului. Pentru măsurarea complexității vom folosi notația complexității „O(n)” (n reprezintă numarul de comparații ale algoritmului).

Cazul Mediu - situatia in care probabilitatea duratei executiei algoritmului se apropie de media timpului de executie al algoritmului respectiv

Cazul defavorabil - situatia in care timpul de executie al algoritmului este cel mai ridicat

Memorie folositamemoria necesara sortarii vectorului