Programozás | Programozás-elmélet » Lukácsi Balázs - Rendezési algoritmusok összehasonlító elemzése

Lukácsi Balázs V.b Rendezési algoritmusok összehasonlító elemzése A feladat elvégzése érdekében négy rendezési fajtát hasonlítottam össze névszerint : - Minimum - Csökkenő - Buborék - Beszúrásos rendezést. Mind a négy esetben azonos tömböt rendeztem. A teszteket az iskolában végeztem Am5*86-P75-S 133 MHz 8Mb-os Hálózatra kötött gépen .A Tesztelés során a rendezéseket különböző szempontok alapján mérlegeltem .Többek közt elemszámváltoztatás ,lépés(vizsgálat) és csere számláló beiktatása ; a rendezendő tömb véletlenszerü feltöltése során 30.000 nagyságrendű számokat deklaráltam. Az algoritmusokhoz az adatokat a Rendez.Txt-böl szedtem ki Az értékek Századmásodpercben értendők. Tömb 2.500 elemű Tömb fajta / rend. fajta Csökkenő Minimum 11 17 17 Véletlen Rendezett Ford. rendezett Beszúrásos Buborék 66 0 71 44 16 44 16 0 38 Tömb 5.000 elemű Tömb fajta / rend. fajta Csökkenő Minimum 61 66 72

Véletlen Rendezett Ford. rendezett Beszúrásos Buborék 269 0 308 153 55 164 71 0 148 A tömb 10.000 elemű Tömb fajta / rend. fajta Véletlen Rendezett Ford. rendezett Csökkenő Minimum 247 247 269 Buborék 637 242 670 Beszúrásos 1104 297 0 0 1230 532 A rendezésekbe lépés( összehasonlítás ) és csere számlálót helyeztem. 2.500 Db-ú tömb esetén Véletlen Csere Idő Lépés Minimum Csökkenő Buborék Beszúrásos Rendezett Fordítva rendezett Lépés Csere Idő Lépés Csere Idő 3123750 1250 22 3123750 0 27 3123750 1250 22 3123750 3123750 55 3123750 0 17 3123750 3123750 55 3123750 3123750 82 0 0 0 3123750 3123750 83 2499 2499 39 2499 0 0 2499 2499 38 5.000 Db-ú tömb esetén Véletlen Lépés Minimum Csökkenő Buborék Beszúrásos Csere 12497500 Rendezett Idő Fordítva rendezett Csere Idő Lépés Lépés Csere Idő 2500 98 12497500 0 99 12497500 2500 104 12497500 12497500 225

12497500 0 88 12497500 12497500 225 12497500 12497500 357 0 0 0 12497500 12497500 319 148 4999 0 0 4999 4999 4999 4999 148 10.000 Db-ú tömb esetén Véletlen Lépés Minimum Csökkenő Buborék Beszúráso s Csere Rendezett Idő Fordítva rendezett Csere Idő Lépés Lépés Csere Idő 49995000 5000 406 49995000 0 401 49995000 5000 406 49995000 49995000 896 49995000 0 352 49995000 895 4999500 49990000 1290 0 0 0 49995000 9999 9999 588 9999 0 0 9999 4999500 0 4999000 0 9999 A táblázatokat áttanulmányozva láthatjuk a rendezések közti különbséget. 1291 588 Rendezési algotitmusok : - Minimum rendezés T [1.Elemszám] : TombTip Min : TombTip Ciklus I:= 1 - Től Elemszám-1 - ig Min:= i Ciklus J:=I+1 -től Elemszámig Ha T[J] < T[Min] Akkor Min:= I Csere(T[i],T[Min]) Cv Cv Deklarálunk egy Tombtip tipusu tömböt ami Elemszám elemböl áll.Feltesszük ,hogy ez a tömb felvan töltve. Indítunk egy ciklust 1

