ugrás a tartalomhoz

rendezés a felhasználó kedvtelése szerint - quicksort

frankdavid · 2008. Jún. 5. (Cs), 15.45
Van egy tömböm, ami gyümölcsnevekből áll. pl: array("banán", "citrom", "eper", "dinnye", "alma")
Egy körben megkérdezem a felhasználót, hogy melyiket szereted jobban, a ....-t vagy a ....-t, a .... helyén persze egy-egy gyümölcs van a tömbből. És pár kérdés(lehetőleg minnél kevesebb kérdés) után megadom neki, hogy mi a "szeretési listája". A rendezést ugye quicksorttal lehet a leggyorsabban(legkevesebb kérdéssel) megcsinálni, de a PHP program, amit láttam quicksorthoz, számokat rendez nagyság szerint. Hogy alakítsam át? Addig ok, hogy a változókat SESSION-be teszem, de hogy ugorjak bele a ciklus közepébe?

Ez a program, ami számokat rendez(a változókat már session-be rakva)

<?php
$_SESSION['array'] = array(8, 9, 1, 176, -45, 27, 99, 31, 15, 35, 88, 74, 0 );
$_SESSION['cur'] = 1;
$_SESSION['stack'][1]['l'] = 0;
$_SESSION['stack'][1]['r'] = count($_SESSION['array'])-1;

while ($_SESSION['cur'] != 0 ) {
    $_SESSION['l'] = $_SESSION['stack'][$_SESSION['cur']]['l'];
    $_SESSION['r'] = $_SESSION['stack'][$_SESSION['cur']]['r'];
    $_SESSION['cur']--;
   
    while ($_SESSION['l'] < $_SESSION['r'] ) {
        $_SESSION['i'] = $_SESSION['l'];
        $_SESSION['j'] = $_SESSION['r'];
        $_SESSION['tmp'] = $_SESSION['array'][(int)( ($_SESSION['l']+$_SESSION['r'])/2 )];
       
        // partion the array in two parts.
        // left from $_SESSION['tmp'] are with smaller values,
        // right from $_SESSION['tmp'] are with bigger ones
        while ($_SESSION['i'] <= $_SESSION['j'] ) {
            while ($_SESSION['array'][$_SESSION['i']] < $_SESSION['tmp'] ) {
                $_SESSION['i']++;
            }
           
            while ($_SESSION['tmp'] < $_SESSION['array'][$_SESSION['j']] ) {
                $_SESSION['j']--;
            }
           
            // swap elements from the two sides
            if ($_SESSION['i'] <= $_SESSION['j'] ) {
                $_SESSION['w'] = $_SESSION['array'][$_SESSION['i']];
                $_SESSION['array'][$_SESSION['i']] = $_SESSION['array'][$_SESSION['j']];
                $_SESSION['array'][$_SESSION['j']] = $_SESSION['w'];
               
                $_SESSION['i']++;
                $_SESSION['j']--;
            }
           
        }
       
       
        if ($_SESSION['i'] < $_SESSION['r'] ) {
            $_SESSION['cur']++;
            $_SESSION['stack'][$_SESSION['cur']]['l'] = $_SESSION['i'];
            $_SESSION['stack'][$_SESSION['cur']]['r'] = $_SESSION['r'];
        }
        $_SESSION['r'] = $_SESSION['j'];
       
    }
   
}

print_r($_SESSION['array']);
?>
‹ mySQL insert form probléma cookie és session változó problémák ›
 ■
1

Ne ugorj bele

N0r3i · 2008. Jún. 5. (Cs), 16.08
Szerintem beleugrani a ciklus közepébe nem fogsz tudni, egyébként is a quicksort (is) olyan párokra is rákérdez, amikre egyszer már kaptál választ.

Szóval én úgy csinálnám, hogy begyűjteném a felhasználótól a sorrendre adott válaszait, és amikor az algoritmus olyan párra kérdez rá, amire a felhasználó még nem adott választ, akkor kérdeznék, egyébként a korábbi válasz alapján hagynám rendezni.
Ja és minden válasz után előlről újraindítanám a rendezést, vélhetően nem lesz olyan sok elem, hogy túl sokáig fusson, egyébként a felhasználó kap hülyét :-)

Norbi
2

xxx

frankdavid · 2008. Jún. 5. (Cs), 16.12
Köszi a gyors választ! Abban nincs igazad, hogy újra megkérdezni az egyszer összehasonlított elemeket. Egyébként le tudnád egy kicsit konkrétabban írni, hogy mire gondolsz?
Köszönettel: Dávid
4

De mégis szerintem megkérdezi

N0r3i · 2008. Jún. 5. (Cs), 18.45
Úgy értem, a sorbarendezés során olyan elempárokra is lefut az összehasonlítás, amik amúgy sorban vannak már, másképp az algoritmus (pláne ha mindig újraindítod) honnét tudná, hogy azok sorban vannak?

Itt van pl. ez a rész a kódodból:

#             // swap elements from the two sides  
#             if ($_SESSION['i'] <= $_SESSION['j'] ) {
Ugyebár ha a feltétel nem teljesül, akkor nem fog cserélni, de honnét tudja, hogy teljesül-e? Össze kell hasonlítani. Itt ágaztatnám én ketté a dolgot, aszerint, hogy a két elem közti viszonyt a felhasználótól már megkérdeztem (akkor el tudom végezni az összehasonlítást, ha megőriztem a választ), illetve ha még nem kérdeztem meg: ekkor kiírom a kérdést. Ha megvan a válasz, akkor újraindítom az egész rendezést, és amikor ismét ehhez a ponthoz ér az algoritmus, akkor már ismert lesz a válsz, tehát mehetünk tovább.

