Ø Hasonlítások Ø Mozgatások 7/29 2021. 0: 44 száma: N– 1 … száma: 2 (N– 1) … Horváth-Papné-Szlávi-Zsakó: Programozási alapismeretek 11. előadás Számlálva szétosztó rendezés Algoritmus: Számlálva szétosztó rendezés: Db[i]: hány darab van i-ből? Megszámolás tétel Első[i]: hol az i. elsője? Rekurzív kiszámítás Változó i: Egész Db, Első: Tömb[1.. Max. N: TH] DB[1.. Rendezési algoritmusok. M]: =0 Ciklus i=1 -től N-ig Db[X[i]]: =Db[X[i]]+1 Ciklus vége Első[1]: =1 Ciklus i=1 -től M-1 -ig Első[i+1]: =Első[i]+Db[i] Ciklus vége … 8/29 2021. 0: 44 Horváth-Papné-Szlávi-Zsakó: Programozási alapismeretek 11. előadás Számláló rendezés. Algoritmus: Az egyszerű cserés rendezés elvén működő számlálás. Másolás tétel Számláló rendezés: Változó i, j: Egész Db: Tömb[1.. M]: =0 Ciklus i=1 -től N-1 -ig Ciklus j=i+1 -től N-ig Ha X[i]>X[j] akkor Db[i]: =Db[i]+1 különben Db[j]: =Db[j]+1 Ciklus vége Ciklus i=1 -től N-ig Y[Db[i]+1]: =X[i]: = Ciklus vége Eljárás vége. Ø Hasonlítások 9/29 2021. +N– 1= Ø Mozgatások száma: N Ø Additív műveletek száma: ~hasonlítások Horváth-Papné-Szlávi-Zsakó: Programozási alapismeretek 11. előadás
Animáció Az animáció az egyszerű cserés rendezés elvét mutatja be. Véletlenszerűen generált számsort rendez, közben mutatja, hogy az algoritmus melyik sorában jár. A rendezést a Rendezés gombbal lehet elindítani és megállítani. Így lehetőség van lépésenként vagy folyamatosan végrehajtani az algoritmust. Az Újra gomb félbeszakítja az éppen zajló rendezést és új számsorozatot generál. Programozási alapismeretek 11. előadás - PDF Free Download. A program mutatja a hasonlítások és a cserék számát, így össze lehet hasonlítani a különböző rendezések hatékonyságát. Használat Rendezés: elindítja vagy megállítja az animációt, aszerint hogy éppen áll-e vagy nem Újra: megállítja az animációt, ha éppen fut, és új számsort generál. Videó
(Megoldás itt. ) F0036e: Írd ki a táblát az elért pontok szerinti fordított sorrendben! (Megoldás itt. ) F0036f: Számold ki a gólkülönbséget és rendezz aszerint – írd ki így a táblát! (Megoldás itt. ) Legutóbb szétválogattunk. Legközelebb metszetet képezünk.
(Részletesebb magyarázat a kupac adatszerkezet leírásánál. ) bal ( k): bal:= 2 * k Eljárás vége jobb ( k): jobb:= 2 * k + 1 Eljárás vége epit ( T): Ciklus i:= ( N / 2) - től 1 - ig ( -1) - esével sullyeszt ( N, i, T) Ciklus vége Eljárás vége sullyeszt ( p, r, T): b:= bal ( r); j:= jobb ( r) Ha b <= p és T [ b] > T [ r] akkor max:= b különben max:= r Elágazás vége Ha j <= p és T [ j] > T [ max] akkor max:= j Elágazás vége Ha max! = r akkor Csere ( max, r) sullyeszt ( p, max, a); Elágazás vége Eljárás vége rendez ( T): db:= N epit ( T) Ciklus i:= db - től 1 - ig ( -1) - esével Csere ( 1, i) db --; sullyeszt ( db, 1, T); Ciklus vége Eljárás vége Gyorsrendezés A középső indexű elem szerint kettéválogatjuk a tömböt. Alulra kerülnek a középsőnél kisebbek, felülre pedig a nagyobbak. Ezután az alsó és a felső részre rekurzívan meghívjuk a rendező eljárást. Egyszerű cserés rendezés. A rendezést a QuickSort(T, 1, N) hívással indíthatjuk el. A rekurzív módszer akkor hatékony, ha elég sokszor nagyjából két egyenlő részre bontjuk az éppen rendezendő szakaszt.
Adott egy adathalmazunk, mondjuk egy tömb. A benne tárolt elemeket sorba szeretnénk rendezni. Ez esetben a legegyszerűbb algoritmus, amit választhatunk, az a cserés rendezés. Ennek a lényege az, hogy a tömb elemeit egymással összehasonlítjuk. Ha a tömb soron következő eleme nagyobb az utána következőnél, akkor megcseréljük őket. Ahhoz, hogy a tömb rendezett állapotba kerüljön, N elem esetén N*N alkalommal kell lefuttatni a cseréket, ami nem a legjobb, mivel az elemszám növekedésével négyzetesen nő a futási idő. Egy lehetséges implementáció: using System; namespace PeldaAlgoritmusCseresrendez { class Program static void TombKiir(int[] tomb) foreach (var elem in tomb) ("{0}, ", elem);} Console. WriteLine();} public static int[] CseresRendez(int[] bemenet) int[] tomb = new int[]; (bemenet, tomb, ); for (int i = 0; i <; i++) for (int j = 0; j <; j++) if (tomb[i] < tomb[j]) var tmp = tomb[i]; tomb[i] = tomb[j]; tomb[j] = tmp;}}} return tomb;} static void Main(string[] args) var tomb = new int[] { 9, 6, 0, 0, 1, 2, 2, 2, 3, 1, 5, 4, 8, 2, 8, 6}; Console.
Rendezési algoritmusok Első feladatként készítsünk programot, amely két pozitív egész számot kivon egymásból úgy, hogy a nagyobból vonja ki a kisebbet! Eredményül adja meg a különbséget a program! Be kell olvasnunk 2 számot a programunk első utasításaival. Ezután meg kell vizsgálnunk, hogy melyik a nagyobb. A vizsgálattól függően kell a kivonást megcsinálni. Nézzük meg az algoritmusát a programnak: Beolvas(a) beolvas(b) Ha a>=b akkor Legyen eredmeny=a-b különben Legyen eredmeny=b-a Elágazás vége Kiír(eredmény) Algoritmus vége Az eredmeny változóban lesz a különbség tárolva. Az értékét attól függően kapja, hogy melyik szám volt a nagyobb. Nézzük meg hogyan tudnánk egy tömbbe beolvasott 2 számot rendezni úgy, hogy a kisebb szám legyen a tömbben a nagyobb szám előtt. Első lépésben beolvassuk a tömbbe a két számot. Ezután kell megvizsgálni, hogy melyik szám a nagyobb. Abban az esetben, ha már eleve a kisebb szám volt a tömb első tagja, akkora tömböt változatlanul hagyjuk. Ha viszont a második tömbelem a kisebb szám, akkor fel kell a 2 elemet cserélni.