- töl elemszám -1 -ig A ciklusszámlálló legyen I . A Min változó legyen I Majd elindítunk egy másik ciklust I+1 - től Elemszámig aminek a ciklusszámlállója J . Ha T[j] -dik eleme kisebb mint T[Min] akkor a Min legyen I Ha nem akkor Cseréljük a T[i] -t T[Min]-el. Ha a belsőciklusunk végéreért akkor külső ciklus növeli i értékét addig amig nem teljesül a feltétel . Összehasonlítások száma Tárigény : elemszám+1 Összehasonlítások száma : Elemszám *(Elemszám-1)/2 Cserék : Legjobb esetben : 0 Legrosszabb : 3*Elemszám(Elemszám-1)+ElemszámElemszám/4 - Csökkenő rendezés T [1.Elemszám] : TombTip Min : TombTip Ciklus I =1 -től Elemszám-1-ig Ciklus J:=I+1-től Elemszámig Ha T[i] > T[j] akkor Csere (T[i],T[j]) Cv Cv Deklarálunk egy Tombtip tipusu tömböt ami Elemszám elemböl áll.Van egy Min változóm ami Tömbtipusú.Ciklust indítunk 1-től elemszám -1 -ig I ciklusszámlallóval Ezen a cikluson belül elindítunk egy másik

ciklust I+1 -től Elemszámig J ciklusszámlálóval . A cikluson belül egy feltételt vizsgállok Ha T[i]-dik eleme Kisebb mint T[ j ]-dik eleme akkor .Cseréljük T[i]-dik elemét T[ j ]-dik elemével. Tárigény : elemszám+1 Összehasonlítások száma : Elemszám *(Elemszám-1)/2 Cserék : Legjobb esetben : 0 Legrosszabb : 3*Elemszám(Elemszám-1)/2 - Buborék rendezés (Marci módra) T [1.Elemszám] : TombTip Min : TombTip Van még = Igaz I= 1 Feltétel amig (I<Elemszám) és (Van még) Van még = hamis Ciklus J:= 1-től Elemszám-1-ig Ha T[j ] > T[J+1] Csere (T[J],T[J+1]) Van még = Igaz Cv I := I+1 Cv Deklarálunk egy Tombtip tipusu tömböt ami Elemszám elemböl áll és egy Vanmég logikai véltozót amt igazra állítunk.I változónknak 1-et adunk értékül és elindítunk egy ciklust amig I Kisebb mint Elemszám és Vanmég löogikai változóm Hamis -ra állítjuk.Ezen a cikluson belül elindítunk egy feltételt mejnek ciklusszámlálója J és 1-től

Elemszám-1-ig mejtódik végre.Most már megszabhatjuk a feltételt Ha T[ j ] nagyobb mint T[J+1] Akkor T[J]-t kicseréljük T[J+1]-el és vanmég logikai változót igazra állítjuk ezzel elérve azt ,hogy a feltételünk csak addig hajtótjonvégre mig T[J]-dik eleme nem rendeződik .Ezután növeljük I-t 1-el és ujra kezdődik a feltétel addig míg rendezett nem lesz a tömb. Tárigény : elemszám+1 Összehasonlítások száma : Elemszám *(Elemszám-1)/2 Cserék : Legjobb esetben : 0 Legrosszabb : 3*Elemszám(Elemszám-1)/2 - Beszúrásos rendezés T [1.Elemszám] : TombTip Min : TombTip Ciklus I:= 2 - től Elemszámig Ha T[i] < T[i-1] akkor Ment:=T[i] J:=I Ciklus J:=J-1 T[j+1]:=T[j] Addig amíg T[j-1] <= Ment Cv T[j]:=Ment Fv Cv Deklarálunk egy Tombtip tipusu tömböt ami Elemszám elemböl áll és egy Min változó ami TombTip tipusú.Elindítunk egy ellenörzést T második elemétöl a végéig I ciklusszámlálóval. Ha T [i]-dik eleme kisabb mint T[i-1] -dik

eleme akkor ezt az értéket elmentjük egy Ment nevű változóba és J változó értékének átadjuk az I értékét. Elindítunk egy ciklust ami hátultesztelő és addig hajtódik végra amíg T[j-1]dik eleme kisebb egyenlő Ment -el Ebben a ciklusban J értékét csökkentjük 1-el és T[J+1]-dik elemének értékét átadjuk T[J]-dik elemének.Miután végrehajtottuk a cserét ki és teljesül a feltétel ki is léphetünk a ciklusból :T[J] értékének átajuk Ment értékét.Ezzel elérve azt,hogy rendezett tömböt kapunk Tárigény : elemszám+1 Összehasonlítások száma : Cserék : N-1 Legjobb esetben : 0 Legrosszabb : 3*Elemszám(Elemszám-1)/2