Sortare prin numSortare prin număărarerare

Silaghi Ioana SorinaSilaghi Ioana Sorina

Clasa a XI-a B Clasa a XI-a B

EnunţulEnunţul problemeiproblemei

Se dă un şir de numere intregi.Se cere Se dă un şir de numere intregi.Se cere sortarea lor în ordine crescătoare.sortarea lor în ordine crescătoare.

ExempluExemplu

7 2 3 -1A:

i:=1 7

j

= 7

7

k:=0

> 2

7

7

>

>

3

-1

k:=1

k:=2

k:=3

7

k+1

i:=2

2

2

2

2

=

<

<

>

7

2

3

-1

k:=0

k:=0

k:=0

k:=172

k+1

i:=3

33

3

3

3

<

>

>

=

7

2

-1

k:=0

k:=1

k:=1

k:=22 3 7

k+1

i:=4

-1

-1

-1

-1

-1

<

<

<

=

7

2

3

k:=0

k:=0

k:=0

k:=0

732-1

k+1

AlgoritmulAlgoritmul

Metoda de sortare prin numărare constă în Metoda de sortare prin numărare constă în construirea unui nou tablou B care are aceaşi construirea unui nou tablou B care are aceaşi dimensiune ca şi tabloul A , în care depunem dimensiune ca şi tabloul A , în care depunem elementele din A ordonate crescător.elementele din A ordonate crescător.

Vom analiza fiecare element şi îl vom compara cu Vom analiza fiecare element şi îl vom compara cu fiecare alt element din şir pentru a putea reţine în fiecare alt element din şir pentru a putea reţine în variabila K numărul elementelor care sunt mai mici variabila K numărul elementelor care sunt mai mici decât elementul considerat astfel vom afla poziţia decât elementul considerat astfel vom afla poziţia pe care trebuie să-l punem pe acesta în şirul B.pe care trebuie să-l punem pe acesta în şirul B.

Dacă în problemăavem nevoie de şirul ordonat tot Dacă în problemăavem nevoie de şirul ordonat tot în tabloul A,vom copia în A întreg tabloul B prin în tabloul A,vom copia în A întreg tabloul B prin A:=B. A:=B.

ImplementareaImplementarea

AA:array[:array[1..1001..100]of integer;-şirul care ]of integer;-şirul care trebuie ordonattrebuie ordonat

NN:integer;-numarul elementelor lui A:integer;-numarul elementelor lui A BB:array[1..100]of integer;-şirul gata :array[1..100]of integer;-şirul gata

ordonatordonat KK:integer;-numărul elementelor mai :integer;-numărul elementelor mai

mici decât elementul considerat;mici decât elementul considerat;

ProgramulProgramul Program numărare;Program numărare;Type vector=array[1..100]of integer;Type vector=array[1..100]of integer;Var a:vector;Var a:vector;I,j,n:integer;I,j,n:integer;Procedure num(var a:vector;n:integer);Procedure num(var a:vector;n:integer); var b:vector;var b:vector; k:integer;k:integer;BeginBeginFor i:=1 to n do beginFor i:=1 to n do begin k:=0;k:=0;For j:=1 to n do For j:=1 to n do If (a[i]If (a[i]>a[j]>a[j])) and (i<>j) and (i<>j) then k:=k+1; then k:=k+1; b[k+1]:=a[i];b[k+1]:=a[i]; end;end; aa:=:=bb;;end;end; BEGINBEGINWrite(Write(‘‘n=n=‘‘);readln(n););readln(n);For i:= 1 to n do beginFor i:= 1 to n do begin write(write(‘a[‘,i,’]=‘‘a[‘,i,’]=‘));readln(a[i]);;readln(a[i]); end;end;Num(a,n);Num(a,n);For i:=1 to n do write(a[i]);For i:=1 to n do write(a[i]);Readln;Readln;end.end.