Radix Sort

Aspecte teoretice: Sortarea după ranguri (sau sortarea digitală ) este o metodă care utilizează reprezentarea binară a cheilor. Este mai eficientă decât orice altă metodă de sortare internă realizată pe asemenea calculatoare cu condiția ca N (numãrul elementelor) să nu fie prea mic si cheile să nu fie prea mici. Algoritmul Radixsort tratează cheile ca…

Bucket Sort

Aspecte teoretice: Ipoteză: Elementele a[i] sunt distribuite uniform peste intervalul [0,1). Principiul este următorul: se divide intervalul [0,1) în n subintervale de mărimi egale, numerotate de la 0 la n−1; se distribuie elementele a[i] în intervalul corespunzător: n·a[i]; se sortează fiecare pachet folosind o altă metodă; se combină cele n pachete într-o listă sortată. Analiza complexității: Cazul…

Insertion Sort

Aspecte teoretice: Inserția directă aparține familiei de tehnici de sortare care se bazează pe metoda “jucătorului de bridge”. Este un algoritm aproape la fel de simplu ca Selection sort, dar poate mai flexibil. Considerăm elementele A[1]…A[i-1] fiind sortate, inserăm elementul A[i] în locul ce îi revine. Fiind dat o tabelă A cu N elemente nesortate,…

Shell Sort

Aspecte teoretice: Sortarea cu micșorarea incrementului (shellsort) este o extensie simplă al Insertion sortului care câștigă viteză permițând schimbarea elementelor aflate departe. Ideea de bază o constituie rearanjarea elementelor din tabela A în așa fel încât, luând fiecare al h-lea element (începând de oriunde), să obținem o tabelă sortată. Astfel spunem că tabela este h-sortată….

Selection Sort

Aspecte teoretice: Selectia directã este una dintre cele mai simple metode de sortare si va lucra foarte bine pentru tabele mici, fiecare element (înregistrare), este mutat cel mult o datã.. Implementarea algoritmului este simplu. Algoritmul presupune ca la fiecare pas “i “ sa se gaseasca elementul minim dintre a[i+1], a[i+2]…a[n] si se interschimba cu a[i]….

Bubble Sort

Aspecte teoretice: Această metodă se rezumă la a compara fiecare element cu celelalte, făcându-se interschimbarea dacă elementul mai mare are indexul mai mic. Este cea mai simplă metodă de sortare și nu necesită cunoașterea detaliată a limbajului de programare. Poate fi folosită cu succes de către începători. Analiza complexității: Bubble sort este o metodă de…

Quick Sort

Aspecte teoretice: În practică algoritmul de sortare cel mai rapid este Quicksort (numit sortare rapidă), care folosește partiționarea ca idee de bază. Este mai rapid decât orice metodă de sortare simplă, se execută bine pentru fișiere sau tabele mari, dar ineficient pentru cele mici. Strategia de bază folosită este “divide et impera”, pentru că este…

Counting Sort

Aspecte teoretice: Sortarea prin numărare necesită spațiu suplimentar de memorie. Ea folosește următorii vectori: – vectorul sursă (vectorul nesortat) a; – vectorul destinație (vectorul sortat) b; – vectorul numărător (vectorul de contoare) k. Elementele vectorului sursă a[i] se copie în vectorul destinație prin inserarea în poziția corespunzătoare, astfel încât, în vectorul destinație să fie respectată relația…

Shaker Sort

Aspecte teoretice: Sortarea prin amestecare (Shaker Sort/ Cocktail Sort) reprezintă o variantă a metodei bubble sort, având următoarele îmbunătățiri: La fiecare parcurgere a subtabloului a[i],…,a[N] se memorează indicele k al ultimei interschimbări efectuate, astfel încât la următoarea trecere, un capăt al subtabloului va fi marcat de k (între 1 și k tabloul este ordonat); Se…

Heap Sort

Aspecte teoretice: Un ”Heap”, numit uneori ansamblu sau movilă este un tablou de elemente H[1..n] care are proprietatea ca pentru fiecare element H[i] cu 1<=i<=[n/2] sunt adevărate inegalitățile: H[i]>=H[2i] si H[i]>=H[2i+1] (în cazul în care 2i+1<=n. O astfel de structură poate fi vizualizată sub forma unui arbore binar aproape complet (arbore în care fiecare nod…

Pancake Sort

Aspecte teoretice: Bucătarul-șef al restaurantului este neglijent și de fiecare dată când pregătește un teanc de clătite, ele ies de dimensiuni diferite. Prin urmare, atunci când le-am livra la un client la masă, trebuie rearanjate (pentru ca cele mai mici să fie deasupra și cele mai mari să fie în partea de jos). Pentru aceasta,…

Gnome Sort

Aspecte teoretice: Gnome Sort este un algoritm de sortare propus inițial de către Dr. Hamid Sarbazi-Azad (Profesor de ingineria calculatoarelor la Sharif University of Technology) în anul 2000. Mai târziu acesta a fost descris de către Dick Grune, dându-i-se numele de Gnome Sort. Este un algoritm de sortare asemănător cu Insertion Sort, doar că etapa…