Gyakorlati alapok
Bugyborékrendezések
Az algoritmust működtető egyik fontos kódrészletről már tanulhattunk a Hogyan cseréljünk meg kezeinkben 2 teli poharat? (adatcserebere) című fejezetben. Javaslatom, hogy a kód tanulmányozása előtt ezt a fejezetet nézzük át.
A buborékrendezés során -hasonlóan a pezsgőpohárban látható, folyamatosan felfelé áramló szénsavbuborékokhoz-, a mindenkori legnagyobb tömbelem szállingózik fel a tömb legtetejére. Ehhez mindig a szomszédos elemeket hasonlítjuk össze és csere esetén a nagyobb elem kerül feljebb. A rendezés tehát mindig egyre szűkebb tömbelem-tartományt érint.
Ám éppen aprólékossága miatt a buborékrendezés nem hatékony rendezési mód, mert műveletigénye a tömbméret négyzetével arányos.
Nézzük meg futtatható Java-kódos változatát:
import java.util.Random;
public class Main {
public static void main(String[] args) {
Random rnd = new Random();
int [] tomb = new int[10];
for(int i = 0; i < tomb.length; i++){
tomb[i] = rnd.nextInt(50) + 1;
System.out.print(tomb[i] + " ");
}
System.out.println();
for(int i = tomb.length-1; i > 0; i--)
for(int j = 0; j < i; j++)
if(tomb[j] > tomb[j+1]){
int tarolo = tomb[j];
tomb[j] = tomb[j+1];
tomb[j+1] = tarolo;
}
for(int i = 0; i < tomb.length; i++)
System.out.print(tomb[i] + " ");
}
}
Végeredmény (például):
35 7 11 13 37 40 19 39 29 14
7 11 13 14 19 29 35 37 39 40
Forrás - Source: wiki.prog.hu
Az algoritmus hatékonysága javítható, ha bevezetünk egy flag-et (Az állapotjelzők (flag) című fejezet), amely azt figyeli, hogy a belső ciklusban volt-e csere, hiszen csakis ebben az esetben érdemes a külső ciklusnak tovább futnia.
import java.util.Random;
public class Main {
public static void main(String[] args) {
Random rnd = new Random();
int [] tomb = new int[10];
boolean csere = true;
for(int i = 0; i < tomb.length; i++){
tomb[i] =
rnd.nextInt(50) + 1;
System.out.print(tomb[i] + " ");
}
System.out.println();
for(int i = tomb.length-1; i > 0 &&
csere; i--){
csere = false;
for(int j =
0; j < i; j++){
if(tomb[j] > tomb[j+1]){
int tarolo = tomb[j];
tomb[j] = tomb[j+1];
tomb[j+1] = tarolo;
csere = true;
}
}
}
for(int i = 0; i < tomb.length; i++)
System.out.print(tomb[i] + " ");
}
}
Végeredmény (például):
35 7 11 13 37 40 19 39 29 14
7 11 13 14 19 29 35 37 39 40
Forrás - Source: wiki.prog.hu
Az algoritmus hatékonysága egy másik módszerrel is javítható: egy segédváltozó bevezetésével (int aktualisPozicio) megjegyezzük az utolsó cserélt elem tömbpozícióját és a következő ciklus már csak eddig fog tartani.
import java.util.Random;
public class Main {
public static void main(String[] args) {
Random rnd = new Random();
int [] tomb = new int[10];
int i, aktualisPozicio;
for(i = 0; i < tomb.length; i++){
tomb[i] =
rnd.nextInt(50) + 1;
System.out.print(tomb[i] + " ");
}
System.out.println();
i = tomb.length - 1;
while(i >= 1){
aktualisPozicio = 0;
for(int j =
0; j < i; j++){
if(tomb[j] > tomb[j+1]){
int tarolo = tomb[j];
tomb[j] = tomb[j+1];
tomb[j+1] = tarolo;
aktualisPozicio = j;
}
}
i =
aktualisPozicio;
}
for(i = 0; i < tomb.length; i++)
System.out.print(tomb[i] + " ");
}
}
Végeredmény (például):
8 20 45 28 1 28 38 42 2 9
1 2 8 9 20 28 28 38 42 45
Pénzes László