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)
  1. <?php  
  2. $_SESSION['array'] = array(8, 9, 1, 176, -45, 27, 99, 31, 15, 35, 88, 74, 0 );  
  3. $_SESSION['cur'] = 1;  
  4. $_SESSION['stack'][1]['l'] = 0;  
  5. $_SESSION['stack'][1]['r'] = count($_SESSION['array'])-1;  
  6.   
  7. while ($_SESSION['cur'] != 0 ) {  
  8.     $_SESSION['l'] = $_SESSION['stack'][$_SESSION['cur']]['l'];  
  9.     $_SESSION['r'] = $_SESSION['stack'][$_SESSION['cur']]['r'];  
  10.     $_SESSION['cur']--;  
  11.      
  12.     while ($_SESSION['l'] < $_SESSION['r'] ) {  
  13.         $_SESSION['i'] = $_SESSION['l'];  
  14.         $_SESSION['j'] = $_SESSION['r'];  
  15.         $_SESSION['tmp'] = $_SESSION['array'][(int)( ($_SESSION['l']+$_SESSION['r'])/2 )];  
  16.          
  17.         // partion the array in two parts.  
  18.         // left from $_SESSION['tmp'] are with smaller values,  
  19.         // right from $_SESSION['tmp'] are with bigger ones  
  20.         while ($_SESSION['i'] <= $_SESSION['j'] ) {  
  21.             while ($_SESSION['array'][$_SESSION['i']] < $_SESSION['tmp'] ) {  
  22.                 $_SESSION['i']++;  
  23.             }  
  24.              
  25.             while ($_SESSION['tmp'] < $_SESSION['array'][$_SESSION['j']] ) {  
  26.                 $_SESSION['j']--;  
  27.             }  
  28.              
  29.             // swap elements from the two sides  
  30.             if ($_SESSION['i'] <= $_SESSION['j'] ) {  
  31.                 $_SESSION['w'] = $_SESSION['array'][$_SESSION['i']];  
  32.                 $_SESSION['array'][$_SESSION['i']] = $_SESSION['array'][$_SESSION['j']];  
  33.                 $_SESSION['array'][$_SESSION['j']] = $_SESSION['w'];  
  34.                  
  35.                 $_SESSION['i']++;  
  36.                 $_SESSION['j']--;  
  37.             }  
  38.              
  39.         }  
  40.          
  41.          
  42.         if ($_SESSION['i'] < $_SESSION['r'] ) {  
  43.             $_SESSION['cur']++;  
  44.             $_SESSION['stack'][$_SESSION['cur']]['l'] = $_SESSION['i'];  
  45.             $_SESSION['stack'][$_SESSION['cur']]['r'] = $_SESSION['r'];  
  46.         }  
  47.         $_SESSION['r'] = $_SESSION['j'];  
  48.          
  49.     }  
  50.      
  51. }  
  52.   
  53. print_r($_SESSION['array']);  
  54. ?>  
‹ 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:
  1. #             // swap elements from the two sides    
  2. #             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
  1. // swap elements from the two sides      
  2. 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:
  1.    
  2. 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.