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

Informatica


Index » educatie » Informatica
Ordonarea unui sir - Metoda "bulelor" (Bubble Sort)


Ordonarea unui sir - Metoda "bulelor" (Bubble Sort)




I. Ordonarea unui sir - Metoda "bulelor" (Bubble Sort)

Se citeste un sir de numere intregi si se cere sa se ordoneze elementele acestui sir crescator

A: 7 , 4 , 5 , 3 , 9 , 1 (inainte)

A: 1 , 3 , 4 , 5 , 7 , 9 (dupa)

Ideea care sta la baza acestei metode este urmatoarea: se parcurge sirul, comparandu-se elementele consecutive din sir doua cate doua. Daca acestea nu sant in relatia dorita ("³" sau "£") se schimba valorile elemntelor.




Printr-o parcurgere a sirului si efectuarea comparatiilor obtinem: 


Comparam A[i] > A[i+1] daca da, le schimb

Se observa ca, dupa o parcurgere a vectorului, sirul obtinut nu este ordonat deci este necesara reluarea procedeului descris anterior.


Daca vectorul contine elemente deja ordonate se face o singura parcurgere. La efectuarea unei interschimbari se marcheaza aceasta operatie prin valoarea "FALSE" a unei variabile logice care, inainte de parcurgere va avea valoarea "TRUE". La sfarsitul algoritmului valoarea acestei variabile va fi "TRUE" , pentru ca nu va mai fi necesara nici o interschimbare.

Flowchart: Manual Operation: a[i]



NU DA

aux := a[i]

 


Diamond: ordonat=true


NU

pentru i := 1 la n

 

Flowchart: Manual Operation: a[i]
Flowchart: Alternate Process: STOP

PROGRAM BULE;

TYPE

vector = ARRAY[1..100] OF integer;

VAR

a : vector;

n , i , aux : integer;

ordonat : boolean;

BEGIN

Write ('nr de componente= ');readln(n);

FOR i := 1 TO n DO BEGIN

write ('a[', i ,']= ');

readln( a[i] );

END;

FOR i := 1 TO n DO

write (a[ i ],' ');

writeln;

REPEAT

ordonat := true;

FOR i := 1 TO n-1 DO

IF a[i] > a[i+1] THEN BEGIN

aux := a[i];

a[i] := a[i+1];

a[i+1] := aux;

ordonat := false;




END;

UNTIL ordonat = true;

FOR i := 1 TO n DO

write (a[ i ], ' ');

writeln;

END.

2. Metoda de sortare prin INSERTIE

consta in inserarea fiecarui element al vectorului la locul corespunzator in raport cu elementele sortate anterior. Principiul de baza al algoritmului de sortare prin insertie este urmatorul:

Se presupune ca subsecventa a[1], a[2], . , a[i-1] este sortata; Se cauta in aceasta subsecventa locul j al elementului a[i] si se insereaza a[i] pe pozitia j. Sa vedem cum se determina pozitia j (finala in vectorul sortat):

j = 1 daca a[i] < a

1 < j < i si sunt satisfacute relatiile a[j-1] <= a[i] < a[j]

j = i daca a[i] >= a[i-1]

Determinarea lui j se face prin cautare secventiala sau prin cautare binara. Putem observa ca aceasta tehnica de sortare se bazeaza pe metoda jucatorului de bridge

Implementare: Consideram cazul cand pozitia j este determinata prin cautare secvetiala (de la dreapta la stanga) simultan cu deplasarea elementelor mai mari ca a[i] cu o pozitie la dreapta. Aceasta deplasare se realizeaza prin interschimbari astfel incat valoarea a[i] realizeaza o deplasare la stanga pana ajunge la locul ei final.

PROGRAM Sort_Ins;

VAR a:array[1..50] of integer;

n, i, j, k, aux: integer;

BEGIN

Write('cate elem are vectorul: '); readln(n);

Writeln('Introduceti elem:');

