Hol a hiba a programban? C nyelvről lenne szó.
A program célja egy tömb elemeit rendezni. Kétféle rendezést ismerek, a buborék-és gyorsrendezést, úgy tudom, hogy van más is, de puszta kíváncsiságból gondoltam, írok egy saját algoritmust. Ez a következő elven működik: A tömbben megkeresi a legkisebb ill. legnagyobb elemet, ezeket a legelső ill. legutolsó helyre viszi, majd megismétli, ám ezúttal már nem dolgozik a két szélső elemmel. Harmadszor már a széltől számított 2-2 elem nem játszik stb. Ezt elvégzi feleannyiszor, mint ahány elemű a tömb, és így elméletileg minden elem a helyére kerül. Ha páratlan elemszámú tömbről van szó, akkor az elemszám felét lefele kerekíti, és elméletileg így is rendezett kéne legyen. Megjegyzem, hogy mérjem, milyen hatékony a megoldás, beépítettem egy időmérőt is.
A probléma a következő: A program a legnagyobb elemet nem viszi hátra, és a legkisebb elem értékét nem kicseréli a legelső helyen levővel, hanem csak beírja az értékét az első helyre, így elvesztődik az az érték, amit ott tároltam. A kicserélő függvényt külön ellenőriztem, jól működik. Különös módon, az utolsó helyre sokszor bekerül elemnek a 2293616, egy nem kigenerált szám, ami állandó.
Itt a kód, nem a legszebb, de olvasható, és nem tudom, mi okozhatja a problémát.
Ami a szépségét illeti, ezen tervezek javítani, ám először szeretném működőképessé tenni. A válaszokat köszönöm előre is.
válasza:"felcserel(&min, &t[0+k])"
Itt a min változó címét adod át, ami nem a tömbben van, persze, hogy össze-vissza cserélget. A min vagy legyen az index, és akkor &t[min], vagy legyen pointer, és akkor fentebb min = &t[j]; és a felcserélnél csak simán átadod.
Ugyanez a maxra is.
Azt most hírtelen nem látom, honnan jöhet a memóriaszemét, szóval lehet más probléma is van.
válasza:Ami elsőre szemet szúrt:
Minden kör elején "nullázni" kéne a min és a max értékét (=beállítani az AKTUÁLIS rész első elemére). Ezt csak a legelején, a ciklus előtt teszed meg a 0 indexű elemmel. Így szerintem végig az marad a min és a max...
iostream ill. #2: Köszönöm a válaszokat, az említett problémát sikerült kiküszöbölni, ám valamiért a rendezés még mindig nem teljes, eleinte nagyon jól megy, sőt, van, hogy végigfut gond nélkül, máskor viszont megbolondul, és összevissza dolgozik. A kódon úgy változtattam, hogy ha talált új maximumot/minimumot, akkor az elem indexét eltárolja, és később felcseréli az indexnek megfelelő elemet a legkisebbel. A fura, hogy a minimumokkal nicnsen semmi baj, viszont a maximumnál van, hogy felcserél valamiket amiket nem kéne, továbbá, megpróbáltam kiíratni a max és min értékeket, és a max időnként ismét felveszi ugyanezt a "memóriaszemét" értéket. Először arra gondoltam, hogy a kelleténél eggyel több lépésszámot adok egy for ciklusnak, és ezért olyan memóriarészlettel dolgozik, ami nem az övé, de ilyenkor a Win megállítja a program futását, úgy tudom. Íme az új kódrészlet, csak a rendezést másolom be, mert csak ott változtattam + a két új változó bejelentése.
válasza: válasza:Ahogy ezt meg is teszed:
"for (j=(0+k);j<=(ARR-k);j++)"
j=0-ra j ARR-ig megy, ami már nagyobb, mint az utolsó index.
válasza:Ez megint nem jó szerintem.
Az előző elképzelés jó volt: kezdetben a min és a max az 1. elem, és a 2. elemtől keresel újat.
Ugye nem véletlenül hívják maximum KIVÁLASZTÁSnak azt a bizonyos programozási tételt, mivel MINDIG van maximum ÉS minimum, HA legalább 1 elem van.
És tényleg az indexeket kéne eltenni, de akkor azokat kéne újrainicializálni (kinullázni)!
Tehát én így csinálnám:
// k. kör:
min=k;
max=k;
for (j=k+1; j<ARR-k; ++j) {
if (t[j] < t[min]) min=j;
if (t[j] > t[max]) max=j;
}
// kell még:
// csere(t[k],t[min])
// csere(t[ARR-k-1],t[max])
Másik észrevétel: Szerintem a k és az i mindig egyenlő... Tehát felesleges 2 változó.
Most hogy jobban belenéztem, a t[ARR-k]-t cseréled, de az az első körben (k=0) esetén túlindexelés!
válasza:Itt a teljesen agyatlan cserélgetésekkel van a probléma.
Nekem pl kijött ilyen példa:
A generalt tomb:
6, 16, 10, 11, 13, 9, 1, 11, 2, 14,
A reszben rendezett tomb:
1, 14, 10, 11, 13, 9, 6, 11, 2, 16,
A reszben rendezett tomb:
1, 14, 10, 11, 13, 9, 6, 11, 2, 16,
Itt jól látszik, hogy az első lépés után a max pont a második elem, a min pedig pont az utolsó előtti.
Emiatt az történik, hogy először megcseréli őket, majd megint megcseréli, vissza az eredeti, rendezetlen állapotra.
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
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!