Home - Rasfoiesc.com
Educatie Sanatate Inginerie Business Familie Hobby Legal
Doar rabdarea si perseverenta in invatare aduce rezultate bune. stiinta, numere naturale, teoreme, multimi, calcule, ecuatii, sisteme


Biologie Chimie Didactica Fizica Geografie Informatica
Istorie Literatura Matematica Psihologie

Matematica


Index » educatie » Matematica
Algoritmi de sortare


Algoritmi de sortare




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.






Politica de confidentialitate


Copyright © 2019 - Toate drepturile rezervate

Matematica


Statistica


Functii periodice
Metoda aproximatiilor succesive
INEGALITATI SI INDUCTIA MATEMATICA
Monotonia si injectivitatea unei functii
Variabile aleatoare discrete
Calculul numeric al valorilor si vectorilor proprii
Derivarea functiilor elementare
Analiza factoriala a variantei
Folosirea analogiei in predarea geometriei in spatiu
Matrici inversabile