A feladat Egy N elemű T[] tömb elemeit kell nagyság szerint növekvő sorrendbe rakni. Az elmélet Két elem összehasonlításakor három választ kaphatunk (<, =, >), tehát $k$ kérdéssel legfeljebb $3^k$ lehetőség között tudunk választani. Az $\, N$ elemnek $\, N! $ -féle sorrendje van, ezek közül kell az egyetlen jót meghatároznunk, tehát szükségszerűen $N! \le 3^k$. Kettes alapú logaritmust véve innen $\log N! /\log 3 \le k$. Finomabb matematikai eszközökkel megmutatható, hogy $\log N! \approx c\cdot N\log N$, ennél gyorsabb rendező algoritmus nem készíthető. (Ez természetesen csak azokra a rendezésekre vonatkozik, amelyek a tömbelemek összehasonlításával és cserélgetésével működnek. ) A legegyszerűbb rendező algoritmusok általában $N^2$ -tel arányos lépésszámmal dolgoznak, a kupacrendezés és a gyorsrendezés elméletileg optimális. Óvatosan kell azonban bánnunk az elméleti becslésekkel, a nagyságrend szempontjából elhanyagolt konstansokon néha sok múlik. "Kis" tömbök esetén az egyszerű cserés rendezések is tökéletesen megfelelnek.
Programozási Tételek - Egyszerű Cserés Rendezés:: EduBase Login Sign Up Features For Business Contact Programozási Tételek - Egyszerű Cserés Rendezés 34 You need to register to view this content. A videó megtekintéséhez jelentkezz be vagy regisztrálj gyorsan és ingyen egy új fiókot. A regisztrációval számos további extra funkcióhoz férhetsz hozzá! Volume Speed Pause Error report 3 thanks back seen report EduBase - Bázis a tanuláshoz. | Köszönet a videóért a TheHUNtutorials youtube csatornának! A C nyelv az egyik legnagyobb múltú programozási nyelvek közé tartozik, mégis napjaink egyik legkorszerűbb nyelve. Gyakorlatilag mindegyik operációs rendszerhez készítettek C fordító programot, így a legnépszerűbb programozási nyelvek egyike. Log in to write a comment! Be the first to comment!
Sokan vizsgálták azt a kérdést, hogy milyen távolságsorozat adja a legjobb futási időt. A most bemutatott változatban a D. E. Knuth által javasolt h[] = {1, 4, 13, 40, 121} távolságsorozattal dolgozunk. Tetszőleges távolságsorozat helyes rendezést biztosít, ha a legkisebb lépés értéke 1. Ciklus s:= 5 - től 1 - ig ( -1) - esével lep:= h [ s] Ciklus j:= ( lep +1) - től N - ig i:= j - lep; x:= T [ j] Ciklus amíg i > 0 és T [ i] > x T [ i + lep]:= T [ i] i = i - lep Ciklus vége T [ i + lep]:= x Ciklus vége Ciklus vége Kupac rendezés A tömböt kupaccá alakítjuk. A kupac tetejére kerül a legnagyobb elem, ezt a tömb végén lévő elemmel felcseréljük, csökkentjük a kupac méretét és helyreállítjuk a kupac-tulajdonságot. A buborékrendezéshez hasonlóan itt is minden menetben az aktuális szakasz legnagyobb eleme kerül helyére. Egy menet azonban sokkal gyorsabb, mert a kupac-tulajdonság helyreállítása $\log N$ -nel arányos lépésben megy, míg a buborék rendezésnél egy-egy menet $N$ -nel arányos lépést végez.
Az animáció lejátszása során figyeld meg, hogy az algoritmus milyen sorrendben hasonlítja össze az elemeket, majd az egyes összehasonlítások után mikor cseréli ki őket.
Egy menetben a legkisebb és legnagyobb elemet tesszük helyre, így egyszerre mozognak a kis elemek a tömb eleje, a nagyok pedig a tömb vége felé.
A rendezssel kszen vagyunk.