xSortLab je aplet sa animacijama metoda sortiranja. Kliknite na dugme da ga aktivirate.

Browser ne podrzava Javu!

Jednodimenzionalni nizovi

• Zamislite da pišete program koji obradjuje 500 podataka (npr. svaki podatak je prosečna temperatura jednog od tih 5000 dana) i da morate svakom od njih dati jedinstvenu oznaku. Kako biste to napravili?

• U programiranju kolekcija sličnih elemenata se naziva niz, a redni broj odredjenog elementa niza se naziva indeks.

Napomena: indeks može biti bilo koji nabrojivi tip a ne samo integer

• Ako u programu želimo raditi s više varijabli istog tipa, da ne bi koristili više oznaka za navedene varijable i da bi jednostavnije učitali i obradili takvu vrstu varijabli koristimo nizove i naredbu var.

Primer 1

Dani	1	2	3	4	5	...	...	...	500
Dani	12	23	18	17	16	...	...	...	15

program Temperature;

var
Dani: array[1..500] of Integer;

begin

   Dani[1] := 12;
   Dani[3] := 18;
   Dani[2] := 23;
   Dani[1] := 12;
   Dani[3] := 18;
   Dani[3] := 18;
   Dani[4] := 17;
   Dani[5] := 16;

...

Dani[500] := 15;
end.

• Označavanje jednog elementa niza

• Ime_niza[indeks] --> u našem primeru recimo Dani[3]

• Dani[3]: = 12 je prvi element niza.

• Dani je naziv niza

• Koja je vrednost varijable Dani[5]?

• Mora se unapred navesti koliko će elemenata biti u nizu

var
Dani: array[1..500] of Integer;

• rezerviše se 500 lokacija u memoriji računara u koje se mogu upisivati celobrojne vrednosti.

• Indeksi elemenata niza mogu biti aritmetički izrazi.

• Npr., Dani[n+3] gde n+3 mora biti celobrojno.

• Elementu niza može se dodeliti i vrednost nekog drugog elementa istog niza. (ili nekog niza istog tipa)

• Npr., Dani[5]:=Dani[2];

Primer 2

Temperatura je beležena za 3 dana i bila je:

Dan 1: 12

Dan 2: 23

Dan 3: 18 stepeni

• Napišite program kojim će se uneti ove vrednosti u niz Dani i izračunati i ispisati prosek temperatura

program Temperature;
var
Dani: array[1..3] of Integer;

Prosek:Real;
begin
write(‘Unesi temperaturu za dan 1:’); readln(Dani[1]);

write(‘Unesi temperaturu za dan 2:’); readln(Dani[2]);

write(‘Unesi temperaturu za dan 3:’); readln(Dani[3]);

Prosek:= (Dani[1]+ Dani[2]+ Dani[3])/3;

write(‘Prosecna temperatura je :’,Prosek:5:2);

end.

Primer 3

• • Napišite program koji će izračunati prosek temperatura za proizvoljan broj dana

o Korisnik prvo mora uneti koliko dana želi.

o Uneti temperature za svaki dan.

o Izračunati i ispisati prosek temperatura.

o Ispisati samo one dane kada su temperature bile ispod proseka

Rešenje

program Temperature;
var
Dani: array[1..500] of Integer;

BrojDana,i:integer;

Prosek:Real;
begin

Prosek:=0;
write(‘Unesi broj dana:’);

readln(BrojDana);

for i:=1 to BrojDana do

begin

write(‘Unesi temperaturu za dan ‘,i,’ : ’);

readln(Dani[i]);

Prosek:=Prosek+Dani[i];

end;

Prosek:=Prosek/BrojDana;

Writeln(‘Temperatura je bila ispod proseka za dane broj:’);

for i:=1 to BrojDana do

if Dani[i]<Prosek then writeln(‘Dan:’,i);

end.

Primer 4 - Traženje maksimuma niza

· Napišite program koji će izračunati maksimalnu temperaturu za proizvoljan broj dana

Rešenje

program Temperature;
var
Dani: array[1..500] of Integer;

BrojDana,i,Max:integer;

begin
write(‘Unesi broj dana:’);

readln(BrojDana);

for i:=1 to BrojDana do

begin

write(‘Unesi temperaturu za dan ‘,i,’ : ’);

readln(Dani[i]);

end;

Max:=Dani[1];

for i:=1 to BrojDana do

if Dani[i]>Max then Max:=Dani[i];

Writeln(‘Maksimalna temperatura je bila :’,Max,’ stepeni);

