Ki az aki ismeri és érti a pszeudokódokat?

@#16, tánc:

Jé, ilyesmiket én is csináltam:

https://www.youtube.com/watch?v=eQP6-qmkckg

https://www.youtube.com/watch?v=eFxUKPFb3Q0

https://www.youtube.com/watch?v=2ndFcg2bOVk

Bocs a generikus kód miatt. Csak azért írtam így, mert le akartam tesztelni a különböző méretű értéktípusok közötti teljesítménykülönbséget.

Jól értelmezed. A lényeges eltérés a kettő között, hogy az általam linkelt algoritmus először kikeresi a minIndexet és csak a legvégén cserél. Azaz max array.Length-1 cserét végez. Ezeket számlálom a swap változóban. Képzelj el egy olyan szituációt ahol a T mondjuk egy 50 bájtos értéktípus és van belőle egymillió. Ekkor nem mindegy, hogy hány cserét végzel.

Elméletben ki lehetne matekolni, hogy átlagosan melyik menyi cserét végez de én inkább közelítem Monte Carlo módszerrel.

Véletlen számokból generáltam 1 000 hosszú listákat és ezeket rendeztem mindhárom rendezéssel.

Ezer ilyen lista rendezése során a cserék átlaga:

Unknown sort swaps: 216169

Bubble sort swaps: 249564

Selection sort swaps: 995

Na most ha ezek 50 bájtos értékek és minden cserénél ezeket 3x mozgatod minden egyes csere esetén (temp változót használsz stb). Ekkor az általam linkelt algoritus 50 * 3 * 995 = 149 250 bájt = 150 megabájt memóriaforgalmat generál. A kérdező átlal linkelt algoritmus(unknown) viszont 50 * 3 * 216 169 = 32 425 350 bájt = 32,4 GB!!! memóriaforgalom.

És ez csak egy ezer soros lista. Mivan, ha egmiliárd rekordot akarsz rendezni. A memóriaforgalom is exp. növekszik.

A fenti számítást ugye beárnyékolja a cache és cpu regiszterek létezése illetve hogy erre a problémára a quick sort lenne az alkalmas.

Egyébként a selection sort is nagyon hatékony ha csak néhány elem nincs a helyén.

váááá elszámoltam ennyire meredek különbség nincs csak a fölös cseréket spórolja meg

a másodiknál még hozzá kell adni a minimumkeresésnél minden összehasonlításnál 2 olvasás történik amiből van 5 273

50 * 3 * 995 + 50 * 2 * 5 273 = 676 550 bájt 676 megabájt

Utólag aztán rájöttem, hogy igen, egy minimumkeresés volt benne és a végén csak azt cserélte.

Mondjuk én annyiból nem bánom, hogy beraktad ide azt a generikust, hogy így le tudtam tesztelni magam, hogy mennyire értem meg.

2-3 hónapja még konkrétan sírtam volna a látványától, most viszont ezek szerint kb 15 perc alatt nagyjából megértettem. Még az IComparable interface-nek kell utánanéznem, pont az említett 2-3 hónapja találkoztam vele utoljára és jegeltem szegényt.

Azért szeintem egy kezdőnek nehéz téma a generikusok.