Poznámky k triedeniu z DÚ č. 1

Bubble sort

Vstup: pole A dlžky n
for i := 1 to n - 1
	for j := 1 to n - i - 1
		if A[j] < A[j + 1]
			swap(A[j], A[j+1]) # prehoď hodnoty A[j] a A[j+1]
return A # zostupne zotriedené pole A

Vizualizácia fungovania

Na zamyslenie:

• Aká je presná časová zložitosť tejto implementácie?
• Aká je asymptotická zložitosť v najlepšom a najhoršom prípade?

Insertion sort

Vstup: pole A dlžky n
for i := 0 to n - 2
	j := i + 1
	tmp = A[j]
	while j > 0 and tmp > a[j-1]
		if A[j] < A[j + 1]
			A[j] = A[j-1])
			j = j - 1
		a[j] = tmp
return A # zostupne zotriedené pole A

Vizualizácia fungovania

Na zamyslenie

• Aká je časová zložitošť tohto algoritmu v najhoršom prípade ? Na akom vstupe nastáva?
• Aká je časová zložitosť v najlepšom prípade? Na akom vstupne nastáva?

Counting sort

Vstup: pole A dĺžky n
       max = najväčšia hodnota v poli A
Pomocné premenné:
       count - pole dĺžky max, na začiatku samé 0
for i in A:
	count[i] =  1

j := 1
for i := 1 to max:
	if count[i] > 0
	   A[j] := i
	   j = j + 1
return A

Na zamyslenie:

• Aká je asymptotická časová zložitosť tohto algoritmu?

Úlohy

Pseudokód

Logické operátory

Swap

Navrhnite jednoduchý algoritmus prehodenia hodnôt dvoch celočíslených premenných A a B bez akejkoľvek pomocnej premennej.

Správne uzátvorkovanie

Na vstup dostanete postupnosť zátvoriek S napr. S=”(()())()”. Navrhnite algoritmus, ktorý skontroluje správnosť uzátvorkovania, tj. vŕati True ak je uzátvorkovanie správne a False inak.

Bin2Dec a Dec2Bin

Navrhnite algoritmus prevodu binárneho čísla na číslo desiatkové a späť.

Pascal

Jednoduchý program:

Program priklad;
Var       
	Num1, Num2, Sum : Integer;
	a, b, c, d: Double;

Begin
	Write('Input number 1:');
	Readln(Num1);
	Writeln('Input number 2:');
	Readln(Num2);
	Sum := Num1 + Num2; {scitanie}
	Writeln(Sum);
	Readln;
End.  

Domáce úlohy

Vašu domácu úlohu tentokrát nájdete v CodEx-e. Ide o úlohy PPPPP 0.2 Hello World 2 a Suma.

Niekoľko z vás som v CodEx-e nenašiel, zariadte si účet a napíšte mi.

Termín odovzdania: 26. 10. 2016 (23:59)