Gyakorlati alapok
Gyorsrendezés
Figyelem! Ez a kód nehézsége miatt valójában magasabb szintű. Az ok, amely miatt mégis ide (is) került, hogy a Tömbműveletek nevű fejezetcsomag összefüggő és teljes logikai egységet alkosson. Az alábbi kódban már rekurzió, valamint a következő fejezetcsomag legjellegzetesebb programozás-technikai megoldása, a külön eljárás-függvény szerepel.
A gyorsrendezés nagyságrendekkel hatékonyabb az előző fejezetekben ismertetett megoldásoknál. Az alapelv a következő: a véletlenszámokkal feltöltött, rendezendő tömb folyamatosan egyre kisebb részekre van tagolva. A határ mindig az int valaszto, tőle balra a kisebb, tőle jobbra mindig a nála nagyobb elemek kerülnek. Az esetleges cserét a csere nevű külön eljárás végzi el. Ilyen módon a tömb egyre kisebb résztömbökre lesz osztva, míg végül megkapjuk a rendezett elemsorozatot.
A rendezés legérdekesebb programozás-technikai megoldása a rekurzió, amely során a gyorsRendezes nevű függvény önmagán belül önmagát hívja meg. Nézzük meg futtatható Java-kódos változatát:
import java.util.Random;
public class Main {
static void gyorsRendezes(int[] tomb, int bal, int jobb){
if(bal < jobb){
int also =
bal, felso = jobb + 1, valaszto = tomb[bal];
for( ; ; ){
while(++also < felso && tomb[also] < valaszto);
while(tomb[--felso] > valaszto);
if(also >= felso)
break;
csere(tomb, also, felso);
}
csere(tomb,
felso, bal);
gyorsRendezes(tomb, bal, felso-1);
gyorsRendezes(tomb, felso+1, jobb);
}
}
static void csere(int[] tomb, int i, int j){
int seged = tomb[i];
tomb[i] = tomb[j];
tomb[j] = seged;
}
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();
gyorsRendezes(tomb, 0,
tomb.length-1);
for(int i = 0; i < tomb.length; i++)
System.out.print(tomb[i] + " ");
System.out.println();
}
}
Végeredmény (például):
42 50 48 31 26 20 19 16 14 12
12 14 16 19 20 26 31 42 48 50
Pénzes László