METODE DE SORTARE.docx

7/29/2019 METODE DE SORTARE.docx

1/8

METODE SI TEHNICI DE SORTARE A UNUI SIR

(SORTARE IN ORDINE CRESCATOARE)

1.METODA DE SORTARE PRIN INTERSCHIMBARE Aceasta metoda consta in parcurgerea sirului

utilizand doi contori (i sij) .

Fiecare element a[i] se va compara cu toateelementele din dreapta sa, elemente de forma a[j],

cuj=i+1,n Daca a[i]>a[j] atunci cele doua component e se vor

interschimba

Obs: aceasta metoda nu este eficienta deoarecedaca sirul ar fi de la inceput sortat sirul tot se

parcurge realizand n(n-1)/2 comparatii

ALGORITMUL:

Citeste n

Citeste sirul a cu n elemente

Pentru i=1,n-1 executa

Pentruj=i+1,n executa

Daca a[i]>a[j] atunci

{

aux=a[i]a[i]=a[j]

a[j]=aux

}

Afisare sir a


2/8

2.SORTAREA PRIN METODA BULELOR Metoda consta in parcurgerea sirului ori de cate ori

este nevoie pana cand sirul devine sortat sau cat

timp sirul nu este sortat Inainte de parcurgerea sirului se presupune de

fiecare daca ca sirul ar fi sortat utilizand o variabila

logica

La fiecare iteratie sirul se va parcurge pana la ultimacomponenta care nu este sortata .

Parcurgerea sirului consta in compararea de fiecaredata a doua componente de pe pozitii consecutive,

de forma a[i] si a[i+1]

Daca a[i]>a[i+1] cele doua componente se vorinterschimba

Daca la o parcurgere a sirului exista cel putin ointerschimbare inseamna ca sirul inca nu este sigur

sortat si se reia parcurgerea sirului Daca la o parcurgere a sirului nu exista nicio

interschimbare atunci cu siguranta sirul este sortat

Obs : metoda are rolul de a transporta , la fiecareparcurgere a sirului, valoare maxima dintre

componente nesortate si de a o plasa pe pozitia

finala in sirul sortat .


3/8

ALGORITMUL

V1

Citeste nCiteste sirul a cu n elemente

ok=1

k=1

Cat timp (ok=1)

{

ok=0 // se presupune ca sirul este sortat

Pentru i=1,n-k executaDaca a[i]>a[i+1] atunci

{

aux=a[i]

a[i]=a[i+1]

a[i+1]=aux

ok=1

}

k=k+1

}

Se afiseaza sirul a


4/8

V2

Citeste n

Citeste sirul a cu n elementek=1

repeta

{

ok=0 // se presupune ca sirul este sortat

Pentru i=1,n-k executa

Daca a[i]>a[i+1] atunci

{aux=a[i]

a[i]=a[i+1]

a[i+1]=aux

ok=1

}

k=k+1

} pana cand ok=0;

Se afiseaza sirul a

3.METODA DE SORTARE PRIN NUMARARE Este o metoda ineficienta ca spatiu de memorie

deoarece utilizeaza 3 siruri astfel : sirul a cel care

trebuie sortat, sirul b cel in care se vor plasa


5/8

elementele sortate si respectiv sirul nr avand

semnificatia ca nr[i]= numarul elementelor sirului a

care sunt mai mici decat a[i]

Pentru formarea sirului nr se parcurge sirul cu douaforuri avand variabilele contor i si respectivj

Fiecare element a[i] se compara cu toateelementele din dreapta sa, elemente de forma a[j]

cuj=i+1,n

Daca a[i]>a[j] creste nr[i] cu o unitate , in cazcontrar creste nr[j] cu o unitate

Dupa formarea sirului nr , orice componenta nr[i],la care se aduna o unitate reprezinta pozitia

elementului a[i] in sirul sortat

Sirul sortat b se formeaza dupa urmatoarea regula :b[nr[i]+1]=a[i], unde i=1,n

ALGORITMUL

Citeste n


Pentru i=1,n executa

Pentruj=i+1, n executa

Daca a[i]>a[j] atunci nr[i]=nr[i]+1

Altfel nr[j]=nr[j]+1

Pentru i=1,n executab[nr[i]+1]=a[i]

Afiseaza sirul b


6/8

4.METODA DE SORTARE PRIN SELECTIE DIRECTA Metoda consta in parcurgerea sirului de la prima

componenta pana la componenta n-1 inclusiv

La pasul i componentele a[1],a[2],...,a[i-1] suntdeja sortate .

La pasul i se determina valoarea minima respectivpozitia elementului minim dintrea componentele

a[i],a[i+1],...,a[n] .

Fie p pozitia elementului minim . Daca p este diferitde i atunci componentele a[i] si a[p] se vor

interschimba

ALGORITMUL

Citeste n

Citeste sirul a cu n componente

Pentru i=1,n-1 executa{

min=a[i]

p=i

Pentruj=i+1,n executa

Daca a[j]


7/8

}

}

Afiseaza sirul a

5.METODA DE SORTARE PRIN INSERTIE DIRECTA Aceasta metoda consta in parcurgerea sirului

incepand cu a doua componenta pana la final

La pasul i elementele a[1],a[2],..,a[i-1] sunt dejasortate si trebuie sa plasam elementul a[i] printre

elementele deja sortate Pentru a plasa elementul a[i] vom parcurge

urmatorii pasi :

i) Se retine a[i] intr-o variabila temporara tii) Indicele j parcurge in ordine inversa

elementele deja sortate

iii) Cat timp a[j]>t si j>0 elementul a[j] sedeplaseaza la dreapta cu o unitate, iar jdescreste cu o unitate

iv) In final t se va pozitiona pe urmatoarecomponenta pentru care nu a mai fost

adevarata conditia : a[j+1]=t

ALGORITMUL

Citeste n


Pentru i=2,n executa

{

t=a[i]

j=i-1


8/8

Cat timp a[j]>t sij>0 executa

{

a[j+1]=a[j]

j=j-1}

a[j+1]=t

}

Afiseaza sirul a

METODE DE SORTARE.docx

Documents

Transcript of METODE DE SORTARE.docx