end.

Zadatak 1

· Napišite program koji će ispisati koji su dani u prethodnom primeru imali maksimalnu temperaturu

Zadatak 2

· Napišite program koji će ispisati koliko dana je imalo temperaturu Tx (gde je Tmin<=Tx<=TMax a TMin i TMax su temperature koje se unose) i koji su to dani.

Primer 5 – O Deklaraciji niza

Type Dani: array [1..500] of integer;

Var a,b,c:Dani;

Na ovaj način smo deklarisali tri niza a,b i c.

Napomena: U ovom primeru Dani nisu niz već tip niza!!!

Ova naredba je ekvivalentna sa:

Var a,b,c: array [1..8] of integer;

Pitanje: Koja je moguća svrha deklarisanja niza preko Type?

Type mesec= (jan, feb, mar, apr, maj, jun, jul, avg, sep, okt, nov, dec);

Var prihod: array [mesec] of real;

nocenja: array [apr..okt] of integer;

Ovo su neki primeri deklaracije nizova nabrojivim tipovima.

Primer 6 – O korišćenju indeksa niza

· Napišite program koji će od niza Dani napraviti niz Nedelje koji će sadržati samo temperature svakog sedmog dana. Ispisati niz Nedelje.

program Temperature;
var
Dani: array[1..500] of Integer;

Nedelje: array[1..72] of Integer;

BrojDana,i,j:integer;

begin
write(‘Unesi broj dana:’);

readln(BrojDana);

for i:=1 to BrojDana do

begin

write(‘Unesi temperaturu za dan ‘,i,’ : ’);

readln(Dani[i]);

end;

j:=1;

for i:=1 to BrojDana do

if (i mod 7=0) then

begin

Nedelje[j]:=Dani[i];

j:=j+1;

end;

for i:=1 to j do

Writeln(‘Nedelja[‘,j,’]=’,Nedelja[j]);

end.

Primer 7 – Zamena vrednosti elemenata u nizu

· Napišite program koji će od niza Dani zameniti temperature svakog sedmog i šestog dana. Ispisati novodobijeni niz.

program Temperature;
var
Dani: array[1..500] of Integer;

BrojDana,i,Tpom:integer;

begin
write(‘Unesi broj dana:’);

readln(BrojDana);

for i:=1 to BrojDana do

begin

write(‘Unesi temperaturu za dan ‘,i,’ : ’);

readln(Dani[i]);

end;

for i:=1 to BrojDana do

if (i mod 7=0) then

begin

Tpom:=Dani[i];

Dani[i]:=Dani[i-1];

Dani[i-1]:=Tpom;

end;

for i:=1 to BrojDana do

Writeln(‘Dani[‘,i,’]=’,Dani[i]);

end.

Primer 8 – Generisanje niza

· Fibonnacijev niz je: 1,1,2,3,5,8,13,21,...

Svaki n-ti član niza izračunava se po formuli Fn=Fn-1 +Fn-2 tj. izračunava se kao suma prethodna dva člana. Prvi i drugi član niza jednaki su 1. Najjednostavniji način je stavljanje brojeva u niz.

Program Fibonnaci;

var f:array[1..20000] of integer;

i,n,j: integer;

begin

write('Unesi granicu: ');

readln(n);

f[1]:=1;

f[2]:=1;

i:=3;

while f[i-1]<=n do

begin

f[i]:=f[i-1]+f[i-2];

i:=i+1;

end;

for j:=1 to i-2 do

write(f[j]:6);

end.

Pitanje: Gde bi se mogao upotrebiti ovaj niz?

Sortiranje nizova

Problem sortiranja datog niza sastoji se u urdjenju elemenata u traženom poretku. Poredak može biti:

- rastući :                   x[1] < x[2] < x[3] < . . . < x[n]
- neopadajući:           x[1] <= x[2] <= x[3] <=. . . <= x[n]
- opadajući:               x[1] >x[2]> x[3]> . . . > x[n]
- nerastući                 x[1] => x[2]=>x[3] => . . . => x[n]

Postoji više metoda sortiranja i najbitnija razlika izmedju njih je u brzini. Takodje je i bitna „osetljivost“ algoritma na redosled ulaznih podataka. Pored ovoga pri izboru algoritma sortiranja treba imati u vidu i šta se sortira, tj. koliki prostor u memoriji zauzimaju pojedinačno članovi niza koji se sortira , jer bi onda trebalo izabrati algoritam koji će ih manje premeštati.

Na početku strane možete videti Java applet koji pokazuje animacije nekih od najpopularnijih metoda sortiranja.

program BubbleSortZamena;

type niz=array[1..100] of real;

var i,n:integer; a:niz;

procedure stampajniz(n:integer;var a:niz); //stamapa sve clanove niza

var k:integer;

begin

for k:=1 to n do write(a[k]:5:2,' ');

writeln;

end;

procedure bublesortzamena(n:integer;var a:niz);

var i,j:integer;

p:real;

begin

for i:=1 to n-1 do

begin

writeln;

write(i,'.prolazak kroz niz: ');

for j:=1 to n-i do

if a[j]>a[j+1] then

begin

P:=a[j];

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

a[j+1]:=p;

end;

stampajniz(n,a); //poziva se procedura za stampanje

end;

begin //glavni program

write('unesi broj clanova niza:');

readln(n);

writeln;

writeln('unesi clanove niza:');

writeln;

for i:=1 to n do

begin

write(i,'. clan:');

readln(a[i]);

end;

bublesortzamena(n,a);

writeln;

write('SORTIRANI NIZ JE: ');

stampajniz(n,a);

readln;

end.

Program BubbleSort;

type niz=array[1..100] of real;

var i,n:integer; a:niz;

procedure stampajniz(n:integer;var a:niz); //stamapa sve clanove niza

var k:integer;

begin

for k:=1 to n do write(a[k]:5:2,' ');

writeln;

end;

procedure bublesort(n:integer;var a:niz);

var i,j,granica:integer;

p:real;

sortirano:boolean;

begin

j:=1;

granica:=n-1;

repeat

sortirano:=true;

for i:=1 to granica do

begin

if a[i]>a[i+1] then

begin

P:=a[i];

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

a[i+1]:=p;

sortirano:=false;

end;

granica:=granica-1;

writeln;

write(j,'.prolazak kroz niz: ');

j:=j+1;

stampajniz(n,a); //poziva se procedura za stampanje

until sortirano;

end;

begin //glavni program

write('unesi broj clanova niza:');

readln(n);

writeln;

writeln('unesi clanove niza:');

writeln;

for i:=1 to n do

begin

write(i,'. clan:');

readln(a[i]);

end;

bublesort(n,a);

writeln;

write('SORTIRANI NIZ JE: ');

stampajniz(n,a);

readln;

end.

program SelekcijaSort;

type niz=array[1..100] of real;

var i,n:integer; a:niz;

procedure stampajniz(n:integer;var a:niz); //stamapa sve clanove niza

var k:integer;

begin

for k:=1 to n do write(a[k]:5:2,' ');

writeln;

end;

procedure selekcija(n:integer;var a:niz);

var i,j, min:integer;

p:real;

begin

for i:=1 to n-1 do begin

min:=i;

for j:=i+1 to n do

if a[j]<a[min] then

min:=j;

if min<>i then

begin

P:=a[min];

a[min]:=a[i];

a[i]:=p;

end;

writeln;

write(i,'.prolazak kroz niz: ');

stampajniz(n,a); //poziva se procedura za stampanje

end;

begin //glavni program

write('unesi broj clanova niza:');

readln(n);

writeln;

writeln('unesi clanove niza:');

writeln;

for i:=1 to n do

begin

write(i,'. clan:');

readln(a[i]);

end;

selekcija(n,a);

writeln;

write('SORTIRANI NIZ JE: ');

stampajniz(n,a);

readln;

end.

program UmetanjeSort;

type niz=array[1..100] of real;

var i,n:integer; a:niz;

procedure stampajniz(n:integer;var a:niz); //stamapa sve clanove niza

var k:integer;

begin

for k:=1 to n do write(a[k]:5:2,' ');

writeln;

end;

procedure umetanje(n:integer;var a:niz);

var i,j: integer;

p: real;

begin

for i:=2 to n do

begin

p:=a[i];

j:=i;

while a[j-1]>p do begin

a[j]:=a[j-1];

j:=j-1;

end;

a[j]:=p;

writeln;

write(i-1,'.prolazak kroz niz: ');

stampajniz(n,a); //poziva se procedura za stampanje

end;

begin //glavni program

write('unesi broj clanova niza:');

readln(n);

writeln;

writeln('unesi clanove niza:');

writeln;

for i:=1 to n do

begin

write(i,'. clan:');

readln(a[i]);

end;

umetanje(n,a);

writeln;

write('SORTIRANI NIZ JE: ');

stampajniz(n,a);

readln;

end.