Probleme de sortare.
Sortarea
se aplică pe larg în viaţa de toate zilele. În cadrul sistemelor automatizate
de conducere datele sunt supuse unor sortări permanente. Păstrarea datelor
sortate simplifică operaţiile de prelucrare a acestor date. Studierea metodelor
de sortare prezintă un interes deosebit datorită importanţei sale practice de
aplicare. Vom analiza 3 algoritmi de sortare:
1.
sortarea prin selecţie;
2.
sortarea prin inserţie;
3.
sortarea prin metoda bulelor.
Problemă. Fie dat
tabloul unidimensional A[1..N], N≤200, elementele căruia sunt numere întregi. Scrieţi
un program care ordonează crescător elementele tabloului.
Intrare:
numărul N şi elementele tabloului se citesc de la tastatură.
Ieşire: pe ecran se afişează elementele
tabloului ordonat, separate prin spaţiu.
Algoritmul metodei prin selecţie: se determină elementul cu valoarea minimă
din tot tabloul şi se schimbă cu locul cu primul element, în continuare se
caută elementul cu valoare minimă, începînd cu elementul al doilea al tabloului
şi se schimbă cu locul cu elementul al doilea ş.a.m.d. pînă la sfîrşitul
tabloului.
Program Metoda_prin_selectie;
Uses CRT;
Type
Lin=Array[1..200] Of Integer;
Var A:Lin;
N,I,J,L:Byte; Min:Integer;
Begin ClrScr;
Write(’Numarul de elemente=’);ReadLn(N);
WriteLn(’Introduceti elementele tabloului’);
For I:=1 To N Do
Begin
Write(’Elementul ’,I,’ este:’); ReadLn(A[I])
End;
ClrScr;
WriteLn(’Tabloul initial’);
For I:=1 To N Do Write(A[I], ’ ’);
WriteLn;
(* metoda prin selectie *)
For I:=1 To N-1 Do
Begin
Min:=A[I]; L:=I;
For J:=I+1 To N Do
If A[J]<Min Then Begin
Min:=A[J]; L:=J
End;
A[L]:=A[I]; A[I]:=Min
End;
(* sfirsitul metodei *)
WriteLn(’Tabloul ordonat crescator’);
For I:=1 To N Do Write(A[I], ’ ’);
WriteLn;
ReadLn End.
Algoritmul metodei prin inserţie: Înainte de examinarea elementului A[i],
i:=2,…,n al tabloului A[1..n] vom considera, că elementele precedente A[1],
A[2],…,A[i-1] au fost în prealabil ordonate şi se cere inserarea elementului
A[i] în locul, care îi revine între elementele ordonate anterior. În urma
operaţiei de includere se va obţine un sector din i elemente ordonate.
Următorul element A[i+1] va fi inclus între cele ordonate în
mod analog ş.a.m.d., pînă cînd va fi ordonat tot tabloul A. Pentru includerea
elementului A[i] printre cele ordonate vom compara pe rînd elementul A[i] cu
A[i-1], A[i-2],… până cînd vom găsi poziţia j (1≤j≤i), unde va fi scris
elementul A[i]. Concomitent cu compararea vom efectua şi deplasarea elementelor
A[i-1], A[i-2],…,A[j] cu o poziţie la dreapta.
Program Metoda_prin_insertie;
Uses CRT;
Type
Lin=Array[1..200] Of Integer;
Var A:Lin;
N,I,L:Byte;
X:Integer;
Begin
ClrScr;
Write(’Numarul de elemente=’);ReadLn(N);
WriteLn(’Introduceti elementele tabloului’);
For I:=1 To N Do
Begin
Write(’Elementul ’,I,’ este:’); ReadLn(A[I])
End;
ClrScr;
WriteLn(’Tabloul initial’);
For I:=1 To N Do Write(A[I], ’ ’);
WriteLn;
(* metoda prin insertie *)
For I:=2 To N Do
Begin
X:=A[I]; L:=I-1;
While (L>0) And (A[L]>X)
Do
Begin
A[L+1]:=A[L]; Dec(L)
End;
A[L+1]:=X
End;
(* sfirsitul metodei *)
WriteLn(’Tabloul ordonat crescator’);
For I:=1 To N Do Write(A[I], ’ ’);
ReadLn End.
Algoritmul metodei bulelor: se compară elementele adiacente A[i] cu
A[i+1]. Dacă nu sunt ordonate, valorile lor sunt interschimbate. Procedura se
repetă pînă cînd parcurgînd tabloul nu vom face nici o schimbare.
Program Metoda_bulelor;
Uses CRT;
Type
Lin=Array[1..200] Of Integer;
Var A:Lin;
N,I:Byte;
X:Integer; S:Boolean;
Begin
ClrScr;
Write(’Numarul de elemente=’);ReadLn(N);
WriteLn(’Introduceti elementele tabloului’);
For I:=1 To N Do
Begin
Write(’Elementul ’,I,’ este:’); ReadLn(A[I])
End;
WriteLn(’Tabloul initial’);
For I:=1 To N Do
Write(A[I], ’ ’); WriteLn;
(* metoda bulelor *)
S:=True;
While S Do Begin S:=False;
For I:=1 To N-1 Do
If A[I]>A[I+1] Then Begin
S:=True;
X:=A[I];
A[I]:=A[I+1]; A[I+1]:=X
End
End;
(* sfirsitul metodei *)
WriteLn(’Tabloul ordonat crescator’);
For I:=1 To N Do
Write(A[I], ’ ’);
ReadLn End.
Sarcini pentru realizare:
1. Este dat un tablou unidimensional cu numere intregi A[1..N], N,=200. Numarul de elemente si elementele tabloului se citesc de la tastatura. Ordonati tabloul descrescator.
2. Este dat un tablou bidimensional cu numere reale A[1..N,1..M], N,M<=20. Numarul de lini, coloane si elementele tabloului se citesc de la tastatura. Ordonati crescator fiecare linie a tabloului.
3. Este dat un tablou patrat cu numere intregi A[1..N,1..N], N<=10. Dimensiunea tabloului si elementele se citesc de la tastatura. Ordonato descrescator fiecare coloana a tabloului.
Rezultatele le transmiteti la adresa: toloaca.svetlana@gmail.com pina la data de 17.04.2020
Succese!!!
