Programozási tételek

Sorozat(ok)hoz több sorozat hozzárendelése

Únió

Általános feladat: Rendelkezésünkre áll egy N és egy M elemű halmaz az A() és a B()

vektorban ábrázolva. Készítsük el a két halmaz egyesítését a C() vektorba!

Ciklus I=1-től N-ig
	C(I):=A(I)
Ciklus vége
CN:=N
Ciklus J=1-től M-ig
	I:=1
	Ciklus amíg I<=N és A(I)<>B(J)
		I:=I+1
	Ciklus vége
	Ha I>N akkor CN:=CN+1  C(CN):=B(J)
Ciklus vége

Metszet

Általános feladat: Rendelkezésünkre áll egy N és egy M elemű halmaz az A() és a B()

vektorban ábrázolva. Készítsük el a két halmaz metszetét a C() vektorba!

CN:=0
Ciklus I=1-től N-ig
	J:=1
	Ciklus amíg J<=M és A(I)<>B(J)
		J:=J+1
	Ciklus vége
	Ha J<=M akkor CN:=CN+1  C(CN):=A(I)
Ciklus vége

Összefuttatás

Általános feladat: Két rendezett sorozat uniója úgy, hogy a rendezettség megmaradjon.

I:=1  J:=1  K:=0
Ciklus amíg I<=N és J<=M
	K:=K+1
	Elágazás
		A(I) < B(J) esetén  C(K):=A(I)  I:=I+1
		A(I) = B(J) esetén  C(K):=A(I)  I:=I+1  J:=J+1
		A(I) > B(J) esetén  C(K):=B(J)  J:=J+1
	Elágazás vége
Ciklus vége
Ciklus amíg I<=N
	K:=K+1  C(K):=A(I)  I:=I+1
Ciklus vége
Ciklus amíg J<=M
	K:=K+1  C(K):=B(J)  J:=J+1
Ciklus vége

Szétválogatás

Feladat: egy sorozat elemeit választjuk külön két különböző sorozatba aszerint, hogy egy adott T tulajdonsággal rendelkeznek-e az elemek vagy nem.

J:=0  K:=0
Ciklus I=1-től N-ig
	Ha A(I) T tulajdonságú
		akkor J:=J+1  B(J):=A(I)
		egyébként K:=K+1  C(K):=A(I)
Ciklus vége

Ha a szétválogatáshoz nem használhatunk fel újabb vektorokat, akkor a megoldás lényegesen bonyolultabb.

Rendezések

Rendezés közvetlen kiválasztással

Lényege: Első menetben az A(1)-et összehasonlítjuk az összes elemmel és ha kisebbet találunk nála, akkor felcseréljük.

Így az első menet végére a legkisebb elem lesz az első helyen. Ezután ezt ismételjük az A(2)-es elemmel, stb.

Az N-1. menet után rendezett lesz a sorozat.

Ciklus I=1-től N-1-ig
	Ciklus J=I+1-től N-ig
		Ha A(J) < A(I) akkor C:=A(J)  A(J):=A(I)  A(I):=C
	Ciklus vége
Ciklus vége

Rendezés minimum-kiválasztással

Lényege: A felesleges cserék kiküszöbölése érdekében két segédváltozót vezetünk be (legkisebb elem értékének és indexének).

Ciklus I=1-től N-1-ig
	INDEX:=I  ÉRTÉK:=A(I)
	Ciklus J=I+1-től N-ig
		Ha A(J)<ÉRTÉK akkor ÉRTÉK:=A(J)  INDEX:=J
	Ciklus vége
	A(INDEX):=A(I)  A(I):=ÉRTÉK
Ciklus vége

Buborékos rendezés

Lényege: Hasonlítsuk össze a vektor első és második elemét, s ha az első nagyobb, cseréljük meg őket. Ezt követően hasonlítsuk össze a vektor második és harmadik elemét, s ha a második nagyobb, cseréljük meg őket, és így tovább. Látható, hogy ekkor a vektor legnagyobb eleme biztosan a helyére kerül, még akkor is, ha ő volt az első.

Sajnos ez a többi elemre nem feltétlenül teljesül, tehát ahhoz, hogy a második legnagyobb elem a helyére kerüljön, ismét el kell indulnunk a vektor elejéről. Az első elemet össze kell hasonlítani a másodikkal, a másodikat a harmadikkal, stb., azonban most már elég elmenni az utolsó előtti elemig, hiszen az utolsó a helyén van. A következő körben már a harmadik legnagyobb elemet tesszük a helyére, és így tovább. A külső ciklust tehát annyiszor kell lefuttatnunk, ahány eleme van a vektorunknak.

Ciklus I=1-től N-ig
	Ciklus J=1-től N-I-ig
		Ha A(J)>A(J+1) akkor Cs:=A(J)  A(J):=A(J+1)  A(J+1):=Cs
	Ciklus vége
Ciklus vége

Egyszerű beillesztéses rendezés

Lényege: Mintha kártyáinkat egyesével felvéve sorba raknánk. (N-1 menet)

Ciklus J=2-től N-ig
	I:=J-1  ÉRTÉK:=A(J)
	Ciklus amíg I > 0 és ÉRTÉK < A(I)
		A(I+1):=A(I)  I:=I-1
	Ciklus vége
	A(I+1):=ÉRTÉK
Ciklus vége