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.

Principalele metode de sortare

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

Sortarea prin insertie

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.