GYKBD kérdése:
Cserés rendezés gyorsabb, mint a minimum kiválasztásos rendezés?
Figyelt kérdés
Kaptam egy feladatot, ami szerint van olyan számsor (monjduk 10 9 8 7 6 5 4 3 2 1), ahol a cserés rendezés kevesebb lépés alatt oldja meg a sorba rendezést, mint a minimum kiválasztásos rendezés, de én egyszerűen nem tudok rájönni, hogy milyen számsor lehet ez. A segítséget előre is köszönöm.2014. jan. 12. 13:58
11/17 anonim válasza:
Rendezett sorban persze hogy nem cserél egyik sem. Az összehasonlítások számát számold meg.
12/17 A kérdező kommentje:
De ez a problémám, hogy ezt kellene levezetni, de nem igazán sikerül. A kérdés alapból úgy szólt, hogy a Cserék száma legyen kevesebb, ami ugye teljesen lehetetlen. Csak azt nem értem, hogy hogy lesz kevesebb lépésben az összehasonlítás. Tudtommal mind a két rendezés végig megy a függvényen nem?
2014. jan. 13. 22:40
13/17 A kérdező kommentje:
Elnézést, a tömbön
2014. jan. 13. 22:40
14/17 anonim válasza:
Igen, végigmennek, de másképpen. Mondom, számold meg az összehasonlításokat. :) Másképp nem fogod megérteni.
15/17 A kérdező kommentje:
Ha az sikerülne, nem kellene itt kérdeznem :D. Amúgy az mennyire hihető, hogy egy rendezett sornál (1 2 3 4 5 6 7 8 9 10)-nél azért cserél kevesebbet a cserés rendezés (0-át), mert csak akkor kell cserélnie, ha T[i] > T[j], és ugye ebben az esetben nem kell cserélni, mert a Ha függyvény hamis. A minimum kiválasztásos pedig azért cserél egyet, mert a T[i] mindenképpen cserél legalább egyszer a T[min]-el, akkor is, ha az önmaga?
2014. jan. 13. 23:25
16/17 A kérdező kommentje:
És mindkettő úgy megy végig, hogy Ciklus i=1-től N-1-ig, Ciklus j=1+1-től N-ig. Én nem igazán látom a különbséget.
2014. jan. 13. 23:28
17/17 anonim válasza:
Jaaa, jó. Megtévesztő ez a név, hogy cserés rendezés, mert a legtöbb rendező algoritmus cserélgetéssel teremt sorrendet. Rákerestem most így, hogy "cserés rendezés", valóban nagyon hasonló a kettő és a ciklusfeltételek tényleg egyeznek. Akkor viszont az lesz, amit írtál, a minimum kiválasztásos mindenképpen végez 1 cserét.
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!