Algoritmusok
bulletAlgoritmus megadása
bulletAlapalgoritmusok

Keresések

Szekvenciális keresés
Gyorsított szekvenciális keresés
Felezéses (bináris, logaritmikus) keresés

Rendezések

Közvetlenbeszúrásos rendezés
Buborék rendezés
Gyors rendezés

 

Szekvenciális keresés:

adott:     K1,...,Kn     sorozat
              K                   kersett érték

  1. i=1
  2. ha Ki=K akkor sikeresen vége
  3. i=i+1
  4. ha i<=N     akkor ugrás a 2. pontra
                       különmben sikertelenül vége

Hátránya: Egy cikluson belől két összehasonlítás van ezért lassú.

Gyorsított szekvenciális keresés

  1. i=1 és Kn+1 =K
  2. ha Ki=K akkor ugrás a 4. pontra
  3. i=i+1 és 2. pontra ugrás
  4. ha i<=N      akkor sikeresen vége
                        különben sikertelenül vége

Előnye: Ezzel a megoldással csak egy összehasonlítás van a cikluson belől.

Felezéses (bináris, logaritmikus) keresés

Rendezett sorokon végezhető algoritmus, mely sokkal gyorsabb az előzőeknél. Bináris esetben mindig az aktuális sorrész felénél végez összehasonlítást. Logaritmikus esetben, logaritmikus skála szerint osztja ketté az aktuális sorrészt, ez bizonyos esetekben gyorsabb.

algoritmus

Közvetlen beszúrásos rendezés

  1. CIKLUS I=1-TŐL N-1 - IG

    CIKLUS J=I+1 - TŐL N-IG

    HA A(J)<A(I) AKKOR

    A:=A(J)

    A(J):=A(I)

    A(I):=A

    HA VÉGE

    CIKLUS VÉGE

    CIKLUS VÉGE

Buborék rendezés

Elv: A szomszédos elemeket cseréljük, ha szükséges.
Előny: Könnyen implementálható algoritmushoz jutunk.

  1. i=2,3,...,N -re hajtsuk végra a 2. pontot
  2. j=N,N-1,...,i -re hajtsuk végre a 3. pontot
  3. ha Aj-1 > Aj akkor ezek felcserélése
  4. Vége

Az algoritmus gyorsítható, ha egy flag-et vezetünk be, mely figyeli, hogy a cikluson belől volt-e csere, amenyiben nem volt, vége az algoritmusnak, a sor többi része már rendezett.

 

Gyors rendezés

A leggyorsabb rendezési algoritmus

  1. ha a rendező sorozat hossza <=1 akkor vége
  2. Kiválasztun egy X sorozatelemet
  3. Helyezzünk X elé az X nél kisebb, X mögé az X nél nagyobb elemeket
  4. Gyosrendezés az X-né kisebb elemekre
  5. Gyorsrendezés az X-nél nagyobb elemekre
  6. Vége

hátrány: Ez egy rekurzív algoritmus, az újraindítások idő és tárigényesek ezért kis elemszám esetén erősen leromlik az algoritmus hatásfoka. Ez a hiányosság javíható, ha kombinált algoritmust használunk, nagy elemszám esetén gyorsrendezés, majd amikor az elemszám lecsökken áttérünk valamely más klasszikus algoritmusra.