Gyakorlati alapok
2 tömb összefuttatása
Az összefuttatás hasonló az unióhoz, tőle csupán abban különbözik, hogy maguk az alaptömbök is rendezettek, ezért az eredménytömbnek is rendezettnek kell lennie. A közös részek csak egyszer fordulhatnak elő. Ha nincs közös rész, azt az összefuttatási módot összefésülésnek nevezzük.
Az alábbi példakódban az átláthatóság kedvéért 2 db fix int értékekkel feltöltött tömbből indulunk ki:
int[] tomb1 = new int[] {1, 3, 5, 7, 9, 11, 13};
int[] tomb2 = new int[] {2, 4, 6, 8, 9, 10, 13};
Minden elem egyszeresen a tombOsszefuttatas-be kerül, ezért a mérete:
int[] tombOsszefuttatas = new int[tomb1.length+tomb2.length];
Az összefuttatás mondatszerű leírása (pszeudo-kód) a progalap.elte.hu oldalon van publikálva...
Összefuttatás(N,X,M,Y,Db,Z):
I:=1; J:=1; Db:=0
Ciklus amíg I≤N és J≤M
Db:=Db+1
Elágazás
X[I]<Y[J]
esetén Z[Db]:= X[I]; I:=I+1
X[I]=Y[J]
esetén Z[Db]:= X[I]; I:=I+1; J:=J+1
X[I]>Y[J]
esetén Z[Db]:=Y[J]; J:=J+1
Elágazás vége
Ciklus vége
Ciklus amíg I≤N
Db:=Db+1; Z[Db]:=X[I]; I:=I+1
Ciklus vége
Ciklus amíg J≤M
Db:=Db+1; Z[Db]:=Y[J]; J:=J+1
Ciklus vége
Eljárás vége.
...az alábbi futtatható Java-kód ennek közvetlen implementációja:
public class Main {
public static void main(String[] args) {
int[] tomb1 = new int[] {1, 3, 5, 7, 9, 11, 13};
int[] tomb2 = new int[] {2, 4, 6, 8, 9, 10, 13};
int[] tombOsszefuttatas = new int[tomb1.length+tomb2.length];
int i = 0;
int j = 0;
int szamlalo = -1;
while(i < tomb1.length && j < tomb2.length) {
szamlalo++;
if(tomb1[i] < tomb2[j]) {
tombOsszefuttatas[szamlalo] = tomb1[i++];
}else if(tomb1[i] == tomb2[j]) {
tombOsszefuttatas[szamlalo] = tomb1[i];
i++;
j++;
}else if(tomb1[i] > tomb2[j]) {
tombOsszefuttatas[szamlalo] = tomb2[j++];
}
}
while(i < tomb1.length)
tombOsszefuttatas[++szamlalo] =
tomb1[i++];
while(j < tomb2.length)
tombOsszefuttatas[++szamlalo] =
tomb2[j++];
for(i = 0; i < szamlalo+1; i++){
System.out.print(tombOsszefuttatas[i]
+ " ");
}
}
}
Végeredmény:
1 2 3 4 5 6 7 8 9 10 11 13
Az összefésülés is elvégezhető ugyanezzel az algoritmussal. Ennek illusztrálására csak a bemeneti értékeket változtassuk meg olyasformán, hogy páros és páratlan tömbelemeket fésülünk össze:
int[] tomb1 = new int[] {1, 3, 5, 7, 9, 11, 13};
int[] tomb2 = new int[] {2, 4, 6, 8, 10, 12, 14};
public class Main {
public static void main(String[] args) {
int[] tomb1 = new int[] {1, 3, 5, 7,
9, 11, 13};
int[] tomb2 = new int[] {2, 4, 6, 8, 10, 12, 14};
int[] tombOsszefuttatas = new int[tomb1.length+tomb2.length];
int i = 0;
int j = 0;
int szamlalo = -1;
while(i < tomb1.length && j < tomb2.length) {
szamlalo++;
if(tomb1[i] < tomb2[j]) {
tombOsszefuttatas[szamlalo] = tomb1[i++];
}else if(tomb1[i] == tomb2[j]) {
tombOsszefuttatas[szamlalo] = tomb1[i];
i++;
j++;
}else if(tomb1[i] > tomb2[j]) {
tombOsszefuttatas[szamlalo] = tomb2[j++];
}
}
while(i < tomb1.length)
tombOsszefuttatas[++szamlalo] =
tomb1[i++];
while(j < tomb2.length)
tombOsszefuttatas[++szamlalo] =
tomb2[j++];
for(i = 0; i < szamlalo+1; i++){
System.out.print(tombOsszefuttatas[i]
+ " ");
}
}
}
Végeredmény:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
Ha meg kívánjuk őrizni a redundáns elemtartalmat (tehát azonos elemek többször is előfordulhatnak), akkor ezt a sort...
tombOsszefuttatas[++szamlalo] = tomb2[j];
...kell a megfelelő helyre a kódba illesztenünk:
public class Main {
public static void main(String[] args) {
int[] tomb1 = new int[] {1, 3, 5, 7, 9, 11, 13};
int[] tomb2 = new int[] {2, 4, 6, 8, 9, 10, 13};
int[] tombOsszefuttatas = new int[tomb1.length+tomb2.length];
int i = 0;
int j = 0;
int szamlalo = -1;
while(i < tomb1.length && j < tomb2.length) {
szamlalo++;
if(tomb1[i] < tomb2[j]) {
tombOsszefuttatas[szamlalo] = tomb1[i++];
}else if(tomb1[i] == tomb2[j]) {
tombOsszefuttatas[szamlalo] = tomb1[i];
tombOsszefuttatas[++szamlalo] = tomb2[j];
i++;
j++;
}else if(tomb1[i] > tomb2[j]) {
tombOsszefuttatas[szamlalo] = tomb2[j++];
}
}
while(i < tomb1.length)
tombOsszefuttatas[++szamlalo] =
tomb1[i++];
while(j < tomb2.length)
tombOsszefuttatas[++szamlalo] =
tomb2[j++];
for(i = 0; i < szamlalo+1; i++){
System.out.print(tombOsszefuttatas[i]
+ " ");
}
}
}
Végeredmény:
1 2 3 4 5 6 7 8 9 9 10 11 13 13
Pénzes László