Kihagyás

2. gyakorlat

Stabil rendezés fogalma

Ha adott \(a\), \(a': a \ne a'\), de A rendezési szempont szerint \(a \ngtr a'\) és \(a \nless a'\), a rendezés után \(a_{i}\) és \(a'_{i+1}\) helye relatíve ugyanaz marad-e

Insertion Sort

Insertion - Megoldás menete

  • Az első elem rendezve van
  • A következő elemet addig az elemig hasonítgatja, amíg nem nagyobb nála

Insertion - Aspektusai

  • Helyben rendez
  • Space Complexity: \(\varTheta(1)\)
  • Time complexity: \(\varTheta(?)\)

Naív és sima közti különbség

A naív nem jó ZH-n :kekw:

A sima idk, send help :peko:

Merge Sort

Merge - Megoldás menete

  • Felezzük a listát (logikailag)
    • Majd a felezett listákat
    • Amíg 1 hosszú nem lesz
      • Ami triviálisan rendezett
    • Layer-enként összefűzi őket, egészen az utolsóig
  • Létrejön egy Z segédtömb, ami maximum \(n/2\) hosszú
    • A tömb második fele érintetlen
    • Az első tömb i és i+1-edik elemeinek helyét dönti el Z[j] és Z[n/2 + j] edik elemei közt
    • Ha a végére értünk, Z és \(\mathscr{T}\) egy rendezett \(\mathscr{T}\)-t eredményez

Merge - Aspektusai

  • Rekurzív
  • Space Complexity: \(\varTheta(n/2) \sim \varTheta(n)\)
  • Time Complexity: \(\varTheta(n\log{n})\)
  • Stabil

Verem - Stack

LIFO - Last in, First out

Struccy Tips and Tricks

Struktogram osztály objektumához tartozó metódus <Osztálynév>::<Metódusnév>(<Paraméterek>) Szintaxissal lehet megadni

P.L.: Stack::push(t:T)

Negáció - \(\lnot\)

MaciFicaM