Diskuze: quick sort - kde je chyba

Peter Mlich

Člen

Peter Mlich:24.11.2021 14:35

Hraji si s implementaci quicksortu na me nove testovaci rozhrani a nekde mam chybu v algoritmu. Umel by nekdo zjistit, kde?

function quicksortPartition(items, left, right, cmp)
        {
        var cycles = 0;
        var moves = 0;
        var mid   = (right + left)>>1,  // mid = L + (R - L) / 2 = (2L + R - L) / 2 = (L+R)/2   //Math.floor((right + left) / 2)
            pivot = items[mid],
            i     = left,
            j     = right;
        moves++;
//console.log(mid, pivot)
        while (i <= j)
                {
//        while (items[i] < pivot) {
                while (cmp(items[i], pivot) < 0)        // najde prvni vetsi nez pivot, zleva
                        {
                        i++;
        cycles++
                        }
//        while (items[j] > pivot) {
                while (cmp(items[j], pivot) > 0)        // najde prvni mensi nez pivot, zprava
                        {
                        j--;
        cycles++
                        }
                if (i <= j)
                        {
                        swap(items, i, j);              // a kdyz to neco naslo, tak je vzajemne vymeni - a myslim si, ze tady muze dojit k tomu, ze se porusi poradi polozek (protoze se hleda od konce), stabilita sortu (muze byt rychly, jak chce, ale bez stability je na prd)
                        i++;
                        j--;
                        }
        cycles++
                }
        glob.moves += moves;
        glob.cycles += cycles;
        return i;
        }

//# Quick Sort Function
function XsortBubblingQuick_m1_v2(cmp, start, end, n)
// v debugu to zatim nedava spravne serazene
        {
        var o = mm.func.sortReset(cmp, start, end, n);
        if (o.size<2) {return o.n;}
        if (!(o.fn_getTime(false)<o.tmax)) {return o.n;}
//console.log(typeof end !== "undefined");
        o.end = typeof end !== "undefined" ? o.end : o.end - 1;
        var index = quicksortPartition(arr[o.n], o.start, o.end, o.fn_cmp);
        if (o.start < index-1)
                XsortBubblingQuick_m1_v2(o.fn_cmp, o.start, index-1, o.n);
        if (index < o.end)
                XsortBubblingQuick_m1_v2(o.fn_cmp, index, o.end, o.n);
        return o.n;
        }

Zkusil jsem: https://mlich.zam.slu.cz/…g4-pokus.htm

test2
debug = actived
start

id alg name                 | cycles moves cmp   time | t0
 0 sortJsNative             |      0     0  9005    2 |  2
 1 sortListMerge_m2_v2      |  11001 10000  8726    2 |  2
18 sortBubblingQuick_m2_v1  |  11936 16476 11281    4 |  4
19 XsortBubblingQuick_m1_v2 |   9478  7366 12126    3 |  3

Po sem je to ok.
Ale, protoze mate DEBUG on, tak v "Debug input/output" vyberte pred tlacitkem "Show out" volbu "number-diff" a kliknete na "show out".
Zobrazi vam vystup posledniho sortu, cili XsortBubblingQuick_m1_v2.

V kodu mam pak nejaky zdroj z javy. Ja myslim, ze jsem to prepsal spravne. I na pohled to tak vypada. Nechce se mi ted ztracet cas a hledat ten rozdil. Takze, kdyby si nekdo chtel hrat.
Ale, osobne bych spis uvital tuto podobnou verzi, ktera je typu stabilni-sort. Myslim si, ze tato nebude, protoze swapuje polozky od konce array za pivotem.

o.end pri prvnim pruchodu ma hodnotu arr.length.
Tam je ta funkce, co naplnuje promenou o, ktera resi, zda je neco definovano nebo ne. Proto je tam ten dalsi test pro end, zda je defined, protoze v tom algoritmu tam davaji end = arr.length-1

Chci docílit: Spravne serazene by melo zobrazovat 1 1 1 1 1 1 1 1... vse same 1, rozdil dvou po sobe jdoucich cisel (takovy rychly opticky test)
Ale, zobrazuje 1 1 1 1 1 1 1 1 2 -1 2. To znamena, ze to seradil spatne.

Editováno 24.11.2021 14:38

Odpovědět

24.11.2021 14:35

Peter Mlich

Člen

Peter Mlich:26.11.2021 11:43

No, uz jsem to asi nasel. Resil jsem jiny kod a narazil na problem, ze se neprovedou vsechna zanorovani, protoze tam mam podminku

if (o.size<2) {return o.n;}

Coz je zrovna u quicksortu chyba, protoze tam nemam start, end, ale start a end-1. Tim padem se size spocita chybne pro 2 prvky je 1. A jeden cylus/permutace se nevykona

A myslim, ze u toho algoritmu mam ten samy problem jako u toho, co jsem ted resil.

Nahoru Odpovědět

26.11.2021 11:43

Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 2 zpráv z 2.