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?