FOR i := 1 TO n DO BEGIN

Write('a[', i ,']= '); Readln(a[i]);

END;

FOR i := 2 TO n DO begin

j := i - 1;

aux := a[i];

WHILE (j>=1) AND (a[j]>aux) DO j := j - 1;

FOR k := i DOWNTO j+1 DO a[k] := a[k-1];

a[j+1] := aux;

end;

FOR i :=1 TO n DO write(a[i],' ');

END. 

3. Metoda de sortare prin SELECTIE

consta in determinarea elementului minim si aducerea lui pe prima pozitie; apoi dintre elementele ramase in vector, se determina minimul si va fi adus pe a 2-a pozitie, s.a.m.d. pana cand toate elementele vor fi asezate in ordine.

Implementare: Vectorul se parcurge de la prima pozitie pana la pozitia n-1; se compara fiecare element de la pozitia 1 pana la pozitia n-1 cu elementele aflate dupa el. Daca elementele nu sunt in ordinea corecta, se efectueaza interschimbarea acestora, astfel incat minimul se determina comparand un element cu toate elementele care ii succed.

Algoritmul Sort_Sel;

FOR i := 1 TO n-1 DO

FOR j := i+1 TO n DO

IF a[i] > a[j] THEN begin

aux := a[i];

a[i] := a[j];

a[j] := aux;

end;

4. Metoda de sortare prin NUMARARE

Fie vectorul a = (a1, a2, . , an).

Pentru fiecare element se numara cate elemente sunt mai mici decat el. Numerele pe care le obtinem se vor memora intr-un vector k = (k1, k2, . , kn).

Pentru a obtine elementele sortate, pe baza elementelor vectorului k, vom rearanja elementele vectorului a intr-un vector b = (b1, b2, . , bn), unde b[k[i]+1] = a[i].
EX:
N=5, a=(7, 6, 3, 8, 0)
Initial: k = (0, 0, 0, 0, 0)
Iterativ: k = (3, 2, 1, 4, 0)
k = (0, 3, 6, 7, 8)
Procedeul: Pentru fiecare element incepand de la pozitia 2, se compara valoarea acestuia cu valorile aflate in vectorul a, inaintea sa. Daca elementul curent este mai mic decat un anumit element aflat inaintea sa, atunci se contorizeaza numarul de elemente mai mici pentru elementul care este mai mare, marindu-se cu o unitate acest contor; in caz contrar acesta se modifica pentru numarul curent.
Algoritmul Sort_Number;

FOR i := 1 TO n DO k[i] := 0;

For i := 2 TO n DO
FOR j := 1 To i-1 DO
IF a[i] < a[j] THEN k[j] := k[j]+1

ELSE k[i] := k[i]+1;

FOR i :=1 TO n DO b[k[i]+1] := a[i];

FOR i := 1 TO n DO write (b[i],' ');

Problema: Se considera un vector cu n elemente, ordonat crescator si un numar intreg x. Sa se insereze x in vectorul dat astfel incat acesta sa ramana ordonat.



loading...




Politica de confidentialitate


Copyright © 2019 - Toate drepturile rezervate

Informatica


Access
Adobe photoshop
Autocad
Baze de date
C
Calculatoare
Corel draw
Excel
Foxpro
Html
Internet
Java
Linux
Mathcad
Matlab
Outlook
Pascal
Php
Powerpoint
Retele calculatoare
Sql
Windows
Word


PROTECTIA JURIDICA A PROGRAMELOR PE CALCULATOR
Sistem informatic pentru urmarirea activitatii intr-o agentie imobiliare
Mentenabilitatea si mentenanta sistemelor
Sisteme de Management al Informatiei
ELABORARE PROGRAME
GRAFICA 3D - Plug-in
Inginerie Software - Definirea si specificarea cerintelor soft
ORGANIZAREA INFORMATIEI
Solutia problemei Banda
Facilitati pe tipul STRING ( functii si proceduri predefinite )



loading...