Algoritmusok vektorokkal – keresések function TELJES_KERES1(A, érték) - - teljes keresés while ciklussal 1. i ← 1 2. while i ≤ méret(A) és A[i] 6= érték do i←i+1
3.
4. end while 5. if
i > méret(A) then KIVÉTEL "nincs ilyen értékű elem"
6. 7. else
return i
8.
9. end if end function function TELJES_KERES2(A, érték) - - teljes keresés for ciklussal 1. for
i ← 1 to méret(A) do
2.
if
A[i] = érték then return i
3.
end if
4.
5. end for 6. KIVÉTEL "nincs ilyen értékű elem" end function function TELJES_KERES_REK(A, érték) - - teljes keresés rekurzívan 1. if
méret(A) = 0 then
2.
KIVÉTEL "nincs ilyen értékű elem"
3. else if 4.
A[1] = érték then
return 1
5. else 6.
return TELJES_KERES_REK(A[2..méret(A)], érték) + 1
7. end if end function
1
Algoritmusok vektorokkal – keresések function LINEÁRIS_KERES1(A, érték) - - lineáris keresés while ciklussal 1. i ← 1 2. while i ≤ méret(A) és A[i] < érték do i←i+1
3.
4. end while 5. if
i > méret(A) vagy A[i] > érték then KIVÉTEL "nincs ilyen értékű elem"
6. 7. else
return i
8.
9. end if end function function LINEÁRIS_KERES2(A, érték) - - lineáris keresés for ciklussal 1. for
i ← 1 to méret(A) do
2.
if
A[i] = érték then return i
3.
else if
4.
A[i] > érték then
KIVÉTEL "nincs ilyen értékű elem"
5.
end if
6.
7. end for 8. KIVÉTEL "nincs ilyen értékű elem" end function function LINEÁRIS_KERES_REK(A, érték) - - lineáris keresés rekurzívan 1. if
méret(A) = 0 vagy A[1] > érték then
2.
KIVÉTEL "nincs ilyen értékű elem"
3. else if 4.
A[1] = érték then
return 1
5. else 6.
return LINEÁRIS_KERES_REK(A[2..méret(A)], érték) + 1
7. end if end function
2
Algoritmusok vektorokkal – keresések function BINÁRIS_KERES1(A, érték) - - bináris keresés iteratívan 1. alsó ← 1 2. felső ← méret(A) 3. while alsó ≤ felső do 4.
középső ← [(alsó + felső) / 2]
5.
if
A[középső] = érték then return középső
6.
else if
7.
A[középső] > érték then
felső ← középső – 1
8. else
9.
alsó ← középső + 1
10.
end if
11.
12. end while 13. KIVÉTEL "nincs ilyen értékű elem" end function function BINÁRIS_KERES2(A, érték) - - bináris keresés rekurzívan 1. if
méret(A) = 0 then KIVÉTEL "nincs ilyen értékű elem"
2.
3. end if 4. középső ← [(1 + méret(A)) / 2] 5. if
A[középső] = érték then
6.
return középső
7. else if 8.
A[középső] > érték then
return BINÁRIS_KERES2(A[1..középső – 1], érték)
9. else 10.
return középső + BINÁRIS_KERES2(A[középső + 1..méret(A)], érték)
11. end if end function
3
Algoritmusok vektorokkal – keresések function BINÁRIS_KERES3(A, érték, alsó, felső) - - bináris keresés rekurzívan, részvektorok nélkül 1. if
alsó > felső then KIVÉTEL "nincs ilyen értékű elem"
2.
3. end if 4. középső ← [(alsó + felső) / 2] 5. if
A[középső] = érték then
6.
return középső
7. else if 8.
A[középső] > érték then
return BINÁRIS_KERES3(A, érték, alsó, középső – 1)
9. else 10.
return BINÁRIS_KERES3(A, érték, középső + 1, felső)
11. end if end function
4
Algoritmusok vektorokkal – rendezések procedure MIN_KIVÁL_RENDEZ(A) - - minimumkiválasztásos rendezés 1. for
i ← 1 to méret(A) – 1 do
2.
min ← i
3.
for
j ← i + 1 to méret(A) do if
4.
A[j] < A[min] then min ← j
5.
end if
6. 7.
end for
8.
A[i] és A[min] felcserélése
9. end for end procedure procedure MAX_KIVÁL_RENDEZ(A) - - maximumkiválasztásos rendezés 1. i ← méret(A) 2. while i ≥ 2 do 3.
max ← 1
4.
for
j ← 2 to i do if
5.
A[j] > A[max] then max ← j
6.
end if
7. 8.
end for
9.
A[i] és A[max] felcserélése
10.
i←i–1
11. end while end procedure procedure BESZÚRÁSOS_RENDEZ(A) - - beszúrásos rendezés 1. for
i ← 2 to méret(A) do
2.
kulcs ← A[i]
3.
j←i–1
4.
while j ≥ 1 és A[j] > kulcs do
5.
A[j + 1] ← A[j]
6.
j←j–1
7.
end while
8.
A[j + 1] ← kulcs
9. end for end procedure
5
Algoritmusok vektorokkal – rendezések procedure BUBORÉKOS_RENDEZ1(A) - - buborékos rendezés 1. i ← méret(A) – 1 2. while i ≥ 1 do 3.
for
j ← 1 to i do if
4.
A[j + 1] < A[j] then A[j] és A[j + 1] felcserélése
5.
end if
6. 7.
end for
8.
i←i–1
9. end while end procedure procedure BUBORÉKOS_RENDEZ2(A) - - javított buborékos rendezés 1. i ← méret(A) – 1 2. volt_csere ← IGAZ 3. while i ≥ 1 és volt_csere do 4.
volt_csere ← HAMIS
5.
for
6.
j ← 1 to i do if
A[j + 1] < A[j] then
7.
A[j] és A[j + 1] felcserélése
8.
volt_csere ← IGAZ
9.
end if
10.
end for
11.
i←i–1
12. end while end procedure
6
Algoritmusok vektorokkal – rendezések procedure BUBORÉKOS_RENDEZ3(A) - - tovább javított buborékos rendezés 1. i ← méret(A) – 1 2. while i ≥ 1 do 3.
utolsó_csere ← 1
4.
for
j ← 1 to i do if
5.
A[j + 1] < A[j] then
6.
A[j] és A[j + 1] felcserélése
7.
utolsó_csere ← j end if
8. 9. 10.
end for i ← utolsó_csere – 1
11. end while end procedure procedure SHELL_RENDEZ1(A) - - shell rendezés beszúrásos rendezéssel 1. LK ← {100,30,8,3,1} 2. for
k ← 1 to méret(LK) do
3.
lépésköz ← LK[k]
4.
for
eltolás ← 1 to lépésköz do
5.
i ← lépésköz + eltolás
6.
while i ≤ méret(A) do
7.
kulcs ← A[i]
8.
j ← i – lépésköz
9.
while j ≥ 1 és A[j] > kulcs do
10.
A[j + lépésköz] ← A[j]
11.
j ← j – lépésköz
12.
end while
13.
A[j + lépésköz] ← kulcs
14.
i ← i + lépésköz end while
15. 16.
end for
17. end for end procedure
7
Algoritmusok vektorokkal – rendezések procedure SHELL_RENDEZ2(A) - - egyszerűsített shell rendezés beszúrásos rendezéssel, - - és általánosított lépésköz választással 1. k ← 1 2. repeat 3.
lépésköz ← 3 * lépésköz + 1
4. until lépésköz ≥ méret(A) 5. while lépésköz > 1 do 6.
lépésköz ← (lépésköz – 1) / 3
7.
for
i ← lépésköz + 1 to méret(A) do
8.
kulcs ← A[i]
9.
j ← i – lépésköz
10.
while j ≥ 1 és A[j] > kulcs do
11.
A[j + lépésköz] ← A[j]
12.
j ← j – lépésköz
13.
end while
14.
A[j + lépésköz] ← kulcs
15.
end for
16. end while end procedure
8
Algoritmusok vektorokkal – rendezések procedure GYORS_RENDEZ1(A, alsó, felső) - - gyorsrendezés, 1. változat 1. if
alsó < felső then
2.
kulcs ← A[alsó]
3.
i ← alsó
4.
j ← felső + 1
5.
while i < j do
6.
repeat i←i+1
7. 8.
until i ≥ j vagy A[i] ≥ kulcs
9.
repeat
10.
j←j–1
11.
until A[j] ≤ kulcs
12.
if
i < j then A[i] és A[j] felcserélése
13. 14.
end if
15.
end while
16.
A[alsó] és A[j] felcserélése
17.
GYORS_RENDEZ1(A, alsó, j – 1)
18.
GYORS_RENDEZ1(A, j + 1, felső)
19. end if end procedure procedure GYORS_RENDEZ2(A, alsó, felső) - - gyorsrendezés, 2. változat 1. if
alsó < felső then
2.
határ ← FELOSZT(A, alsó, felső)
3.
GYORS_RENDEZ2(A, alsó, határ – 1)
4.
GYORS_RENDEZ2(A, határ + 1, felső)
5. end if end procedure
9
Algoritmusok vektorokkal – rendezések function FELOSZT(A, alsó, felső) 1. kulcs ← A[felső] 2. i ← alsó – 1 3. for
j ← alsó to felső – 1 do
4.
if
A[j] ≤ kulcs then
5.
i←i+1
6.
A[i] és A[j] felcserélése
7.
end if
8. end for 9. A[i + 1] és A[felső] felcserélése 10. return i + 1 end function procedure KUPAC_RENDEZ(A) - - Kupacrendezés 1. i ← [méret(K)/2] 2. while i > 0 do 3.
SÜLLYESZT(K, i, méret(K))
4.
i←i–1
5. end while 6. i ← méret(K) 7. while i > 1 do 8.
K[1] és K[i] felcserélése
9.
i←i–1
10.
SÜLLYESZT(K, 1, i)
11. end while end procedure
10
Algoritmusok vektorokkal – rendezések procedure SÜLLYESZT(K, honnan, vége) - - A bináris (maximum) kupac tulajdonságai teljesülnek - - A K vektor honnan-nál nagyobb indexeire. - - Az algoritmus kiterjeszti ezeket a honnan indexre is. 1. x ← K[honnan] 2. gyermek ← honnan + honnan 3. while gyermek ≤ vége 4.
if
gyermek < vége és K[gyermek + 1] > K[gyermek] then gyermek ← gyermek + 1
5. 6.
end if
7.
if
K[gyermek] > x then
8.
K[honnan] ← K[gyermek]
9.
honnan ← gyermek gyermek ← honnan + honnan
10. 11.
else gyermek ← vége + 1
12. 13.
end if
14. end while 15. K[honnan] ← x end procedure procedure SÜLLYESZT_REK(K, honnan, vége) - - A bináris (maximum) kupac tulajdonságai teljesülnek - - A K vektor honnan-nál nagyobb indexeire. - - A rekurzív algoritmus kiterjeszti ezeket a honnan indexre is. 1. gyermek ← honnan + honnan 2. if 3.
gyermek < vége és K[gyermek + 1] > K[gyermek] then gyermek ← gyermek + 1
4. end if 5. if
gyermek ≤ vége és K[gyermek] > K[honnan] then
6.
K[gyermek] és K[honnan] felcserélése
7.
SÜLLYESZT(K, gyermek, vége)
8. end if end procedure
11
Algoritmusok vektorokkal – rendezések procedure ÖSSZEFÉSÜLVE_RENDEZ(A) - - egy vektor összefésülésen alapuló rendezése 1. rendezett ← 1 2. méret(B) ← méret(A) 3. while rendezett < méret(A) do 4.
ÖSSZEFÉSÜL_1(A, B, rendezett)
5.
ÖSSZEFÉSÜL_1(B, A, rendezett)
6. end while end procedure
12
Algoritmusok vektorokkal – rendezések procedure ÖSSZEFÉSÜL_1(A, B, rendezett) - - egy vektor összefésülésen alapuló rendezésének egy fázisa 1. k ← 1 2. repeat 3.
i←k
4.
j ← a ← k + rendezett
5.
b ← a + rendezett
6.
if
a > méret(A) then a ← méret(A) + 1
7. 8.
end if
9.
if
10.
b > méret(A) then b ← méret(A) + 1
11.
end if
12.
while i < a és j < b do
13.
if
A[i] > A[j] then
14.
B[k] ← A[j]
15.
j←j+1
16.
else
17.
B[k] ← A[i]
18.
i←i+1
19.
end if
20.
k←k+1
21.
end while
22.
while i < a do
23.
B[k] ← A[i]
24.
i←i+1
25.
k←k+1
26.
end while
27.
while j < b do
28.
B[k] ← A[j]
29.
j←j+1
30.
k←k+1
31.
end while
32. until k > méret(A) 33. rendezett ← rendezett + rendezett end procedure
13
— Algoritmusok vektorokkal – Dinamikus vektorok elemi műveletei function ÖSSZEFÉSÜL(A, B) - - két rendezett vektor összefésülése dinamikus vektor esetén 1. méret(C) ← méret(A) + méret(B) 2. i ← j ← k ← 1 3. while i ≤ méret(A) és j ≤ méret(B) do 4.
if
A[i] < B[j] then
5.
C[k] ← A[i]
6.
i←i+1
7.
else
8.
C[k] ← B[j]
9.
j←j+1
10.
end if
11.
k←k+1
12. end while 13. while i ≤ méret(A) do 14.
C[k] ← A[i]
15.
i←i+1
16.
k←k+1
17. end while 18. while j ≤ méret(B) do 19.
C[k] ← B[j]
20.
j←j+1
21.
k←k+1
22. end while 23. return C end function - - Algoritmusok vektorokkal – Dinamikus vektorok elemi műveletei procedure BESZÚR(V, index, érték) - - új elem beszúrása dinamikus vektor adott indexű eleme elé 1. if 2.
index < 1 vagy index > méret(V) + 1 then KIVÉTEL "hibás index"
3. end if 4. i ← méret(V) ← méret(V) + 1 5. while i > index do 6.
V[i] ← V[i – 1]
7.
i←i–1
8. end while 9. V[i] ← érték end procedure
14
— Algoritmusok vektorokkal – Dinamikus vektorok elemi műveletei procedure TÖRÖL(V, index) - - adott indexű elem törlése dinamikus vektorból 1. if 2.
index < 1 vagy index > méret(V) then KIVÉTEL "hibás index"
3. end if 4. for
i ← index to méret(V) – 1 do
5.
V[i] ← V[i + 1]
6. end for 7. méret(V) ← méret(V) – 1 end procedure
15
