Autor Zpráva
Niorko
Profil
Máme jednoduchú implementáciu Quick sortu:

function qs(l,r){
        var l=l; var r=r; var l2=l; var r2=r;
        var pivot=values[l];
                
        while (l!=r) {
            if (l>r) { return 0 }
            while (values[l]<pivot) { l=l+1; }
            while (values[r]>pivot) { r=r-1; }
            var temp = values[l];
            values[l] = values[r];
            values[r] = temp;
        }        

        var piv=l;
        qs(l2,piv-1);
        qs(piv+1,r2);
       
    } qs(0,9);

Plánujem to animovať, tak mi nestačí vnorená hotová implementácia, napísal som si script sám... Avšak v 4 zo 10 pokusov mi stránka zamrzne. Ako vyriešiť prípadné zacyklenie a zachovať pri tom takúto formu? Neviem si vysvetliť prečo sa mi to zacyklí, v Lue mi tento istý skript funguje za každým pokusom.

Ďakujem za pomoc =)
_es
Profil
Niorko:
var l=l; var r=r;
? l a r sú už automaticky premenné - sú to argumenty funkcie.

Čo je v premennej(?) values?

v Lue mi tento istý skript funguje za každým pokusom.
Čo je to to „Lue“?
Joker
Profil
Niorko:
var l=l; var r=r; 
Co má probůh tohle znamenat?

Jinak bych řekl, že se to opravdu může zacyklit. Na řídku 14 je piv = 1 a následně na 15 a 16 je piv-1 a piv+1.
Čili řádek 15 a 16 je pokaždé qs(l2, 0) a qs(2, r2).
Řádek 15 je tak úplně k ničemu, protože pro l2>=0 nakonec vždycky povede k return 0 na řádku 6 aniž by se v poli values něco změnilo.

Ani řádek 7 nic neudělá, protože do pivot se předtím přiřadí values[l], takže v prvním cyklu se vlastně testuje values[l]<values[l], což nikdy nemůže platit.

Zacyklí se to podle mě za těchto podmínek:
1. Pole není už na začátku seřazené, takže qs(0,9) dojde až k ř. 16 a volání qs(2,9). Jak píšu výš, ř. 15 a qs(0,0) nebude mít žádný vliv.
2. Ani v qs(2,9) není pole setříděné, takže znovu dojde na ř. 16 a znovu se zavolá qs(2,9)
3. Při některém volání qs(2,9) dojde k tomu, že na indexu 2 se ocitne nejnižší hodnota dané části pole (indexy 2-9) a zároveň pole ještě nebude úplně setříděné

Tím při každém volání nastane situace, že l==r, neplatí l>r a tedy se pokračuje, hodnota se prohodí sama se sebou a znovu se zavolá qs(2,9)
Niorko
Profil
_es:
Čo je v premennej(?) values?>
>
„v Lue mi tento istý skript funguje za každým pokusom.“
Čo je to to „Lue“?

Premenná Values je pole 10tich čísiel a Lua je skriptovací jazyk. Mám to na iPade, tak preto som to využil. Lua - Wiki

Joker:
var l=l; var r=r;
Co má probůh tohle znamenat?
Odstránil som to hneď po tom, ako som postol otázku, neviem odkiaľ mám tento zvyk.

Na řídku 14 je piv = 1 a následně na 15 a 16 je piv-1 a piv+1.
nie je to piv = 1, ale piv=l (čítam El - L ako Left), čiže podmienka je v pohode, podla mňa.

Řádek 15 je tak úplně k ničemu, protože pro l2>=0 nakonec vždycky povede k return 0 na řádku 6 aniž by se v poli values něco změnilo.
return false tam je preto, aby sa cykli stále neopakovali, ak by tam return false nebolo, stále by sa kontrolovali podmienky, takto to keď podmienka vyhovuje leavne celý sort.


Prikladám skript, ktorý som si písal na iPade a ktorý bol funkčný, len som ho prepisoval do JS, kvôli projektu. http://pastebin.com/ZT1pUAvM
Joker
Profil
Niorko:
nie je to piv = 1, ale piv=l (čítam El - L ako Left)
Jo tak. To už mě nejdřív zmátlo na řádku 2, když jsem myslel, že tam je var l=1.
Není úplně šťastné pojmenovávat proměnné jedním písmenem, zejména O a l.

Tak pak nejjednodušší řešení bude vzít nějaké pole pro které se to zacyklí a běh toho programu si trasovat.
_es
Profil
Niorko:
Možno bude problém v podmienkach na 7. a 8. riadku. JS umožňuje získať aj nedefinované prvky poľa, tie majú hodnotu undefined a vtedy je výsledkom porovnania false. Teda musíš overovať hranice poľa.
Joker
Profil
_es:
Taky mám hlavní podezření na undefined, ale nemohl jsem najít situaci, kdy by se to zacyklilo.