Erre gondolok, szerintem így megoldható.
Érdekel annyira a probléma, hogy meg is írnám, de sajnos még dolgozom :-( Majd máskor.

Norbi
5

?????

frankdavid · 2008. Jún. 5. (Cs), 20.36

    // swap elements from the two sides    
    if ($_SESSION['i'] <= $_SESSION['j'] ) {
itt az i és a j számok, nem pedig tömbelemek, szóval két kulcsot hasonlít össze, nem pedig két tömb értéket.
7

Rossz volt a példa, de

N0r3i · 2008. Jún. 6. (P), 08.01
akkor is össze kell hasonlítani az elemeket, mint pl itt:
 
while ($_SESSION['array'][$_SESSION['i']] < $_SESSION['tmp'] ) {
Ez már tömbelem-összehasonlítás?
9

igen

frankdavid · 2008. Jún. 6. (P), 12.06
igen, de abban nincs igazad, hogy 2x fogja összehasonlítani ugyanazt a két elemet, mert a quicksort úgy működik, hogy miután 1x összehasonlította az elemeket a $tmp-vel, két részre bontja a tömböt, és márcsak azokon belül hasonlítgat össze.

Dávid
11

Igazad lenne, de

N0r3i · 2008. Jún. 7. (Szo), 06.41
Igazad lenne, ha le tudnád futtatni a rendezést "egy menetben", azaz, ha bele tudnál ugrani az algoritmus közepébe a felhasználói válasz után. De ez sajnos (ajax nélkül biztosan) nem fog menni.

Szóval még 1x az én elképzelésem:
- minden felhasználói válasz után újraindítod a rendezést, mivel a közepébe beleugrani nem tudsz (tehát az egyszer eldöntött sorrendet is újra-és-újra ellenőrizni fogod)
- a felhasználó válaszait rendre megjegyzed (mondjuk session változókban), és ezt használod a rendezés során, ha rendelkezésre áll
- ha az adott 2 elem sorrendjére nincs még tárolt felhasználói válasz, akkor kirakod az űrlapot, és megvárod a választ

Továbbá egyetértek a többiek hozzászólásával is: magát a rendezést nem kódolnám le újra, hanem az usort függvénnyel rendeznék, és igénybe venném a callback lehetőséget az összehasonlításra.

Norbi

Ps: közben annyira bizgatta a dolog a fantáziámat, hogy megírtam (kb. 10 perc volt...), és gyönyörűen működik, mindet csak egyszer kérdez meg. Nem túl szép, nincs agyon-optimalizálva, de működik. Viszont nem akarom elrontani az örömödet, úgyhogy nem másolom ide. Legfeljebb ha ragaszkodsz hozzá... :-)
13

megpróbálom

frankdavid · 2008. Jún. 7. (Szo), 10.33
Köszi a 5letet, megpróbálom megcsinálni, ha nem megy, szólok, és akkor majd pls copy!

Dávid
14

MŰKÖDIK

frankdavid · 2008. Jún. 7. (Szo), 11.59
MŰKÖDIK!
KÖSZI A SEGÍTSÉGET!!!
3

sort

Poetro · 2008. Jún. 5. (Cs), 18.14
Használd a PHP sort függvényét, ami minden valószínűség szerint szintén quicksort-ot használ (vagy usort, ha te akarod meghatározni az összehasonlítás szabályait).
6

dasdasd

frankdavid · 2008. Jún. 5. (Cs), 20.38
Csak ezeknél nem tudom, hogy lehet megoldani, hogy letöltse az oldalt(a php program befejezése, űrlap megjelenítése), majd valahonnan újból folytassa a php-t.
8

Bevallom nem nagyon értem mi alapján rendezed a tömbödet

griphons · 2008. Jún. 6. (P), 10.56
Bevallom nem nagyon értem mi alapján rendezed a tömbödet, de több dolog is van ami sztem felesleges.
Minek belekavarni a SESSION változókat? Ha olyan értékekre van szükség amik lépésről lépésre változnak (oldaltöltésről oldaltöltésre) akkor is használhatsz $_POST vagy $_GET változókat (ha jól értettem vmi űrlapos kérdezősködésről van szó). Ha meg csak kiértékelésről van szó, és SESSIONben tárolod az eredményt, elég csak a végeredményt abba rakni.

Ha már tömb rendezésről van szó használd az array_multisort(); gyönyörűséges függvényt, amivel több tömb alapján is, oda-vissza, keresztbe és átlósan :) is tudsz rendezni. Szerintem felesleges újra feltalálni a spanyolviaszt, ha a php már megtette...
10

hát így

frankdavid · 2008. Jún. 6. (P), 12.11
Úgy rendezem, hogy megkérdezem a felhasználót: mit szeretsz jobban, a banánt vagy az almát? aztán az almát vagy az epret? stb.. s a kérdésekből a program kiszámolja, hogy mi a sorrendje a gyümölcsöknek a szeretése szerint. sztem a php beépített rendezési függvényeit nem tudom használni, mert minden egyes összehasonlításnál meg kell szakítani a PHP-programot, hogy kiadja az űrlapot, ezért kell SESSION. ( legalábbis sztem )
12

Nem lenne jobb egy draganddrop?

vbence · 2008. Jún. 7. (Szo), 09.54
Ennyi kerdesre valaszolni remalom a usernek is meg neked sem egyszeru leprogramozni egy rekurziv algoritmust ugy, hogy minden IF utan ki kell nyomni egy HTML reszt, elmenteni a program allasat, majd befejezni. A submit utan meg rekonstrualni az elozo futasi kornyezetet es tovabb futtatni mintha misem tortent volna a kovetkezo IF-ig.