Różnice między wersją iteracyjną a rekurencyjną implementacji algorytmu

Mam dwie wersje implementacji pewnego algorytmu sortowania: iteracyjną i rekurencyjną.

Problem jest taki, że wersja iteracyjna przechodzi testy, a rekurencyjna nie (następuje przepełnienie stosu; środowisko to NodeJS).

Oba zestawy testów są takie same. Test, którego nie przechodzi wersja rekurencyjna, to tablica o postaci:

[2, 0, 1]

Funkcja reprezentująca wersję iteracyjną wygląda tak:

exports.sortIterative
    = arr => {
        const res = arr.slice();

        while (true) {
            let swapped = false;
            let k = 0;

            while (k < res.length) {
                let m = k + 1;

                while (m < res.length && res[k] <= res[m]) {
                    ++m;
                    ++k;
                }

                while (m < res.length && res[k] > res[m]) {
                    ++m;
                }

                if (k !== m - 1) {
                    const tmp = res[k];
                    res[k] = res[m - 1];
                    res[m - 1] = tmp;

                    k = m - 1;
                    swapped = true;
                }

                ++k;
            }

            if (swapped === false) {
                break;
            }
        }

        return res;
    };

Funkcja reprezentująca wersję rekurencyjną wygląda tak:

exports.sort
    = (arr, k, m, swapped) =>
        k === arr.length
            ? swapped === false
                ? arr
                : exports.sort(arr, 0, 1, false)
            : m < arr.length && arr[k] <= arr[m]
                ? exports.sort(arr, k + 1, m + 1, swapped)
                : m < arr.length && arr[k] > arr[m]
                    ? exports.sort(arr, k, m + 1, swapped)
                    : k !== m - 1
                        ? exports.sort(
                            swapElems(arr, k, m - 1), m, m, true
                        )
                        : exports.sort(arr, k + 1, k + 2, swapped);

Wykluczmy na chwilę możliwość, że testy są niepoprawne. Czy możecie pomóc mi ocenić, czy są między nimi jakieś różnice?

Zagnieżdżone ternary operatory? Aż oczy bolą:) Dał byś radę to jakoś czytelniej przepisac?

@lion137: nie jestem pewien, czy dobrze Cię rozumiem – wersja z if-ami będzie czytelniejsza? Nie sądzę; ale może? Proszę – ale nie wiem, czy znów jakichś błędów nie popełniłem; ;) w każdym razie nadal ten błąd na tym samym teście:

exports.sort
    = (arr, k, m, swapped) => {
        if (k === arr.length) {
            if (swapped === false) {
                return arr;
            }

            return exports.sort(arr, 0, 1, false);
        }

        if (m < arr.length && arr[k] <= arr[m]) {
            return exports.sort(arr, k + 1, m + 1, swapped);
        }

        if (m < arr.length && arr[k] > arr[m]) {
            return exports.sort(arr, k, m + 1, swapped);
        }

        if (k !== m - 1) {
            return exports.sort(swapElems(arr, k, m - 1), m, m, true);
        }

        return exports.sort(arr, k + 1, k + 2, swapped);
    };

PS Aha, zapomniałbym: wersję rekurencyjną wywołuję tak:

sort([2, 0, 1], 0, 1, false)

Debugowałęś to w ogóle? Bo, jak jest out of memory dla tablicy trzyelementowej, to Masz prawdopodobnie buga; rekurencja się z jakiś powodów nie zatrzymuje.

Wiesz co, nie debugowałem. Raz, że pisałem to w Vimie, a nie mam dla niego jeszcze debugera ustawionego, a dwa, że rzadko do tej pory w ogóle potrzebowałem debugować swoje algorytmy w JavaScripcie… (może dlatego oprócz tego jednego wszystkie napisane do tej pory przechodzą testy :P). Może to i dobry pomysł, ale od ręki tego nie zrobię.

W ogóle mi się to nie podoba, Masz, z tej metody, pięć(!?!) returnów, w zasadzie sześć licząc ten niby końcowy, jak rozumiem, (return arr), na pewno o to chodzi? Z jednego wywołania funkcji robi się pięć, to jaka jest tego złożóność, 5^n?
A tak w ogóle, jeszcze, linijka 8:
return exports.sort(arr, 0, 1, false);
To Ci nie zapętla tej funkcji w nieskończoność?

Masz, z tej metody, pięć(!?!) returnów, w zasadzie sześć licząc ten niby końcowy, jak rozumiem, (return arr), na pewno o to chodzi?

No tak by wynikało z algorytmu iteracyjnego. Zauważ, że są tam 4 pętle i jeden warunek, a każde odpowiada jednemu return u mnie. Natomiast ostatnie jedno pozostałe return jest wyjściem z funkcji (return arr).

Z jednego wywołania funkcji robi się pięć, to jaka jest tego złożóność, 5^n?

Nie bardzo znam się (jeszcze) na złożoności, nie sprawdzałem.

(…) To Ci nie zapętla tej funkcji w nieskończoność?

Wiesz co, tak, zapętla. Co może warto wspomnieć, jak debugowałem "na sucho", bez debugera, to wszystkie warunki przechodziło – i się zapętlało. Już niestety usunąłem zapis.

PS W sumie rozwiązaniem mojego problemu będzie jeszcze wykazanie, że wersja iteracyjna też ma buga (jakiegokolwiek), który powoduje, że dla jakichś danych zwraca niepoprawny wynik. Wtedy po prostu skupię się na samym algorytmie, a nie na jego reprezentacji rekurencyjnej, a ten problem potraktuję jako nieistniejący.

PS W sumie rozwiązaniem mojego problemu będzie jeszcze wykazanie, że wersja iteracyjna też ma buga (jakiegokolwiek), który powoduje, że dla jakichś danych zwraca niepoprawne wartości. Wtedy po prostu skupię się na samym algorytmie, a nie na jego reprezentacji rekurencyjnej, więc ten problem potraktuję jako nieistnieją

Właśnie miałem pisać, czy iteracyjnie działa; masz skądś ten algorytm, czy to Twój autorski?

Mój autorski, ale nie wiem, czy to ma znaczenie. :) Ale jak mówię, testy przechodzi. Zamieszczę je tu może:

[]
[0]
[0, 0, 0]
[0, 1, 2]
[2, 1, 0]
[2, 0, 1]