A přitom teď to jsem to uviděl skoro hned.
Zacyklí se to v případě, že libovolná hodnota pole bude buď undefined, nebo rovna nějaké jiné hodnotě pole.

V takovém případě není splněna ani podmínka na ř. 7, ani podmínka na ř. 8 (pokud jsou ty hodnoty stejné, je to zřejmé, a porovnání undefined s čímkoliv vrátí false), l a r se nezmění, hodnoty v poli se prohodí spolu navzájem a v dalším běhu se porovnají zase proti sobě a vznikne úplně stejná situace.
Dodatek: Neporovnají se ty hodnoty proti sobě, ale pivot se porovnává zase s úplně stejnými hodnotami
peta
Profil
Kdyz se mi neco zacykluje, tak si krok za krokem alertuji hodnoty nebo zapisuji do textarea, abych mohl sledovat, co se deje.
Co se stane v pripade, ze l=1 a r=1?
Co se stane v pripade, ze l=10 a r=-10? // dostanes se mimo oblast pole a nevidim tam zadnou podminku, kterou bys to hlidal. za l++ a r-- se obvykle pouziva %min nebo %max (ale tim bys zustal treba na predchozi hodnote a cyklil by dal) nebo if l>max, r<max ... return.
Joker
Profil
peta:
Kdyz se mi neco zacykluje, tak si krok za krokem alertuji hodnoty nebo zapisuji do textarea, abych mohl sledovat, co se deje.
Eh, no to je zase rada, vložit logování do nekonečného cyklu :-)
A v dnešní době tohle je trochu archaická metoda, ne? Pustím si v prohlížeči vývojářské nástroje, do skriptu si na vhodné místo dám breakpoint a sleduji, co se děje.

dostanes se mimo oblast pole a nevidim tam zadnou podminku, kterou bys to hlidal.
Ale je to ohlídané.
Jednak konstrukcí těch podmínek (buď l>=r a cyklus skončí, nebo mezi aktuální položkou a koncem pole je hodnota, na které se ty cykly l++/r-- zarazí v příštím běhu),
jednak nejmenší možné hodnoty jsou l=0, r=-1, přičemž r=-1 musí skončit return 0,
a jednak se ty cykly l++/r-- mohou dostat maximálně na první index mimo pole, protože jeho hodnota bude undefined a nebude splněna podmínka cyklu.
peta
Profil
Joker:
Omyl.
while (values[r]>pivot) { r=r-1; }
Kdyz ti tady dam na zacatku -1, tak ten cyklus pojede do nekonecna v zavislosti na tom, co ziskas z pole a v pivot. Takze tento cyklus neni ohlidany.
Niorko
Profil
function qs(left,right){
    var left2=left; var right2=right;
    var pivot=val[left];

    while (left!=right) {

        if (left>right) { return false; }

        while (val[left]<pivot) { ++left; }
        while (val[right]>pivot) { --right; }
        
        temp = val[left];
        val[left] = val[right];
        val[right] = temp;
    }

    piv=left;
    qs(left2,piv-1);
    qs(piv+1,right2);
                
} qs(0,9);

Pre prehľadnosť ešte raz postnuté. Okúsil som všetky možné hodnoty a keďže v reťazci val[] sú akceptované iba hodnoty od 1 do 99 vyšlo mi, že cyklí sa to iba v prípade, ak sa tam nachádza ten istý prvok viac krát. Nejak sa mi však stále nedarí to opraviť...
_es
Profil
Niorko:
Znovu: Musíš overovať hranice poľa. Počet prvkov poľa p je p.length.
Niorko
Profil
_es:
Ak overím hranice poľa, zostane mi pole porozhadzované. Stále tam je ten problém, že ak je v poli ten istý prvok, vyskytne sa chyba. Nie a nie prísť na to, ako to ošetriť.
_es
Profil
Niorko:
Ak overím hranice poľa, zostane mi pole porozhadzované.
Čo znamená „porozhadzované“? Máš snáď n prvkov poľa s indexami od 0 po n-1, či nie? A teda nie je problém ich v cykle všetky prejsť.

Máme jednoduchú implementáciu Quick sortu:
Veľa už hotových implementácií v JS sa dá určite nájsť vyhľadávačmi.

Vaše odpověď

Mohlo by se hodit

Neumíte-li správně určit příčinu chyby, vkládejte odkazy na živé ukázky.
Užíváte-li nějakou cizí knihovnu, ukažte odpovídajícím, kde jste ji vzali.

Užitečné odkazy:

Prosím používejte diakritiku a interpunkci.

Ochrana proti spamu. Napište prosím číslo dvě-sta čtyřicet-sedm: