Algoritmus Rendezések - összehasonlító elemzés

Algoritmus Rendezések

összehasonlító elemzés

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 5.000 elemű.

A tömb 10.000 elemű.

A rendezésekbe lépés( összehasonlítás ) és csere számlálót helyeztem.

2.500 Db-ú tömb esetén.

5.000 Db-ú tömb esetén.

10.000 Db-ú tömb esetén.

A táblázatokat áttanulmányozva láthatjuk a rendezések közti különbséget. 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ám*Elemszá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