Algoritmusok kezdőknek – 4. rész

 

Egy sorozathoz egy sorozat hozzárendelése:

 

1. Maximum kiválasztásos rendezés:

 

A tömb rendezése a legnagyobb elem segítségével.

Az utolsó elem a legnagyobb, a legnagyobb elem helyére kerül az utolsó elem. Az utolsó előtti elem lesz a 2. legnagyobb, a 2. legnagyobb helyére kerül az utolsó előtti elem stb.

 

CIKLUS I:=N-től 2-ig (-1-esével)

  MAX:=I

  CIKLUS J:=I-1-től 1-ig (-1-esével)

    HA A[J]>A[MAX] AKKOR

    MAX:=J

  CVÉGE

  C:=A[I]

  A[I]:=A[MAX]

  A[MAX]:=C

CVÉGE

 

2. Buborékrendezés I.:

 

Mindig szomszédos elemeket vizsgál.

Lassú, mert ahol már rendezve van, ott is ellenőrzi.

 

CIKLUS I:=N-től 1-ig (-1-esével)

  CIKLUS J:=1-től I-ig

    Ha A[J]>A[J+1] AKKOR

      C:=A[J]

      A[J]:=A[J+1]

      A[J+1]:=C

    HAVÉGE

  CVÉGE

CVÉGE

 

3. Buborékrendezés II.:

 

Mindig szomszédos elemeket vizsgál.

Ha az adott belső ciklusban nem volt csere, akkor a főciklust, azaz az algoritmust befejezi.

 

 

 

I:=N-1

VEGE:=Hamis

CIKLUS amíg I>=1 (vagyis I>0) AND NOT VEGE

  VEGE:=Igaz

  CIKLUS J:=1-től I-ig

    HA A[J]>A[J+1] AKKOR

      C:=A[J]

      A[J]:= A[J+1]

      A[J+1]:=C

      VEGE:=Hamis

    HAVÉGE

  CVÉGE

  I:=I-1

CVÉGE

 

4. Buborékrendezés III.:

 

Mindig szomszédos elemeket vizsgál.

Az utolsó cseréig vizsgál, ahol már nem volt csere, ott nem vizsgál.

 

I:=N-1

CIKLUS amíg I>0 (vagyis az UTOLSOCSERE>0)

  UTOLSOCSERE:=0

  CIKLUS J:=1-től I-ig

    HA A[J]>A[J+1] AKKOR

      C:=A[J]

      A[J]:=A[J+1]

      A[J+1]:=C

      UTOLSOCSERE:=J

    HAVÉGE

  CVÉGE

  I:=UTOLSOCSERE

CVÉGE

 

5. Póker rendezés:

 

A számokat közvetlenül egymás mellé helyezi – ahogyan az ember a kártyáit rendezi.

 

CIKLUS I:=2-től N-ig

  J:=I-1

  X:=A[I]

  CIKLUS amíg (J>=1) AND (X<A[J])

    A[J+1]:=A[J]

    J:=J-1

  CVÉGE

  A[J+1]:=X

CVÉGE

 

6. Listás-beillesztéses rendezés:

 

Feltétele, hogy MU tömb 0-kat tartalmazzon. Csökkenő sorrendben rendez (lehet fordítva is).

MU 0-tól N-ig tartalmaz számokat, a Tomb tömb indexeit (elemeinek sorszámát). A Tomb tömb rendezettsége nem változik, a MU-ban változik a Tomb tömb indexeinek sorrendje. Az ME az aktuálisat, az MK a következő tömbelemet mutatja. Az új elem mindig az ME és az MK közé szúródik be. Keresi, hogy hol van az első új elem, amelyik a kettő között áll.

Előnye: A tömbnek csak az indexeit rendezi, így nagyobb adatbázisoknál nem kell a rekordokat cserélni, ami nagyon lassítja a folyamatot.

 

Tomb[1..N] – a rendezettsége nem változik

MU[0..N] – segédtömb, a Tomb tömb indexeit tartalmazza

 

MU[0]:=1

CIKLUS I:=2-től N-ig

  MK:=MU[0]

  ME:=0

  A:=Tomb[I]

  CIKLUS amíg (MK>0) AND (A<Tomb[MK])

    ME:=MK

    MK:=MU[ME]

  CVÉGE

  MU[ME]:=I

  MU[I]:=MK

CVÉGE

CIKLUS I:=1-től N-ig

  KI: Tomb[MU[I-1]]

CVÉGE

 

Szűcs Tamás - szucs_t@freestart.hu