Metode de Sortare

Seminar
6/10 (1 vot)
Conține 1 fișier: doc
Pagini : 4 în total
Cuvinte : 1023
Mărime: 20.91KB (arhivat)
Cost: Gratis

Extras din document

In cazul unui vector sortat elementul cu indice i este succesorul celor cu indici de la 0 la i-1 si predecesorul celor cu indici de la i+1 la n-1.

Sortarea prin selectie

Sa consideram un vector in care elementele cu indici de la 0 la i-1 sunt deja sortate. Pentru a continua procesul de sortare, dintre elementele ramase (cu indici de la i pana la n-1) trebuie gasit predecesorul tuturor celorlalte (cu indice ipg) si adus in pozitia i.

i-1 i ipg n-1

. . . . . . . . . . .

elemente sortate elemente nesortate

Sortarea prin selectie a unui vector de intregi:

i Vectorul prelucrat ipg

0 10 5 6 12 3 7 12 9 4

1 3 5 6 12 10 7 12 9 1

2 3 5 6 12 10 7 12 9 2

3 3 5 6 12 10 7 12 9 5

4 3 5 6 7 10 12 12 9 7

5 3 5 6 7 9 12 12 10 7

6 3 5 6 7 9 10 12 12 6

In acest exemplu elementul selectat dintr-o secventa este marcat prin hasurare, iar locul in care trebuie plasat acesta este marcat prin chenar dublu.

Algoritmul SelSort (X, N)

pentru i de la 0 la n-2

{ determina ipg = indice predecesor global (ipg  [i, n-1] )

daca ipg > i atunci

inverseaza x[i] cu x[ipg], folosind zona tampon aux;

}

Sortarea prin insertie

In cazul sortarii prin insertie se considera ca vectorul este sortat pana la o anumita pozitie si se incearca inserarea urmatorului element pe pozitia potrivita. Daca vectorul ar avea un singur element, el ar fi deja sortat; in cazul unui vector cu 2 elemente, care nu respecta relatia de ordine, este suficienta inversarea acestora. Sa presupunem ca vectorul are mai mult de 2 elemente si ca am sortat deja, in ordine crescatoare, primele i-1 elemente. Pentru a extinde sortarea la i elemente este necesara deplasarea la dreapta, cu o pozitie, a tuturor succesorilor elementului i, urmata de inserarea sa in pozitia corespunzatoare. Aceasta presupune compararea elementului i cu cele deja sortate, situate la stanga sa. Daca aceasta operatie se efectueaza de la dreapta spre stanga, atunci ea poate fi combinata cu cea de deplasare.

j j+1 i-1 i

. . . . . . . . . . . .

predecesori aux succesori aux  se deplaseaza la dreapta aux

Sortarea prin insertie a unui vector de intregi:

i Vectorul prelucrat

1 10 5 6 12 3 7 12 9

2 5 10 6 12 3 7 12 9

3 5 6 10 12 3 7 12 9

4 5 6 10 12 3 7 12 9

5 3 5 6 10 12 7 12 9

6 3 5 6 7 10 12 12 9

7 3 5 6 7 10 12 12 9

8 3 5 6 7 9 10 12 12

In acest exemplu elementul care trebuie inserat intr-o secventa deja sortata este marcat cu un chenar dublu, iar succesorii sai, care trebuie deplasati spre dreapta, sunt marcati prin hasurare.

Algoritmul InserSort (x, n)

pentru i de la 1 la n-1

{ copiaza x[i] in aux;

deplaseaza la dreapta succesorii lui aux

inlocuieste ultimul element deplasat cu cel din aux

}

Sortarea prin metoda bulelor imbunatatita

Aceasta metoda se bazeaza pe faptul ca intr-un vector sortat toate perechile de elemente consecutive trebuie sa respecte relatia de ordine. Daca aceasta relatie nu este respectata, atunci elementele trebuie interschimbate. Verificarea perechilor trebuie reluata pana cand nu mai este necesara nici o interschimbare, dar fiecare noua etapa de verificare se poate opri la perechea din fata celei care a necesitat ultima interschimbare (u_inv), deoarece, evident, perechile urmatoare respecta relatia de ordine.

Sortarea prin metoda bulelor imbunatatita a unui vector de intregi:

