![]() | Biologie | Chimie | Didactica | Fizica | Geografie | Informatica |
Istorie | Literatura | Matematica | Psihologie |
Algoritmi de sortare
Problema sortarii consta in ordonarea unui tablou (vector) de elemente de acelasi tip ,dupa un anumit criteriu .
Se pleaca de la o colectie de date - articole, fiecare din elemente continand aceleasi tipuri de informatii. Dintre aceste informatii, dupa una, de un anumit tip, se doreste ordonarea, ea devine cheia dupa care se face ordonarea.
Acestea sunt:
1.Sortarea prin numarare consta in a numara pentru fiecare element al structurii cate elemente strict mai mici decat el exista. Pe baza acestor determinari si prin folosirea unui vector auxiliar se reorganizeaza vectorul initial.
Pentru a ordona un
vector cu ajutorul metodei de sortare prin numarare se foloseste un
vector suplimentar , unde
reprezinta cate elemente mai mici decat
avem in
vectorul
Ideea generala consta in a considera pe rand fiecare element al sirului si de a-l insera in subsirul ordonat, creat anterior din elementele precedente.
2.Sortarea prin insertie directa elementul
se
insereaza in subsirul
Astfel, se compara
cu
,.. pana ajungem la
cu
proprietatea ca
. Ca urmare, vom insera pe
dupa
. Operatiunea de inserare implica
deplasarea spre dreapta a unei secvente.
3.Sortarea prin insertie binara
reprezinta o imbunatatire a metodei de sortare prin
insertie directa (un algoritm de depistare a pozitiei i unde va fi inserat Se foloseste un algoritm
de cautare binara: se compara
cu
Daca
atunci se
restrang cautarile asupra primei jumatati.
Sortare prin interschimbare consta in modificari succesive de pozitii intre doua elemente ale sirului pana la ordonarea totala. Exemple: metoda bulelor, sortare rapida.Fiecare din elementele x[1],x[2], . .x[n-1] va juca pe rand rolul unui asa numit pivot.Parcugem pivotii intr-un ciclu in care contorul i ia pe rand valorile 1,2,3, . n-1 si la fiecare pas al ciclului :
-Comparam pivotul x[i] cu toate elementele aflate dupa el,x[i+1],..,x[n].Parcurgem pozitiile acestor elemente intr-un alt ciclu cu contorul j=i+1, . ,n , si ,pentru fiecare element x[j] ,daca este mai mic decat pivotul x[i] ,atunci interschimbam x[j] cu x[i]
Cand un pivot si-a incheiat rolul ,partea din vector pana la elementul x[i] inclusiv,este sortata crescaror.Dupa ce toate elementele x[1],x[2], ,x[n-1] au fost pivoti,vectorul este in intregime sortat.
4.Metoda bulelor Ideea care sta la baza metodei consta in formarea de perechi de elemente succesive in vectorul dat.Elementele fiecarei perechi vor fi ordonate crescator,iar prin mai multe parcurgeri ale vectorului se va obtine un sir in intregime sortat.
5.Sortarea rapida(quick-sort) Algoritmul consta in impartirea repetata a vectorului dat in doi subvectori avand proprietatea ca orice element din subvectorul stang este mai mic decat orice element din subvectorul drept.Evident,este vorba de un algoritm divide et impera,avand in vedere ca impartim problema data in doua subprobleme de acelasi tip.
6.Sortarea prin selectie Ideea generala este de a plasa la fiecare pas un element al vectorului
pe pozitia sa finala. Metoda selectiei directe: se compara cu restul
elementelor din sirul dat, daca se gaseste un element
astfel
incat
atunci se
interschimba
cu
. Cand ajungem la ultimul element pe prima
pozitie se va afla cel mai mic element.
7.Sortarea prin interclasare consta in interclasarea succesiva de secvente ordonate crescator ale vectorului inttial pana se obtine o ultima secventa ordonata crescator formata cu toate elementele vectorului initial
Sortarea prin interclasare: se imparte vectorul in
doua parti care se ordoneaza, dupa care se
interclaseaza vectorii sortati.
Copyright © 2025 - Toate drepturile rezervate