5. fejezet - Rendezések

Adott n szám. Milyen módon lehet ezeket nagyság szerint növekvő sorrendbe rendezni? A lehetséges megoldásokat rendszerint az alábbi csoportok egyikébe lehet besorolni:

Beszúró rendezés: Egyesével tekinti a rendezendő számokat, és mindegyiket beszúrja a már rendezett számok közé, a megfelelő helyre. (Bridzsező módszer)

Cserélő rendezés: Ha két szám nem megfelelő sorrendben következik, akkor felcseréli őket. Ezt az eljárást ismétli addig, amíg további cserére már nincs szükség.

Kiválasztó rendezés: Először a legkisebb (legnagyobb) számot határozza meg, ezt a többitől elkülöníti, majd a következő legkisebb (legnagyobb) számot határozza meg, stb.

Leszámoló rendezés: Minden számot összehasonlítunk minden más számmal; egy adott szám helyét a nála kisebb számok száma határozza meg.

5.1. Beszúró rendezés

Az előbbi rövid leírásnak megfelelő pszeudókód a következő:

Procedure BESZÚRÓ(A) 
Input: Az A tömb 
Eredmény: Az A tömb elemei nagyság szerint rendezi 
1 for j = 1 to A.hossz-1 do 
2    kulcs = A[j] 
3    //A[j] beszúrása az A[0..j − 1] rendezett sorozatba 
4    i = j − 1 
5    while i ≥= 0 and A[i] ≥ kulcs do 
6       A[i + 1] = A[i] 
7       i-- 
8    endw 
9    A[i + 1] = kulcs 
10 endfor 

A programban az A[i] jelöli az A tömb i-dik elemét, és A.hossz adja meg az A tömb méretét.

5.1. példa - 4. Példa

Tartalmazza az A tömb az 5, 2, 4, 6, 1 és 3 számokat! A tömb tartalma a következőképpen változik az algoritmus végrehajtása során:

A táblázatban az arany színű számok már rendezve vannak. A beszuro.htm fájl tartalmazza azt a programot, amely egy véletlen módon generált számsorozatra végrehajtja a beszúró rendezés és ciklusról ciklusra kiírja a tömb tartalmát.


Az algoritmus elemzése. Jelöljük a c1 c2, . . . , c9 konstansokkal, hogy mennyi idő (hány elemi lépés) kell az első, második, . . . , kilencedik sor végrehajtásához, és jelölje tj azt, hogy a while ciklus hányszor hajtódik végre a j érték esetén. (A nyolcadik és a tizedik sor csak a ciklus végét jelzi, ezek éppúgy nem végrehajtható utasítások, mint a harmadik sorban található megjegyzés.) Ha n jelöli az A tömb hosszát, akkor a program futása

ideig tart. Ha a sorozat növekvően rendezett, akkor a while ciklus nem hajtódik végre, azaz a tj értéke minden esetben 1. Egyszerűsítés és átrendezés után az előbbi képlet

alakra egyszerűsödik. Ebből leolvasható, hogy a futásidő a hossz lineáris függvénye. Ha a sorozat csökkenően rendezett, akkor a while ciklust minden egyes megelőző elemre végre kell hajtani, azaz tj = j. Ekkor a futási idő

azaz a hossz négyzetes függvénye. Ez az eset a legrosszabb eset, így a beszúró rendezés bonyolultsága O(n2).