METODE DE SORTARE A VECTORILOR

ELEVI: Chiriac AndreiStoicescu AlexandruDima Stefan

 CLASA: a X-a CCOLEGIUL NATIONAL „N. GRIGORESCU” CAMPINA

INTRODUCERE

Sortarea este procesul prin care elementele setului sunt rearanjate astfel încât cheile lor să se afle într-o anumită ordine.

Metodele de sortare se clasifică în metode directe (simple); metode avansate.

Metodele directe de sortareA1. Sortarea prin selecţie

Selecţia directă este una dintre cele mai simple metode de sortare, metodă care lucrează foarte bine pentru număr mic de elemente, fiecare element fiind mutat cel mult o dată.Algoritmul presupune ca la fiecare pas i să se găsească elementul minim dintre T[i+1], T[i+2],…, T[n] şi să se interschimbe cu T[i].

Metodele directe de sortareA1. Sortarea prin selecţie - ALGORITM

Algoritmul metodei de sortare prin selecţie este următorul: 

pentru i 1, n-1 executăk imin T[i]

pentru j i +1, n executădacă T[j] < min atunci

min T[j] k j

sfârşit dacăsfârşit pentru

T[k] T[i]T[i] min

sfărşit pentru 

Metodele directe de sortareA2. Sortarea prin inserţie

Inserţia directă aparţine familiei de tehnici de sortare care se bazează pe metoda „jucătorului de bridge”. Înainte de a examina înregistrarea T[i], vom considera că înregistrările precedente T[1], …, T[i-1] au fost deja sortate, apoi vom insera T[i] în locul ce îi revine între înregistrările sortate anterior.

 Se consideră 1 ≤ i ≤ n şi înregistrările T[1], T[2], …, T[i-1] aranjate astfel încât T[1] ≤ T[2] ≤ … ≤ T[i-1]. Vom compara pe rând noua cheie T[i] cu T[i-1], T[i-2], …, până ce vom descoperi că T[i] trebuie inserat între înregistrările T[k] şi T[k+1]; apoi deplasăm înregistrările T[k+1], ..., T[i+1] cu un spaţiu şi introducem noua înregistrare în poziţia k+1. Deoarece T[i] „intră la locul său” această metodă a fost denumită metoda de cernere sau scufundare.

Metodele directe de sortareA2. Sortarea prin inserţie - ALGORITM

Algoritmul metodei de sortare prin inserţie este: pentru i 2, n execută

k 1 cât timp T[k] < T[i] execută

k k +1 sfârşit cât timp dacă i ≠ k atunci

temp T[i] pentru j i, k+1, -1 execută

T[ j] T[ j-1 ] sfârşit pentru

T[k] temp sfârşit dacă  sfârşit pentru

Metodele directe de sortareA3. Sortarea prin metoda bulelor (Bubble Sort)

Această metodă se rezumă la a compara fiecare element cu celelalte, făcându-se interschimbarea dacă elementul mai mare are indexul mai mic. Se repetă parcurgerea vectorului, cu interschimbul elementelor care nu respectă relaţia de ordine, până se ajunge la o parcurgere fără interschimb. Pentru a reţine dacă au loc interschimbări între elemente, se foloseşte o variabilă inv cu două valori posibile: 0(fals), dacă nu a avut loc nici un interschimb şi 1(adevărat) dacă s-a realizat cel puţin un interschimb.La prima trecere prin vector se vor analiza perechile de elemente consecutive (T[i], T[i+1]), cu i = 1, 2, …, n-1 şi pentru fiecare pereche, dacă este cazul, se va face interschimbul.

Metodele directe de sortareA3. Sortarea prin metoda bulelor (Bubble Sort)- ALGORITM

Algoritmul de sortare prin metoda bulelor este următorul: repetă

inv falspentru i 1, n -1 executădacă T[i] > T[i+1] atunciaux T[i]T[i] T[i+1]T[i+1] auxinv adevaratsfârşit dacăsfârşit pentru

până când inv=fals

Metodele directe de sortare A4. Sortarea prin numărare

Această sortare se bazează pe idea că elementul de pe poziţia j din secvenţa finală sortată este mai mare decât (j-1) dintre celelalte elemete. Adică, dacă ştim că o anumită cheie este mai mare decat alte 20 de chei, înregistrarea respectivă trebuie aşezată în poziţia 21.Deci, se compară fiecare pereche de chei, numărând câte vor fi mai mici decât fiecare cheie particulară.Calea de a face comparaţiile este următoarea: compară ((T[i] cu T[j]) pentru 1 ≤ j ≤ n) pentru 1 ≤ i ≤ n.

Metodele directe de sortareA4. Sortarea prin numărare-ALGORITM

Algoritmul metodei de sortare prin numărare este următorul: pentru i 1, n execută

NR[i] 1 sfârşit pentru pentru i 1, n execută pentru j 1, n execută

dacă T[i] > T[j] atunci NR[i] NR[i] + 1 sfârşit dacă  sfârşit pentru sfârşit pentru pentru i 1, n executăVS[ NR[i] ] T[i] sfârşit pentru

Algoritmi avansaţi de sortareB1. Sortarea prin interclasare

Această metodă de sortare se bazează pe tehnica Divide et Impera. Principiul metodei este următorul: Divide – partiţionarea problemei în mai multe subprobleme. În cazul algoritmului nostru, partiţionarea unui vector iniţial T[p], …, T[q] în doi subvectori T[p], …, T[m] şi T[m+1], …, T[q], unde m se obţine prin formula [(p+q)/2]Impera – rezolvarea problemelor obţinute la pasul anterior. Se va apela recursiv algoritmul pentru cele două partiţii create. Dacă subproblema obţinută este cu rezolvare directă, atunci se va rezolva (dacă partiţia are 1 element atunci problema este rezolvată, iar dacă sunt 2 elemente nesortate, atunci se va face interschimbarea acestora).Combine – combinarea soluţiilor obţinute pentru subprobleme într-o soluţie pentru problema iniţială. Această etapă se realizează prin procedeul numit interclasare: având doi vectori sortaţi, se interclasează elementele şi se obţine un vector ordonat care conţine elementele celor doi vectori iniţiali).

 

Algoritmi avansaţi de sortareB1. Sortarea prin interclasare-ALGORITM

Procedura DIVIMP (T, p, q) dacă q - p 1 atunci

daca T[p] > T[q] atunci aux T[p]T[p] T[q]T[q] aux

sfârşit dacă altfelm [(p+q)/2]DIVIMP ( T, p, m)DIVIMP (T, m+1, q)INTERCLASARE ( T, p, q, m)

sfârşit dacă sfarsit

Algoritmi avansaţi de sortareB2. Sortarea rapidă- ALGORITM

Această metodă de sortare se bazează pe tehnica Divide et Impera

Procedura QuiqkSort (T, li, ls)dacă li < ls atunci

Partitionare (T, li, ls, k)QuickSort (T, li, k-1)QuickSort (T, k+1, ls)

sfârşit dacăsfârşit

VA MULTUMIM PENTRU RABDARE