lim ip Vectorul prelucrat u_inv

6 0 10 5 6 12 3 7 12 0

1 5 10 6 12 3 7 12 1

2 5 6 10 12 3 7 12 1

3 5 6 10 12 3 7 12 3

4 5 6 10 3 12 7 12 4

5 5 6 10 3 7 12 12 4

4 0 5 6 10 3 7 12 12 0

1 5 6 10 3 7 12 12 0

2 5 6 10 3 7 12 12 2

3 5 6 3 10 7 12 12 3

3 0 5 6 3 7 10 12 12 0

1 5 6 3 7 10 12 12 1

2 5 3 6 7 10 12 12 1

1 0 5 3 6 7 10 12 12 0

0 3 5 6 7 10 12 12

Fiecare pereche analizata este evidentiata printr-un chenar dublu, hasurat in cazul in care elementele trebuie interschimbate. Limita fiecarei etape de verificare este marcata prin linie dubla mai groasa.

Preview document

Metode de Sortare - Pagina 1
Metode de Sortare - Pagina 2
Metode de Sortare - Pagina 3
Metode de Sortare - Pagina 4

Conținut arhivă zip

  • Metode de Sortare.doc

Alții au mai descărcat și

Probleme Seminar Sisteme Digitale

PROBLEMA 1 Se consideră funcţia booleană descrisă de Tabelul de adevăr: Pentru această funcţie se cer următoarele: 1.1. să se precizeze dacă...

Html Seminar 7

font-family: font1, font2... stabilirea unei liste de fonturi disponibile, separate prin caracterul virgulă font-size: „n” pt unde „n” reprezintă...

Proiectarea Sistemelor Informationale

Notiuni de baza si principii de testare a SI Definitie. Testarea – este un proces de executie a programei cu scopul de a evidentia erorile....

Baze de Date

Facilitati Access Pentru Dezvoltarea Aplicatiilor Access Faciliteza Dezvoltarea si Exploatarea Bazelor De Date Punând La Dispozitia...

Bazele Informaticii

In general, un sistem se defineste ca fiind un ansamblu de elemente fizice si logice interconectate si interconditionate prin relatii fizice,...

SADD

Disciplina SADD face parte din grupul disciplinelor de specialitate Disciplina se predă la domeniul de licenţă Inginerie industrială, la...

Sisteme de Operare

7.Interogari 7.1. Tipuri de interogari Interogarile sunt acele obiecte din baza de date care ne permit sa introducem, sa actualizam si sa aranjam...

Te-ar putea interesa și

Studii privind Stabilirea Perioadei Optime de Altoire a Soiurilor de Măr

Introducere Cultura pomilor şi arbuştilor fructiferi, parte componentă a sectorului horticol şi, implicit, a agricuturii din România, are o veche...

Sortari in Structuri de Date

Metodele de sortare cele mai des folosite pot fi clasificate în doua categorii: METODE DIRECTE si METODE AVANSATE. METODELE DIRECTE se bazeazã...

Sisteme industriale de sortare în funcție de structura unor produse agroalimentare impure pulverulente

Noţiuni introductive Pentru o mai bună cristalizare a unor noţiuni strict necesare pregătirii profesionale a specialistului din domeniul...

Injectorul

INJECTORUL Injectorul este ansamblul care serveste la pulverizarea fina si omogena, precum si la injectarea combustibilului in camera de ardere....

Precizia de Prelucrare și Asamblare a Pieselor Metalice

Argument Tema proiectului meu este,, Precizia de prelucrare şi asamblare a pieselor metalice”face parte integrantă din domeniul pregătirii mele...

Gestionarea deșeurilor

ARGUMENT În mod tradiţional, obiectivul ingineriei mediului era îndepărtarea deşeurilor domestice din motive sanitare. În majoritatea oraşelor...

Sortarea

1.Introducere Sortarea este definită ca operația de separare pe mai multe sortimente sau fracții a produsului de bază (materiei prime) după...

Comportamentul și psihologia consumatorului

I . NOŢIUNILE ŞI DIMENSIUNILE COMPORTAMENTULUI CONSUMATORULUI 1. Noţiuni şi concepte 2. Procese elementare în abordarea comportamentului...

Ai nevoie de altceva?